Second Element as Pivot in Quicksort

Question

I have an assignment that involves the Quicksort algorithm. I have read it severally from different texts and sites like GeeksforGeeks, FCC, JavaPoint, etc. I understand the algorithm, and I understand the sample codes.

The problem I am facing is that the lecturer requires that the pivot is the second element, arr[1].

Here is the code I wrote, for partitioning:

arr = [34, 8, 3, 4, 5, 67, 43]

pivot = arr[1]
j = 0
for i in range(len(arr)):
    if arr[i] >= pivot:
        j = i
    if arr[i] < pivot and i > 1:
        arr[i], arr[j] = arr[j], arr[i]

print(arr)

[What I got]: [34, 8, 3, 4, 5, 67, 43]

[Expected}: [4, 3, 5, 8, 67, 34, 43]

I understand that that chunk of code should be wrapped in a partition function, and I will recursively sort the left and right parts.

So, can someone help me look into it?

Answer 1

It looks like you tried to implement the Lomuto partition scheme, but there are some issues with it:

1. j = i is not right. It sets j to the most recent entry you have found that is not less than the pivot. But thereby you might skip over a previous entry that was also in that situation, and which was not swapped yet. So that previous one is now forever assigned to the left partition, while it should end up in the right partition. Instead, j should point to the first entry you have found that is not less than the pivot, or in other words, it should mark the start of the right partition, and should therefore only increment with steps of 1.

2. After the loop has ended, your code does not ensure that the pivot value is placed between the two resulting partitions. The Lomuto partition scheme does this so that the caller can exclude this index from the two partitions that will be the subject of recursive calls.

Here is a corrected version using the Lomuto partition scheme:

def partition(arr, lo, hi):
    pivot = arr[lo + 1]  # The second value in the current partition
    # Swap the pivot out of the way (to the far right)
    arr[hi], arr[lo + 1] = pivot, arr[hi]
    for i in range(lo, hi):  # Iterate the range, excluding the pivot
        if arr[i] <= pivot: 
            arr[i], arr[lo] = arr[lo], arr[i]
            lo += 1  # Increase the index where the righthand partition starts
    # Move the pivot value (from the right) to the correct pivot index
    arr[hi], arr[lo] = arr[lo], arr[hi]
    return lo  # Return the pivot index

Call as:

arr = [34, 8, 3, 4, 5, 67, 43]
partition(arr, 0, len(arr) - 1)