Basic Algorithms — Quicksort. Sorting an array with randomly selected…
Basic Algorithms — Quicksort

Sorting an array with randomly selected pivots

I introduced a sorting algorithm called Merge-Sort in a previous article and continue writing about another sorting algorithm, Quicksort, in this post. The expected cost of Quicksort is Θ(nlgn), while the worst case that costs Θ(n²) would materialize only at a probability of 2/n!. I will show later in the performance comparison that the constant hidden in Θ notation is lower in Quicksort thus the algorithm outperforms Merge-Sort whose cost is same Θ(nlgn).

Photo by Andrew Buchanan on Unsplash

Insertion Sort

Insertion-Sort is a brute-force algorithm that compares all the pairs in an array to sort it. This is how people commonly sort their hands in porker or other card games. The cost is Θ(n²).

def insertion_sort(array):

for j in range(1, len(array)):

key = array[j]

i = j - 1

while i >= 0 and array[i] > key:

array[i+1] = array[i]

i -= 1

array[i+1] = key

return array

Merge-Sort

We discussed Merge-Sort algorithm as one of the basic divide-conquer algorithms in the previous article. This time, we’ll use a simpler version because we’re dealing with just one-dimensional arrays.

def merge_sort(array):



length = len(array)



if length == 1:

return array



elif length == 2:

if array[0] > array[1]:

return np.array([array[1], array[0]])

else:

return array



elif length > 2:

array_l = array[:length//2]

array_r = array[length//2:]

array_l_sorted = merge_sort(array_l)

array_r_sorted = merge_sort(array_r) l = 0

r = 0



l_length = len(array_l)

r_length = len(array_r)



sorted_list = []



for i in range(length):

if r == r_length:

sorted_list.append(array_l_sorted[l])

l += 1 elif l == l_length:

sorted_list.append(array_r_sorted[r])

r += 1



elif array_l_sorted[l] > array_r_sorted[r]:

sorted_list.append(array_r_sorted[r])

r += 1



elif array_l_sorted[l] < array_r_sorted[r]:

sorted_list.append(array_l_sorted[l])

l += 1



return np.array(sorted_list)

Quicksort

The Quicksort algorithm picks a pivot randomly from an array and divides the original array into two subarrays: a subarray that consists of numbers smaller than the pivot and the other with larger numbers. By doing that recursively, we will eventually obtain the sorted array.

Here is a simple example, and you have an array of eight numbers. Randomly selected pivot turned to be six in this case. Then you assign numbers smaller than six into the left subarray and larger ones to the right.

The next step is applying the algorithm recursively to the subarrays; random pivots are now two in the left (smaller) subarray and seven in the right (larger). By doing that recursively, you will end up with a sorted array.

def quick_sort(array):

length = len(array)



if length <= 1:

return array



if length == 2:

if array[0] > array[1]:

return [array[1], array[0]]

else:

return array



else:

pivot = np.random.randint(0, length)

small = []

large = []



for element in array:

if element < array[pivot]:

small.append(element)

elif element > array[pivot]:

large.append(element)



if not small:

return [array[pivot]] + quick_sort(large)

elif not large:

return quick_sort(small) + [array[pivot]]

else:

return (quick_sort(small)

+ [array[pivot]]

+ quick_sort(large))

In the worst case, you may pick random pivots in ascending or descending order (e.g. one to eight, or eight to one in the example above) and the cost would be Θ(n²). That is, however, ignorable as it takes place only at a probability of 2/n! (once in 21,600 times in the example). So we consider the expected cost of the algorithm instead.

The cost of sorting algorithms depends on how many pairs they compare. Let’s think about the probability at which two numbers in an array, Zi and Zj (i<j), are compared. Zi and Zj are directly compared only when either Zi or Zj is selected as a pivot, and are never directly compared if any number between Zi and Zj is picked as a pivot (Zi and Zj are assigned to separate subarrays). When a pivot is selected outside of Zi and Zj, it does not affect the probability because Zi and Zj stay in the same subarray. Thus, the probability that Zi and Zj are directly compared is 2/(j - i+1).

The expected number of comparison is, therefore, the sum of 2/(j - i+1) for all pairs of numbers in the array.

With a few deformations as shown on the left, we find that the number converges into familiar Θ(nlgn). We can say the expected cost of Quicksort algorithm is Θ(nlgn).

In-Place Quicksort

We can write Quicksort algorithm in-place, which means that the algorithm stores only constant amount of data outside of the original array. In-place algorithms offer an advantage of less memory-usage. Here is the code of in-place Quicksort algorithm.

def quick_sort_in_place(array, start, end):

if start < end:



if start + 1 == end:

if array[start] > array[end]:

larger = array[start]

array[start] = array[end]

array[end] = larger



pivot = np.random.randint(start, end+1)

pivot_value = array[pivot]



array[pivot] = array[-1]

array[-1] = pivot_value



border = start - 1



for i in range(start, end):

if array[i] < pivot_value:

border += 1

border_value = array[i]

array[i] = array[border]

array[border] = border_value

array[-1] = array[border+1]

array[border+1] = pivot_value



array = quick_sort_in_place(array, start, border+1)

array = quick_sort_in_place(array, border+2, end) return array

Performance Check

Now we compare the performance of Insertion-Sort (Θ(n²)), Merge-Sort(Θ(nlgn)), and Quicksort(expected Θ(nlgn)).

Source: Author’s Calculation

Obviously Merge-Sort and Quicksort have an edge over Insertion-Sort, with their slopes flatter than that of Insertion-Sort. With a lower constant hidden in Θ(nlgn) notation, Quicksort algorithm is faster than Merge-Sort, while Quicksort-in-place takes as much time as Merge-Sort (i.e. in-place advantage is cancelled out by some other costs).

As Quicksort algorithm contains some randomness, it is useful to look at the distribution of costs over trials. Here is the histogram of costs for Quicksort and Merge-Sort algorithms processing 2¹⁰ numbers with 10,000 trials. It is noted that Merge-Sort is also prone to randomness as shown in the figure. Both of the distributions are tilted toward the cheapest end (left).

Source: Author’s calculation

One thing we learn from Quicksort algorithm is that randomness can be our friend. Quicksort processes a large set of numbers much more efficiently than other sorting algorithms. With proper knowledge of probability theory, we may be able to write less costly algorithms.
['Keita Miyaki']
['Divide And Conquer', 'Python', 'Quicksort', 'Algorithms', 'Data Science']