Python- How to implement quick sort when middle element is the pivot?

Question

There are many different versions of quickSort that pick pivot in different ways.

Always pick the first element or the last element as the pivot
Pick a random element as a pivot.
Pick median as the pivot.

I have implemented using the last element as the pivot everything worked fine but when I tried to implement the same logic to the middle element, it's no working fine.

Here's my code in python:

import random
import time
start = time.time()

def quickSort(a,l,r):
    if(l<r):
        p = partition(a,l,r)
        quickSort(a,l,p-1)
        quickSort(a,p+1,r)

def partition(a,l,r):
    i = l-1
    p = a[(l+(r-l))//2]
    for j in range(l,r):
        if a[j] <= p:
            i += 1
            a[i],a[j] = a[j],a[i]
            
    a[i+1],a[r] = a[r],a[i+1]
    return (i+1)

N = 10
a = [random.randint(1,100) for i in range(N)]
print(a)
quickSort(a,0,N-1)
print(a)
print("It took %s milli seconds"%((time.time()-start)*100))

This is the output

[88, 35, 55, 68, 96, 23, 44, 77, 78, 71]
[35, 55, 23, 68, 44, 77, 88, 96, 78, 71]
It took 1.5625953674316406 milli seconds

no matter middle of random position, you better move that element to the end, then it becomes the same as selecting element from end as pivot. Without this move, the indexing is nightmare — Bing Wang, Jan 14 '21 at 18:36

rcgldr · Accepted Answer · 2021-01-16T18:55:00.980

Using Hoare partition scheme is better suited to using the middle value as pivot, and Hoare partition scheme is typically faster than the Lomuto partition scheme used in the question.

def qsort(a, lo, hi):
    if(lo >= hi):
        return
    p = a[(lo + hi) // 2]       # pivot, any a[] except a[hi]
    i = lo - 1
    j = hi + 1
    while(1):
        while(1):               # while(a[++i] < p)
            i += 1
            if(a[i] >= p):
                break
        while(1):               # while(a[--j] < p)
            j -= 1
            if(a[j] <= p):
                break
        if(i >= j):
            break
        a[i],a[j] = a[j],a[i]
    qsort(a, lo, j)
    qsort(a, j+1, hi)

As commented above, if you still want to use Lomuto partition scheme, swap the middle element with the last element and use your code with the last element.

Python- How to implement quick sort when middle element is the pivot?

1 Answers1

Linked