Home > Blockchain >  Quicksort implementation, array does not sort
Quicksort implementation, array does not sort

Time:09-15

##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))

CodePudding user response:

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)

CodePudding user response:

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.

  • Related