Quick Sort explained - python coding

Quick Sort explained - python coding


Published at - Sep 14, 2021

Quicksort is an in-place sorting algorithm. Developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be somewhat faster than merge sort and about two or three times faster than heapsort.

Some important points

  • Based on the Divide and conquer strategy
  • Not using additional storage.

Time & Space complexity

Worst complexity: n^2
Average complexity: n*log(n)
Best complexity: n*log(n)

Algorithm

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p - 1)
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo
    for j := lo to hi do
        if A[j] < pivot then
            swap A[i] with A[j]
            i := i + 1
    swap A[i] with A[hi]
    return i

Python program for implementation of QuickSort

def partition(a,l,h):
    pivot = a[l]
    i = l
    j=h
    while i<j:
        while a[i]<=pivot and i<h: i+=1
        while a[j]>pivot and j>l: j-=1
        if i<j: a[i],a[j]=a[j],a[i]
        
    a[j],a[l]=a[l],a[j]
    return j

def quickSort(a,l,h):
    if l < h:
        pi = partition(a, l, h)
        quickSort(a, l, pi - 1)
        quickSort(a, pi + 1, h)
        
#driver Code        
a =[10, 7, 8, 9, 1, 5 ]
quickSort(a, 0, len(a) - 1)
print(a)
#Output: [1, 5, 7, 8, 9, 10]

All programs will print sorted array as output.

I hope you like this article, to learn more about articles like this you can click here. Thank you for reading.

Thank You! 



About author

Harendra
Harendra Kanojiya

Hi I'm Harendra Kumar Kanojiya. Currently I am FSD (Full-stack developer) and I have expertise with Angular ,PHP, Node JS, Laravel, Codeigniter and front end. Done few live projects and portfolio work in above.



Related Posts -

Follow Us

Follow us on facebook Click Here

Facebook QR
Scan from mobile
Join our telegram channel Click Here
Telegram QR
Scan from mobile