# Quick sort program in Python

In this post, you will learn about **quick sort** and how to write a quick sort program using the **Python** programming language.

**Quick sort** is widely used sorting algorithm, developed by **C.A.R**.

In **quick sort**, it first selects one element called a **pivot**. After that, it rearranges the elements in the array in such a way that all the elements less than the pivot element appear before the pivot and all the elements greater than the pivot appear after the pivot. After this, partitioning the pivot is in the final position.

Quick sort is the fastest algorithm and is the best choice. It is faster than other algorithms like bubble sort, selection sort, and insertion sort. But this can be complex on the flip side.

## Quick Sort Example

These are the quick sorting techniques.

We choose the first element as a pivot. So set loc at **0 index**, left at **0 index** and right at **5th index**.

Now scan from right to left until **a[loc] < a[right]**, then decrease the value of right.

Since **a[loc] > a[right]**, interchange the two values and set **loc = right**.

Now scan from left to right until **a[loc] > a[left]**, then increment the value of left.

Since **a[loc] < a[left]**, interchange the values and set **loc = left**.

Since from right to left, since **a[loc] < a[right]**, decrease the value of right.

Start scanning from left to right. Since **a[loc] > a[left]**, increment the value of left.

Since **a[loc] > a[right]**, interchange the two values and set **loc = right**.

## Complexity of Quick sort

Suppose **n** is the number of elements in an array.

```
Best Time Complexity - O(n log(n))
Worst Time Complexity - O(n
```^{2})

## Quick sort Algorithm

```
QUICKSORT (array A, start, end)
{
if (start < end)
{
p = partition(A, start, end)
QUICKSORT (A, start, p - 1)
QUICKSORT (A, p + 1, end)
}
}
```

## Quick sort program in Python

```
# divide function
def partition(arr,low,high):
i = ( low-1 )
# pivot element
pivot = arr[high]
for j in range(low , high):
# If current element is smaller
if arr[j] <= pivot:
# increment
i = i+1
arr[i],arr[j] = arr[j],arr[i]
arr[i+1],arr[high] = arr[high],arr[i+1]
return ( i+1 )
# Implementing quick sort
def quick_sort(arr,low,high):
if low < high:
# index
p = partition(arr,low,high)
# sort the partitions
quick_sort(arr, low, p-1)
quick_sort(arr, p+1, high)
# main
array = [5,2,3,7,8,1,6,4]
n = len(array)
quick_sort(array,0,n-1)
print ("Sorted array is:")
for i in range(n):
print (array[i],end=" ")
```

**Output of the above code:**

```
Sorted array is:
1 2 3 4 5 6 7 8
```

### Related Articles

**Convert Python list to numpy array**

Convert string to list Python

Python program to list even and odd numbers of a list

Python loop through list

Sort list in descending order Python

Convert array to list Python

Python take screenshot of specific window

Web scraping Python BeautifulSoup

Check if two strings are anagrams Python

Python program to add two numbers

Print new line python

Python for loop index

Convert List to Dataframe Python

numpy random choice

Dictionary inside list python

Check if list is empty Python

Python raise keyword

Python program to get the largest number from a list

Python program to map two lists into a dictionary

Convert string to list Python

Python program to list even and odd numbers of a list

Python loop through list

Sort list in descending order Python

Convert array to list Python

Python take screenshot of specific window

Web scraping Python BeautifulSoup

Check if two strings are anagrams Python

Python program to add two numbers

Print new line python

Python for loop index

Convert List to Dataframe Python

numpy random choice

Dictionary inside list python

Check if list is empty Python

Python raise keyword

Python program to get the largest number from a list

Python program to map two lists into a dictionary