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 :

  1. The partition phase
  2. The sort phase
In quicksort , we pick an element as PIVOT. And perform partitioning of the remaining elements around the pivot and call this partitioning procedure recursively to sort the partitions. It is a very good example of divide and conquer. Here we are dividing a bigger problem into smaller ones and then we conquer it by solving the smaller problems.

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:

  1. Choose the last element of the array as pivot.
  2. Choose the first element of the array as pivot.
  3. Choose any random element of the array as pivot.
  4. Choose the median of the array as pivot.
So , let's choose the pivot using the median of the array for our example.

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 :
    1. Choose a pivot
    2. Partition on basis of pivot
    3. Perform it Recursively
  • Performing Quick Sort using Python