Algorithms and Data Structures

# QuickSort

One of the most popular sorting algorithms is QuickSort. It’s a divide-and-conquer algorithm that iteratively picks a pivot element from the array, splits the array into 3 parts - elements that are smaller, equal, and larger than the pivot element and repeats that process until getting to a point where the whole array is sorted.
So, on each iteration:
1. We pick a pivot element from the array
1. Move the smaller elements to the left part of the pivot
1. Move the larger elements to the right part of the pivot
1. Collect all the elements equal to the pivot in the middle
1. Repeat this process on both the left and the right parts
def quicksort(a):
if len(a) <= 1:
return a
pivot = a[len(a) // 2]
left = [x for x in a if x < pivot]
middle = [x for x in a if x == pivot]
right = [x for x in a if x > pivot]
return quicksort(left) + middle + quicksort(right)
This implementation of QuickSort uses additional arrays for the left, middle, and right parts. We can make it in place by modifying the code to use indices and rearranging the elements right in the array.
def quicksort(a, start, end):
if start >= end:                    # No elements to sort
return

pivot = a[start]                    # Choose a pivot
l, r = start + 1, end               # Sort a[start+1 ... end]
while l <= r:                       # While there are elements left in the range
if a[l] < pivot:                # if a[l] < pivot => leave a[i] untouched
l += 1                      # Increase the left pointer
else:                           # otherwise move a[l] to the end
a[l], a[r] = a[r], a[l]     # Swap a[l] and a[r] -> move to the end
r -= 1                      # Reduce the right pointer

a[start], a[r] = a[r], a[start]     # Swap pivot with a[r]
quicksort(a, start, r - 1)          # Sort a[start ... r-1]
quicksort(a, r + 1, end)            # Sort a[r+1 ... end]
You might have noticed that the choice of the pivot was different in these two implementations. The QuickSort algorithm does not have a restriction on picking a pivot. There are several ways to do that. Here are a few ideas on how to pick a pivot:
1. First element: a[start] as demonstrated in the second implementation
1. Last element: a[end]
1. Middle element: a[(start + end + 1) // 2]
1. Random element: Pick any element in a[start ... end]
1. Median element: Pick the median of the current segment. This makes sure that each split results in equal left and right parts but requires a more sophisticated implementation.

Let’s simulate the algorithm on several arrays:
[4, 1, -1, 0, 2, 8]
1. quicksort(a, 0, 5) → pivot = 4 [4, 1, -1, 0, 2, 8]
1. l=1, r=5a[l] = 1 < pivot ⇒ l += 1
2. l=2, r=5a[l] = -1 < pivot ⇒ l += 1
3. l=3, r=5a[l] = 0 < pivot ⇒ l += 1
4. l=4, r=5a[l] = 2 < pivot ⇒ l += 1
5. l=5, r=5a[l] = 8 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
6. swap a[start] and a[r][2, 1, -1, 0, 4, 8]
7. quicksort(a, 0, 3) and quicksort(a, 5, 5)
1. quicksort(a, 0, 3) → pivot = 2 [2, 1, -1, 0, 4, 8]
1. l=1, r=3a[l] = 1 < pivot ⇒ l += 1
2. l=2, r=3a[l] = -1 < pivot ⇒ l += 1
3. l=3, r=3a[l] = 0 < pivot ⇒ l += 1
4. swap a[start] and a[r][0, 1, -1, 2, 4, 8]
5. quicksort(a, 0, 2) and quicksort(a, 3, 3)
1. quicksort(a, 0, 2) → pivot = 0 [0, 1, -1, 2, 4, 8]
1. l=1, r=2a[l] = 1 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [0, -1, 1, 2, 4, 8]
2. l=1, r=1a[l] = -1 < pivot ⇒ l += 1
3. swap a[start] and a[r][-1, 0, 1, 2, 4, 8]
4. quicksort(a, 0, 0) and quicksort(a, 2, 2)
1. [-1, 0, 1, 2, 4, 8]
[4, 5, 3, 4, 4, 8, 4, 1, 2, 9, 7, 4, -1]
1. quicksort(a, 0, 12) → pivot = 4 [4, 5, 3, 4, 4, 8, 4, 1, 2, 9, 7, 4, -1]
1. l=1, r=12a[l] = 5 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, 5, 3, 4, 4, 8, 4, 1, 2, 9, 7, 4, -1]
2. l=1, r=11a[l] = -1 < pivot ⇒ l += 1
3. l=2, r=11a[l] = 3 < pivot ⇒ l += 1
4. l=3, r=11a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, -1, 3, 4, 4, 8, 4, 1, 2, 9, 7, 4, 5]
5. l=3, r=10a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, -1, 3, 4, 4, 8, 4, 1, 2, 9, 7, 4, 5]
6. l=3, r=9a[l] = 7 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, -1, 3, 7, 4, 8, 4, 1, 2, 9, 4, 4, 5]
7. l=3, r=8a[l] = 9 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, -1, 3, 9, 4, 8, 4, 1, 2, 7, 4, 4, 5]
8. l=3, r=7a[l] = 2 < pivot ⇒ l += 1
9. l=4, r=7a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, -1, 3, 2, 4, 8, 4, 1, 9, 7, 4, 4, 5]
10. l=4, r=6a[l] = 1 < pivot ⇒ l += 1
11. l=5, r=6a[l] = 8 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, -1, 3, 2, 1, 8, 4, 4, 9, 7, 4, 4, 5]
12. l=5, r=5a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, -1, 3, 2, 1, 4, 8, 4, 9, 7, 4, 4, 5]
13. swap a[start] and a[r][1, -1, 3, 2, 4, 4, 8, 4, 9, 7, 4, 4, 5]
14. quicksort(a, 0, 3) and quicksort(a, 5, 12)
1. quicksort(a, 0, 3) → pivot = 1 [1, -1, 3, 2, 4, 4, 8, 4, 9, 7, 4, 4, 5]
1. l=1, r=3a[l] = -1 < pivot ⇒ l += 1
2. l=2, r=3a[l] = 3 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [1, -1, 3, 2, 4, 4, 8, 4, 9, 7, 4, 4, 5]
3. l=2, r=2a[l] = 2 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [1, -1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
4. swap a[start] and a[r][-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
5. quicksort(a, 0, 0) and quicksort(a, 2, 3)
1. quicksort(a, 2, 3) → pivot = 2 [-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
1. l=3, r=3a[l] = 3 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
2. swap a[start] and a[r][-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
3. quicksort(a, 2, 1) and quicksort(a, 3, 3)
1. quicksort(a, 5, 12) → pivot = 4 [-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
1. l=6, r=12a[l] = 8 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
2. l=6, r=11a[l] = 5 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 5, 4, 9, 7, 4, 4, 8]
3. l=6, r=10a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 4, 9, 7, 4, 5, 8]
4. l=6, r=9a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 4, 9, 7, 4, 5, 8]
5. l=6, r=8a[l] = 7 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 7, 4, 9, 4, 4, 5, 8]
6. l=6, r=7a[l] = 9 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 9, 4, 7, 4, 4, 5, 8]
7. l=6, r=6a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 9, 7, 4, 4, 5, 8]
8. swap a[start] and a[r][-1, 1, 2, 3, 4, 4, 4, 9, 7, 4, 4, 5, 8]
9. quicksort(a, 5, 4) and quicksort(a, 6, 12)
1. quicksort(a, 6, 12) → pivot = 4 [-1, 1, 2, 3, 4, 4, 4, 9, 7, 4, 4, 5, 8]
1. l=7, r=12a[l] = 9 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 9, 7, 4, 4, 5, 8]
2. l=7, r=11a[l] = 8 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 8, 7, 4, 4, 5, 9]
3. l=7, r=10a[l] = 5 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 5, 7, 4, 4, 8, 9]
4. l=7, r=9a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 4, 7, 4, 5, 8, 9]
5. l=7, r=8a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 4, 7, 4, 5, 8, 9]
6. l=7, r=7a[l] = 7 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 7, 4, 4, 5, 8, 9]
7. swap a[start] and a[r][-1, 1, 2, 3, 4, 4, 4, 7, 4, 4, 5, 8, 9]
8. quicksort(a, 6, 5) and quicksort(a, 7, 12)
1. quicksort(a, 7, 12) → pivot = 7 [-1, 1, 2, 3, 4, 4, 4, 7, 4, 4, 5, 8, 9]
1. l=8, r=12a[l] = 4 < pivot ⇒ l += 1
2. l=9, r=12a[l] = 4 < pivot ⇒ l += 1
3. l=10, r=12a[l] = 5 < pivot ⇒ l += 1
4. l=11, r=12a[l] = 8 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 7, 4, 4, 5, 8, 9]
5. l=11, r=11a[l] = 9 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 7, 4, 4, 5, 9, 8]
6. swap a[start] and a[r][-1, 1, 2, 3, 4, 4, 4, 5, 4, 4, 7, 9, 8]
7. quicksort(a, 7, 9) and quicksort(a, 11, 12)
1. quicksort(a, 7, 9) → pivot = 5 [-1, 1, 2, 3, 4, 4, 4, 5, 4, 4, 7, 9, 8]
1. l=8, r=9a[l] = 4 < pivot ⇒ l += 1
2. l=9, r=9a[l] = 4 < pivot ⇒ l += 1
3. swap a[start] and a[r][-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 9, 8]
4. quicksort(a, 7, 8) and quicksort(a, 10, 9)
1. quicksort(a, 7, 8) → pivot = 4 [-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 9, 8]
1. l=8, r=8a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 9, 8]
2. swap a[start] and a[r][-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 9, 8]
3. quicksort(a, 7, 6) and quicksort(a, 8, 8)
1. quicksort(a, 11, 12) → pivot = 9 [-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 9, 8]
1. l=12, r=12a[l] = 8 < pivot ⇒ l += 1
2. swap a[start] and a[r][-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 8, 9]
3. quicksort(a, 11, 11) and quicksort(a, 13, 12)
1. [-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 8, 9]
The average running time of the QuickSort algorithm is . Yet, depending on the choice of the pivot, it can result in quadratic performance.
🤔 Can you think of an example where the algorithm would perform operations if we always pick the start as the pivot?

### Challenge

Given a list of n integers and q pivots, you are asked to move all the elements smaller than the pivot to the left, and all the elements larger than the pivot to the right of the pivot element, while keeping all the equal ones together (next to each other, to the right of smaller numbers, and to the left of larger ones).

#### Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000).
The next line contains a list of n space-separated integers ().
The third line contains a single integer q (1 ≤ q ≤ 10).
The next line contains a list of n space-separated integers (1 ≤ ≤ n) representing the index of the pivot element.

#### Output

For each of the q pivots, the program should print the resulting array after performing the rearrangement. If there are multiple possible answers, the program should print any of those.

#### Examples

 Input Output 7 1 8 0 3 4 -2 4 3 4 2 5 1 0 -2 3 4 4 8 -2 0 1 3 4 4 8 -2 0 1 3 4 4 8

#### Constraints

Time limit: 0.2 seconds

Memory limit: 512 MB

Output limit: 10 MB