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