Quicksort implementation, array does not sort

Question

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

What output do you get? What output do you expect? Please make sure you take the tour and read How to Ask. Also, make sure the code is a minimal reproducible example, in particular the amount of input data seems suspicious to me. That said, try to find a video that teaches you how to step through the code with a debugger. Finding out where it takes the wrong turn should be simple with that. — Ulrich Eckhardt
– Ulrich Eckhardt, Commented Sep 15, 2022 at 5:19
Perfect opportunity to debugging. This is a small failing example. Some print statements and maybe pen and paper should do the trick. — MrSmith42
– MrSmith42, Commented Sep 15, 2022 at 6:14

fafl · Accepted Answer · 2022-09-15 05:15:22Z

2

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)

answered Sep 15, 2022 at 5:15

fafl

7,5074 gold badges32 silver badges54 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

greybeard · Accepted Answer · 2022-09-15 10:04:40Z

2

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.

edited Sep 15, 2022 at 10:04

greybeard

2,6779 gold badges40 silver badges71 bronze badges

answered Sep 15, 2022 at 8:56

Shubh Patel

791 silver badge6 bronze badges

3 Comments

greybeard Over a year ago

There is no function in the question named array: What are you referring to with in your array function? Consider using a spelling checker.

Shubh Patel Over a year ago

I have edited..

greybeard Over a year ago

I appreciate your effort to improve your answer. I tried to lend a hand with markdown…

Seun Seun · Accepted Answer · 2022-09-15 18:51:22Z

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

Collectives™ on Stack Overflow

Quicksort implementation, array does not sort

3 Answers 3

Comments

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related