Quick sort

Worst case is O(n^2)
Average case is O(nlogn)
Performance depends largely on Pivot selection

Select a pivot from the array

first element
last element
middle element
mediem of above three



In [32]:

    
# source: https://github.com/joeyajames/Python/blob/master/SortingAlgorithms.py
def select_pivot(array, low=0, hi=None):
    if not hi:
        hi = len(array) - 1
        
    mid = (low + hi) // 2
    s = sorted([array[low], array[mid], array[hi]])
    
    #choice the middle element in `s`
    if s[1] == array[low]:
        return low
    if s[1] == array[mid]:
        return mid
    return hi

border: any elements in left of border are less than pivot



In [ ]:



In [36]:

    
def quick_sort(array, lo=0, hi=None):
    if hi is None:
        hi = len(array) - 1
    
    def _quick_sort(array, lo, hi):
        if lo >= hi:
            return
        
        pivot = partition(array, lo, hi)

        _quick_sort(array, lo, pivot-1)
        _quick_sort(array, pivot+1, hi)
    
    return _quick_sort(array, lo, hi)

def partition(array, lo, hi):

    # simply select first element as pivot
    #   or use sorted(low, midum, high)[1] as pivot,
    #       and exchange with a[lo]
    pivot = array[lo]

    border = lo # border: any elements in left of border are less than pivot
    
    for i in range(lo, hi + 1):
        if array[i] < pivot:
            border +=1
            array[i], array[border] = array[border], array[i]
            
    array[lo], array[border] = array[border], array[lo] # exchange border with pivoit

    return border



In [39]:

    
# from grokking algorithms page no.65
def quick_sort2(array):
    if len(array) < 2:
        return array
    
    pivot = array[0]
     
    less = [v for v in array[1:] if v <=pivot]
    greater = [v for v in array[1:] if v > pivot]
    
    return quick_sort2(less) + [pivot] + quick_sort2(greater)



In [40]:

    
alist = [54,26,93,17,77,31,20, 44,55,20]
blist = quick_sort2(alist)
print("before: ",alist)
print("after : ",blist)









    



before:  [54, 26, 93, 17, 77, 31, 20, 44, 55, 20]
after :  [17, 20, 20, 26, 31, 44, 54, 55, 77, 93]

Quick sort with dual pivot



In [41]:

    
def quick_sort_dual_pivot(a):
    _quick_sort_dual_pivot(a, 0, len(a) - 1)
    return a

def _quick_sort_dual_pivot(a, lo, hi):

    if lo >= hi:
        return


    if a[lo] > a[hi]:
        a[lo], a[hi] = a[hi], a[lo]

    pivot1 = a[lo]
    pivot2 = a[hi]

    if (pivot1 == pivot2):
        while pivot1 == pivot2 and lo < hi:
            lo +=1
            pivot1 = a[lo]



    l = lo + 1
    h = hi - 1
    i = lo + 1

    while i <= h:
        if a[i] < pivot1:
            a[i], a[l] = a[l], a[i]
            i += 1
            l += 1
        elif a[i] > pivot2:
            a[i], a[h] = a[h], a[i]
            h -= 1
        else:
            i += 1
    l -= 1
    h += 1

    a[lo], a[l] = a[l], a[lo]
    a[hi], a[h] = a[h], a[hi]


    _quick_sort_dual_pivot(a, lo, l-1)
    _quick_sort_dual_pivot(a, l+1, h-1)
    _quick_sort_dual_pivot(a, h+1, hi)



In [43]:

    
alist = [54,26,99,93,17,77,31,20, 44,55,20]
quick_sort_dual_pivot(alist)
print(alist)









    



[17, 20, 20, 26, 31, 44, 54, 55, 77, 93, 99]

3-way quick sort

In 3 Way QuickSort, an array arr[l..r] is divided in 3 parts:
a) arr[l..i] elements less than pivot.
b) arr[i+1..j-1] elements equal to pivot.
c) arr[j..r] elements greater than pivot.



In [44]:

    
def quick_sort_3way(a):
    _quick_sort_3way(a, 0, len(a) - 1)
    return a

def _quick_sort_3way(a, lo, hi):

    if lo >= hi:
        return

    l = lo
    h = hi
    i = l + 1
    pivot = a[lo]

    while i <= h:
        if a[i] < pivot:
            a[i], a[l] = a[l], a[i]
            i += 1
            l += 1
        elif a[i] > pivot:
            a[i], a[h] = a[h], a[i]
            h -= 1
        else:
            i += 1

    _quick_sort_3way(a, lo, l-1)
    _quick_sort_3way(a, h+1, hi)



In [ ]: