Quick Sort Implementation Python - Understanding Base Cases

Question

I've been trying to understand quick sort by implementing it myself in Python using the left and right pointer method. I can't seem to get it to work and looking at visualizations online, I'm failing to understand how quicksort works when operating on a list of length 2. According to most sources I've read, you should select a pivot and your left and right pointers should not include that pivot value when moving left/right. When a list is of length 2, you select a pivot and are left with a list of length 1 and left/right immediately meet. How would quicksort ever sort the input [5,4]?

Here is the Python code I have written:

def quicksort(arr, low, high):
  if low < high:
    pivot_index = partition(arr, low, high)
    quicksort(arr, low, pivot_index-1)
    quicksort(arr, pivot_index+1, high)

  return arr

def partition(arr, low, high):
  # select last element as pivot
  pivot_index = high
  pivot = arr[high]
  left_wall = low
  # exclude pivot from left/right searching
  right_wall = high-1

  # keep searching until next swap point found
  while left_wall < right_wall:
    # if left wall value is not greater than pivot, keep searching
    while arr[left_wall] <= pivot:
      left_wall += 1
    # if right wall value is not less than pivot, keep searching
    while arr[right_wall] >= pivot:
      right_wall -= 1
    if left_wall < right_wall:
      # perform swap
      temp_left_wall = arr[left_wall]
      arr[left_wall] = arr[right_wall]
      arr[right_wall] = temp_left_wall

  # swap pivot with right wall
  arr[pivot_index] = arr[right_wall]
  arr[right_wall] = pivot
  return right_wall


quicksort([5,4,3,2],0,3)

Can someone help me understand what I am not understanding about the quicksort process?

With the algorithm you're trying to implement, 4 will be the pivot. You'll "partition" the remaining list, moving 5 to "top half" of the array. I.e. you'll have [5,5]. Now you'll swap the pivot to the position below the top half, which makes it [4,5]. If this isn't happening, you have a bug, a good exercise to figure out. — Gene
– Gene, Commented May 7, 2024 at 23:05
The pivot is moved if necessary. In the top level of the recursion, the algorithm creates a state where the pivot element is at its final position in the array, all smaller elements than pivot to the left, all greater to the right. Then do the same recursively to right and left subarrays. — Michael Butscher
– Michael Butscher, Commented May 7, 2024 at 23:08
@Gene Thanks for your response. Can you explain more how this partitioning works on [5,4]? I choose 4 as pivot. Then I just have an array [5] where left and right immediately meet because I excluded the pivot from my list. How do you get around this? — Kirency
– Kirency, Commented May 7, 2024 at 23:14
You have for example while arr[right_wall] >= pivot: this will cause right_wall to cross over the pivot. Same for the left pointer. NB "... your left and right pointers should not include that pivot value": where did you read that? It contradicts what both Knuth and Sedgewick have written about this, and they know more about it than anybody except maybe C.A.R. Hoare.. — user207421
– user207421, Commented May 8, 2024 at 1:46

trincot · Accepted Answer · 2024-05-08 11:17:12Z

First, realise that there are several different schemes for implementing Quicksort, notably the Lomuto and Hoare schemes, and they are quite different. You seem to have taken a mix from both of them resulting in a failing implementation.

If we look at the quicksort function, we see the typical pattern of a Lomuto scheme (the Hoare scheme returns an index that is not necessarily having the pivot value).

Also the first part of the partition function follows a Lomuto scheme.

But then in the loop you have logic that resembles the Hoare scheme. This is asking for problems. Wikipedia on Quicksort and the Hoare partition scheme warns:

With respect to this original description, implementations often make minor but important variations. [...] the argument for correctness of an implementation of the Hoare partition scheme can be subtle, and it is easy to get it wrong.

And here it goes wrong:

The indices in your innermost loop can easily run out of bounds of the array. For instance, if we give [3, 2, 1] or [1, 2, 3] or [1, 1, 1] as input, we get:

IndexError: list index out of range

The Hoare scheme does not have this problem, because it exits the inner loops as soon as a value equal to the pivot is found and because it is certain the pivot value occurs at least once within the current window. The latter is not true in your implementation, because you excluded the pivot element from the window at the start -- which is the Lomuto system. Here is how Wikipedia represents those Hoare inner loops:

    do i := i + 1 while A[i] < pivot
    do j := j - 1 while A[j] > pivot

Also note that these loops always apply at least one update to the respective index. This is important, because after a swap has executed, the two indices could still represent values that would not satisfy the inner loop conditions (if corrected). This could lead to infinite loops.

As you can see, the details are important... very important.

The quicksort partitioning is not as trivial as it may seem at first sight. There are several pitfalls.

I would suggest to either implement the Lomuto scheme or the Hoare scheme (don't mix them!), and use the corresponding pseudo code presented at Wikipedia as starting point.

Collectives™ on Stack Overflow

Quick Sort Implementation Python - Understanding Base Cases

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related