# 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

## 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.

Thank You!

##### Harendra Kanojiya

Hello, I am Harendra Kumar Kanojiya - Owner of this website and a Fullstack web developer. I have expertise in full-stack web development using Angular, PHP, Node JS, Python, Laravel, Codeigniter and, Other web technologies. I also love to write blogs on the latest web technology to keep me and others updated. Thank you for reading the articles.

## Related Posts -

###### Bubble sort examples in pyt ...

In this lesson on python coding, we will talk about one of the fundamental ...

###### Hash table program in pytho ...

In this lesson on python coding, we will talk about one of the most fam...

###### Sequential Search or linear ...

In this lesson on python coding, we will talk about one of the fundamen...

###### Insertion sort examples in ...

In this lesson on python coding, we will talk about one of the Insertion So...

###### Merge sort explained - pyth ...

In computer science, merge sort is an efficient, general-purpose, and compa...