Quick sort

Quick sort#

Is sorting algorithm that is based on recursive procedure which divides an array into two parts - less than some pivot element and greater than some pivot element, and applies itself to each of the parts.

import random
from random import randint

from warnings import warn

Partition#

The core part of the algorithm is a procedure that allows elements less than the pivot to be pre-positioned to the left of the array, and values greater than the pivot to be pre-positioned to the right of the array.

For simplicity, I will use left to denote a subset of elements such that it is smaller than pivot, and right to denote a subset of elements such that it is larger than pivot.

def partition(arr, low, high, pivot):
    '''
    Function shuffle elements in place array
    so that all elements lower than
    pivot have less indexes than elements
    whose value is greater than pivot.

    Parameters
    ----------
    arr : list
        array, which elements need to be shuffled;
    low : int
        left border index that will be 
        considered by funtion;
    high : int
        right border index that will be
        consedered by funtion;
    pivot : number
        such a number that all elements of the array 
        less will be collected in the left part of 
        the array, and all elements of the array 
        more will be collected in the right part of 
        the array.

    Returns
    ----------
    out : int
        index of the half-next element among those 
        that are less than pivot
    '''
    i = low
    for j in range(low, high+1):
        if arr[j] <= pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i+=1
    return i-1

Now let’s see how this works in the most general case. So in the following cell there is an input array and partition is applied from the i-th to the len-i-th elements, with pivot 10. And before execution funtion under consideration is printed results:

  • Elements that were in the input array before low don’t change their order;

  • Elements that were in the input array after `high’ don’t change their order either;

  • Elements between the low and high indices are split into two arrays:

    • less or equal than pivot;

    • more than pivot.

random.seed(10)
arr_size = 20
arr = [randint(0, 20) for i in range(arr_size)]

low = 3
high = arr_size - 3

ind = partition(arr, low, high, 10)
print("Input array", arr, end="\n\n")
print(
    "before left:", arr[:low], "\n",
    "left:", arr[low:ind+1], "\n",
    "right:", arr[ind+1:high], "\n",
    "after right:", arr[high:], "\n",
    sep = ""
)

Input array [18, 1, 13, 0, 6, 8, 5, 1, 10, 2, 7, 18, 14, 16, 15, 15, 15, 20, 11, 1]

before left:[18, 1, 13]
left:[0, 6, 8, 5, 1, 10, 2, 7]
right:[18, 14, 16, 15, 15, 15]
after right:[20, 11, 1]

Also let’s check some boundary cases:

  • Left contains only one lement:

arr = [3,2,1,5,4]
print("Input array", arr)
ind = partition(arr, 0, 4, 1)
print("Result:", arr, f"with separation in {ind}-th position.")

Input array [3, 2, 1, 5, 4]
Result: [1, 2, 3, 5, 4] with separation in 0-th position.

  • Left is empty;

arr = [3,2,1,5,4]
print("Input array", arr)
ind = partition(arr, 0, 4, 0)
print("Result:", arr, f"with separation in {ind}-th position.")

Input array [3, 2, 1, 5, 4]
Result: [3, 2, 1, 5, 4] with separation in -1-th position.

  • Right contains only one element;

arr = [3,2,1,5,4]
print("Input array", arr)
ind = partition(arr, 0, 4, 4)
print("Result:", arr, f"with separation in {ind}-th position.")

Input array [3, 2, 1, 5, 4]
Result: [3, 2, 1, 4, 5] with separation in 3-th position.

  • Right is empty;

arr = [3,2,1,5,4]
print("Input array", arr)
ind = partition(arr, 0, 4, 10)
print("Result:", arr, f"with separation in {ind}-th position.")

Input array [3, 2, 1, 5, 4]
Result: [3, 2, 1, 5, 4] with separation in 4-th position.

Classic sort#

Here is the basic realisation of this algorithm, which is a key to algorithms for different tasks based on the same idea.

def quick_sort(arr, low=0, high=None):
    '''
    Sort in ascending order in place.
    This is a recursive function that only 
    replaces elements in the elements only 
    in the specified range.
    
    Parameters
    ----------
    arr : list
        the object will be sorted by the 
        passed reference;
    low : int
        is the lower index of the subarray 
        under consideration;
    high : int
        is the highes index of the subarry
        under consideration.
    '''
    if len(arr)<=1:
        return arr
    if not high: high=len(arr)-1
    
    ind = partition(arr, low, high, arr[high])
    if ind-1>low:quick_sort(arr, low=low, high=ind-1)
    if ind+1<high: quick_sort(arr, low=ind+1, high=high)

Now let’s check how it works:

random.seed(20)
arr_size = 20
arr = [randint(0, 20) for i in range(arr_size)]
print("Input array:", arr)
quick_sort(arr)
print("Sorted array:", arr)

Input array: [4, 8, 20, 3, 10, 18, 5, 0, 13, 13, 2, 3, 4, 10, 15, 18, 14, 13, 6, 6]
Sorted array: [0, 2, 3, 3, 4, 4, 5, 6, 6, 8, 10, 10, 13, 13, 13, 14, 15, 18, 18, 20]

And finally, a little “stress test” - we’ll compare the results of the function quick_sort and the built-in function sorted.

arr_size = 20

for i in range(1000):
    arr = [randint(0, 20) for i in range(arr_size)]
    classic_res = sorted(arr)
    quick_sort(arr)
    if classic_res != arr:
        warn("there is some problems with your realisation!!")