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 :
suppose we are given an array A [List in case of python] to sort using
quicksort
A = [    10,  5,  3,  15,  24,  17,  7   ]
There are mainly 4 ways of choosing a pivot which are as follows:
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 ]
Now Perform the same operation recursively on the subarrays.
This Sorting mechanism is known as QuickSort.
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],