Quicksort implementation, array does not sort

Seun Seun 0
Viewed 61

##I am implementing quicksort in python, but my array is not changing in result, I do not understand if the algorithm is wrong or the way I am returning the array is not correct. Please help ##

def partition(array, left, right):
  x = array[right]
  left_pointer = left
  for right_pointer in range(left, right):
     if array[right_pointer] <= x:
        swap(array[right_pointer], array[left_pointer])
        left_pointer += 1
  swap(array[left_pointer], array[right])
  return left_pointer


def swap(x, y):
  x, y = y, x
  return x, y


def quicksort(arr, left, right):
  # print(left, right)
  if left < right:
    pivot = partition(arr, left, right)
    quicksort(arr, left, pivot - 1)
    quicksort(arr, pivot + 1, right)
  return array


array = [2, 6, 5, 3, 8, 7, 1, 0]
n = len(array) - 1
print(array)
print(quicksort(array, 0, n))
quicksort sorting arrays algorithm python
3 Answers

The error is in your swap function. You are passing values, which get swapped and then discarded.

Rewrite it like this:

def swap(a, l, r):
  a[l], a[r] = a[r], a[l]

swap(array, right_pointer, left_pointer)
swap(array, left_pointer, right)
fafl0

No need to use a swap function, use this code in your partition function for swapping the data.
Below, i = your first pointer and j = variable of 'for loop'

# swapping element at left with element at right
    (array[i], array[j]) = (array[j], array[i])

# swap the pivot element with the greater element specified by i
    (array[i + 1], array[right]) = (array[right], array[i + 1])

when you use this code in your partition function so, No need to compare data in quicksort function. In quicksort function set pivot elements.

Shubh Patel0

Thank you so much for your solutions. I realized I was not calling the quicksort function on my array and I got rid of the swap function. The code is working fine now

def partition(array, left, right):
  x = array[right]
  left_pointer = left
  for right_pointer in range(left, right):
    if array[right_pointer] <= x:
        array[right_pointer], array[left_pointer] = array[left_pointer], array[right_pointer]
        left_pointer += 1
  array[left_pointer], array[right] = array[right], array[left_pointer]
  return left_pointer


def quicksort(arr, left, right):
# print(left, right)
 if left < right:
    pivot = partition(arr, left, right)
    quicksort(arr, left, pivot - 1)
    quicksort(arr, pivot + 1, right)
 return arr


array = [2, 6, 5, 4, 3, 8, 7, 1, 0]
print(quicksort(array, 0, len(array)-1))
Seun Seun0
Related