QuickSort — Coding Interview Preparation — HackerRank

  1. We write a method called partition method to split an array into two sub-arrays, one containing smaller elements and one containing larger elements than a given number called pivot.
  2. When partition is called on an array, two parts of the array get ‘sorted’ with respect to each other. If partition is then called on each sub-array, the array will now be split into four parts. This process can be repeated until the sub-arrays are small. Notice that when partition is called on just one of the numbers, they end up being sorted.

Explanation
This is a diagram of Quicksort operating on the sample array:

Code:

def quicksort(ar):
if len(ar) <= 1:
return ar
lt, eq, rt = [], [], []
# assuming there that ar[0] is the pivot for item in ar:
if item < ar[0]:
lt.append(item)
elif item > ar[0]:
rt.append(item)
else:
eq.append(item)
sub = quicksort(lt) + eq + quicksort(rt) print(*sub)
return(sub)

n = input().strip().split()
ar = [int(x) for x in input().strip().split()]
quicksort(ar)

2. The previous version of Quicksort was easy to understand, but it was not optimal. It required copying the numbers into other arrays, which takes up space and time. To make things faster, one can create an “in-place” version of Quicksort, where the numbers are all sorted within the array itself.

Guideline
Instead of copying the array into multiple sub-arrays, use indices to keep track of the different sub-arrays. You can pass the indices to a modified partition method. The partition method should partition the sub-array and then return the index location where the pivot gets placed, so you can then call partition on each side of the pivot.

  • Partition the left side and then the right side of the sub-array.
  • Print out the whole array at the end of every partitioning method.
  • An array of length or less will be considered sorted, and there is no need to sort or to print them.

Since you cannot just create new sub-arrays for the elements, partition method will need to use another trick to keep track of which elements are greater and which are lower than the pivot.

The In-place Trick

  • Greater elements should remain where they are.
  • At the end of the partitioning method, the pivot should be swapped with the first element of the right partition, consisting of all larger elements, of the sub-array.
  • To ensure that you don't swap a small element with another small element, use an index to keep track of the small elements that have already been swapped into their "place".

Sample Input

7
1 3 9 8 2 7 5

Sample Output

1 3 2 5 9 7 8
1 2 3 5 9 7 8
1 2 3 5 7 8 9

Explanation
5 is initally selected as the pivot, and the array is partitioned as shown in the diagram. The left side is partitioned next with 2 as the pivot. Finally, the right side is partitioned with 8 as the pivot. The entire array is now sorted.

Solution : IN PLACE INSORT

def getPartitionIdx(A, lo, hi):    # TRACKER IS THE INDEX OF THE LAST ELEMENT SMALLER 
# THAN PIVOT, WE ASSUME ALL ELEMENTS TO THE LEFT OF TRACKER
# ARE SMALLER THAN PIVOT, IF NOT WE SWAP THEM WITH TRACKER POSITION.
pivot_index_tracker=lo-1 pivot = A[hi] # BROWSE THROUGH THE LIST FROM lo to hi-1, SUCH THAT WE CAN FIND
# AN INDEX WHICH HAS ALL ELEMENTS TO THE LEFT SMLLAR THAN PIVOT
# AND ALL ELEMENTS TO THE RIGHT GREATER THAN PIVOT
for j in range(lo, hi): if A[j] <= pivot: pivot_index_tracker+= 1
A[pivot_index_tracker], A[j] = A[j], A[pivot_index_tracker]
# PIVOT SHOULD MOVE TO THE TRACKER POSITION A[pivot_index_tracker+1], A[hi] = A[hi], A[pivot_index_tracker+1] print(' '.join(map(str, A))) #RETURN THE POSITION OF PIVOT return (pivot_index_tracker+1)

# DIVIDE AND CONQUER AT THE POSITION OF PIVOT IN THE ARRAY
def inplaceQuickSort(A, lo, hi):
if(lo < hi):
p=getPartitionIdx(A, lo, hi)
inplaceQuickSort(A, lo, p-1)
inplaceQuickSort(A, p+1, hi)

if __name__ == '__main__':
N = int(input())
inplaceQuickSort(list(map(int,input().split())), 0, N-1)

ANALYSIS:

QUESTON: IN WHAT CASE IS THE RUN TIME EQUAL TO INSERTION SORT?

  • However, Quicksort will usually pick a pivot that is mid-range, and it will partition the array into two parts.
  • Let’s assume Partition is lucky and it always picks the median element as the pivot. What will be the running time in such a case?

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store