Python Tutorial

# Python Program for Quick Sort

## What is quick sort ?

• Quick sort is one of the divide-and-conquer algorithm.
• Quick sort is to sort an array array[0], array[1],....array[n] by picking some element in the array as pivot element around which to rearrange the elements in the array in order to get sorted elements.
• Quick sort reduces the space complexity and removes the use of the auxiliary array that is used in merge sort.
• Use random pivot instead of first array element as pivot element to reduces the time complexity.

## Quick Sort Algorithm

• Pick the pivot element in random which can be first element also in the array.
• Move all the elements in left side of pivot element which are less than pivot element.
• Move all the elements in right side of pivot element which are greater than pivot element.
• Partition array elements which are less than pivot element and repeat the process 1 to 3 till all sub array elements in sorted order.
• Partition array elements which are greater than or equal to pivot element and repeat the process 1 to 3 till all sub array elements in sorted order.

## Quick Sorting Time complexity

Quick sorting time complexity is O(NlogN), here N is the number of elements in the list. worst case time complexity of this algorithm is O(N^2).

## Quick Sort Python Program

```#!/usr/bin/python

def swap(list_vals, index1, index2):
temp = list_vals[index1];
list_vals[index1] = list_vals[index2];
list_vals[index2] = temp;

def partition_by_pivot(list_vals, start_index, end_index):
i = start_index + 1;
# First element as pivot element.
pivot_element = list_vals[start_index];

for j in range(start_index + 1, end_index+1):
# Arranges the list elements which are less than pivot
# on one side and which are greater that on other side.
if (list_vals[j] < pivot_element):
swap(list_vals, i, j);
i += 1;

# swaps pivot element in correct position
swap(list_vals, start_index, i-1);
# returns the updated pivot element position
return i-1;

def quick_sort(list_vals, start_index, end_index):
if (start_index < end_index):
# position of pivot element
pivot_element_position = partition_by_pivot(list_vals, start_index, end_index);
quick_sort(list_vals, start_index, pivot_element_position -1);
quick_sort (list_vals, pivot_element_position+1 , end_index);

if __name__ == "__main__":
list_vals = [30, 10, 20, 70, 60, 80, 50, 40];
print("Collection before sorting: %s" % str(list_vals));
quick_sort(list_vals, 0, len(list_vals)-1);
print("Sorted list elements: %s" % str(list_vals));
```
Output:
```\$ python quick_sort.py
Collection before sorting: [30, 10, 20, 70, 60, 80, 50, 40]
Sorted list elements: [10, 20, 30, 40, 50, 60, 70, 80]
```

Python Tutorial