Algorithms - Quicksort

                                                             QUICKSORT

Excellent explanation at https://www.youtube.com/watch?v=3DV8GO9g7B4

The fundamentals of Quicksort lies in finding the PIVOT (done using the partition method). At the end of partition call, the “pivot” number is PUT IN THE CORRECT LOCATION IN THE ARRAY. i.e To the left of pivot all elements are smaller or equal to it and to the right of the pivot, all elements are bigger than it. The same is repeated on left of the pivot and right of the pivot recursively.

Best case – O(nlogn)

Worst case – O(n²). This can be mitigated by doing a randomization of the array before the operation. (so that its not sorted by chance).

UNLIKE MERGESORT WHERE BOTH BEST AND WORST CASE IS O(nlogn)

Python implementation –

def partition(A,p,r):

    x = A[r]

    i = p-1

    j = p

    while (j<=r-1):

        if A[j] <= x:

            i=i+1

            A[i],A[j] = A[j],A[i]

        j=j+1

    A[i+1],A[r] = A[r],A[i+1]

    return i+1

   

def quicksort(A,p,r):

    if (p<r):

        q = partition(A,p,r)

        quicksort(A,p,q-1)

        quicksort(A,q+1,r)

inputlist = [343,454,232,56565,3432,1,444,454,232,233,4,5,78,]

quicksort(inputlist,0,len(inputlist) - 1)

print inputlist

Practical application of Quicksort -

1)      Find the kth largest element in an array (known as QUICKSELECT). Quickselect is LINEAR on average.

2)      Quicksort (randomized) is 39% faster than Mergesort and doesn’t use any auxiliary extra space.  

Program for QuickSelect (find kth largest value)

def partition(A, p, r):

    j = p

    i = j - 1;

    x = A[r]

    while (j <= r - 1):

        if (A[j] <= x):

            i += 1

            A[i], A[j] = A[j], A[i]

        j += 1

    A[i + 1], A[r] = A[r], A[i + 1]

    return i + 1;

   

def quickselect(A, p, r, k, output): #to find kth largest number using quicksort like technique.      

    if (p <= r):

        q = partition(A, p, r)          

        if (q == k -1):

            output = A[q]           

        elif (k - 1 < q):

            output = quickselect(A, p, q - 1, k, output)

        else:

            output = quickselect(A, q + 1, r, k, output)   

    return output

A = [12, 4, 45, 2, 1, 88, 90, 15, 18]

kthvalue = quickselect(A, 0, len(A) - 1, 3, "Not found")  #find the kth largest value

print(kthvalue)