In this post, I will be explaining about the people’s favorite sorting algorithm – Quick sort

Quick sort can be done in two ways.

**Divide and conquer**: Algorithms that solve (conquer) problems by dividing them into smaller sub-problems until the problem is so small that it is trivially solved.**In-place**: In place sorting algorithms don’t require additional temporary space to store elements as they sort; they use the space originally occupied by the elements.

The steps are:

- Pick an element, called a pivot, from the list.
- Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
- Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values.

The base case of the recursion are lists of size zero or one, which never need to be sorted.

## Example: In-place algorithm

### Code

# /usr/bin/python # A program to do quick sort using separate list def quick_sort(inp): ''' Quick sort function ''' lesser = [] greater = [] if len(inp) <= 1: return inp for i in inp[1:]: # 0th element in the list is always the pivot element if i < inp[0]: lesser.append(i) else: greater.append(i) return quick_sort(lesser) + inp[0:1] + quick_sort(greater) if __name__ =="__main__": '''Main function''' inp =[] s = int(raw_input('How many elements would you like to enter: ')) for x in range(s): inp.append(int(raw_input('Enter element #' + `x+1` + ': '))) quick_sort(inp)

Input list:

9 8 3 7 5

[9, 8, 3, 7, 5] [8, 3, 7, 5] [9] [3, 7, 5] [8] [9] [3] [7, 5] [8] [9] [3] [5] [7] [8] [9]

Output list:

3 5 7 8 9

## Example: Divide and conquer

### Code

# /usr/bin/python # A program to do quick sort using inplace algo def partition(inp, start, end): ''' A function which does partition ''' pivot = inp[end] bottom = start - 1 top = end done = 0 while not done: while not done: bottom = bottom + 1 if bottom == top: done = 1 break if inp[bottom] > pivot: inp[top] = inp[bottom] break while not done: top = top - 1 if top == bottom: done = 1 break if inp[top] < pivot: inp[bottom] = inp[top] break inp[top] = pivot return top def quick_sort(inp, start, end): ''' Quick sort function ''' if start < end: split = partition (inp, start, end) quick_sort(inp, start, split - 1) quick_sort(inp, split + 1, end) else: return if __name__ == "__main__": ''' Main function ''' inp = [] s = int(raw_input('How many elements would you like to enter: ')) for x in range(s): inp.append(int(raw_input('Enter element #' + `x+1` + ': '))) start = 0 end = len(inp) - 1 quick_sort(inp, start, end) import string print string.join(map(str, inp))

Input list:

9 8 3 7 5

[9, 8, 3, 7, 5] Pivot = 9 [5, 8, 3, 7, [9] Pivot = 5 [3, 8, 5, 7] [9] Pivot = 5 [3] [5] [8, 7] [9] Pivot = 3 [3] [5] [8, 7] [9] Pivot = 8 [3] [5] [7] [8] [9] Pivot = 7

Sorted list:

3 5 7 8 9

The partition routine examines every item in the array at most once, so it is clearly **O(n)**

Usually, the partition routine will divide the problem into two roughly equal sized partitions. We know that we can divide n items in half logn times. This makes quicksort a **O(nlogn)** algorithm.

In worst case, i.e when the list is already sorted, it becomes **O(n^2)**

Advertisements