Implementing QuickSort using Python

What is quicksort and how it works ?

QuickSort is an very efficient sorting algorithm based on divide and conquer rule. Although quicksort is not considered stable but it is very fast and space complexity is also very less. It has 2 phases :

- The partition phase
- The sort phase

Let's Understand it with an example

suppose we are given an array A [List in case of python] to sort using
quicksort

A = [ 10, 5, 3, 15, 24, 17, 7 ]

Step 1 : Choose a pivot

There are mainly 4 ways of choosing a pivot which are as follows:

- Choose the last element of the array as pivot.
- Choose the first element of the array as pivot.
- Choose any random element of the array as pivot.
- Choose the median of the array as pivot.

STEP 2 : Partition on basis of pivot

Pivot = A[4] = 15

A = [ 10, 5, 3,** 15**, 24, 17, 7 ]

Now check all the the elements and put elements less than pivot on it
left and elements more than pivot on its right as shown below :

Suppose we are starting from last element

[ 10, 5, 3, 7, 24, 17, 15 ]

Highlighted Elements are swapped.

[ 10, 5, 3, 7, 15, 17, 24 ]

Now we Got 2 sub-arrays and pivot on its correct position

sub-array 1 = [ 10, 5, 3, 7 ]

Sub-array2 = [ 17, 24 ]

Step-3 : Perform it Recursively

Now Perform the same operation recursively on the subarrays.

**This Sorting mechanism is known as QuickSort.**

Performing Quick Sort using Python

In this , We are provided with an Unsorted String of characters which also includes a repeating character.

` ````
#!/bin/python
# this code cares about an element which may be reoccuring.
def partition(ar):
pivotloc = 0
pivot = ar[0]
left = []
right = []
middle = [pivot]
for i in range(0,len(ar)):
if(ar[i]
```pivot):
right.append(ar[i])
elif(ar[i]==pivot):
if(i != pivotloc):
middle.append(ar[i])
if(len(left)>1):
for i in range(0,len(left)):
print left[i],
print ''
left = partition(left)
if(len(right)>1):
for i in range(0,len(right)):
print right[i],
print ''
right = partition(right)
final = left + middle + right
return final
ar = ['r','i','s','h','a','b','h']
final = partition(ar)
for i in range(0,len(final)):
print final[i],

Summary

- What is quicksort and how it works ?
- Let's Understand it with an example :
- Choose a pivot
- Partition on basis of pivot
- Perform it Recursively

- Performing Quick Sort using Python