QuickSort - Summary

https://jordanspencerwu.github.io/randomized-quick-sort/

  public static void RandomizedQuickSort(int[] array, int startIndex, int endIndex) {

    if (startIndex < endIndex) {

      int pivot = randomizedPartition(array, startIndex, endIndex);

      RandomizedQuickSort(array, startIndex, pivot - 1);

      RandomizedQuickSort(array, pivot + 1, endIndex);

    }

  }

  public static int randomizedPartition(int[] array, int startIndex, int endIndex) {

    int randomEndIndex = randomNumberBetween(startIndex, endIndex);

    swap(array, endIndex, randomEndIndex);

    return partition(array, startIndex, endIndex);

  }

  public static int randomNumberBetween(int startNumber, int endNumber) {

    return (int) Math.floor(Math.random() * (endNumber - startNumber + 1) + startNumber);

  }

  public static int partition(int[] array, int startIndex, int endIndex) {

    int pivotValue = array[endIndex];

    int pivotIndex = startIndex;

    for (int j = startIndex; j < endIndex; j++) {

      if (array[j] <= pivotValue) {

        swap(array, pivotIndex, j);

        pivotIndex = pivotIndex + 1;

      }

    }

    swap(array, pivotIndex, endIndex);

    return pivotIndex;

  }

https://www.geeksforgeeks.org/quick-sort/

    /* This function takes last element as pivot,

       places the pivot element at its correct

       position in sorted array, and places all

       smaller (smaller than pivot) to left of

       pivot and all greater elements to right

       of pivot */

    int partition(int arr[], int low, int high)

    {

        int pivot = arr[high]; 

        int i = (low-1); // index of smaller element

        for (int j=low; j<high; j++)

        {

            // If current element is smaller than or

            // equal to pivot

            if (arr[j] <= pivot)

            {

                i++;

  

                // swap arr[i] and arr[j]

                int temp = arr[i];

                arr[i] = arr[j];

                arr[j] = temp;

            }

        }

  

        // swap arr[i+1] and arr[high] (or pivot)

        int temp = arr[i+1];

        arr[i+1] = arr[high];

        arr[high] = temp;

  

        return i+1;

    }

  

  

    /* The main function that implements QuickSort()

      arr[] --> Array to be sorted,

      low  --> Starting index,

      high  --> Ending index */

    void sort(int arr[], int low, int high)

    {

        if (low < high)

        {

            /* pi is partitioning index, arr[pi] is 

              now at right place */

            int pi = partition(arr, low, high);

  

            // Recursively sort elements before

            // partition and after partition

            sort(arr, low, pi-1);

            sort(arr, pi+1, high);

        }

    }

https://www.geeksforgeeks.org/stable-quicksort/

A sorting algorithm is said to be stable if it maintains the relative order of records in the case of equality of keys.

Input : (1, 5), (3, 2) (1, 2) (5, 4) (6, 4)
We need to sort key-value pairs in the increasing order of keys of first digit
There are two possible solution for the two pairs where the key is same i.e. (1, 5) and (1, 2) as shown below:
OUTPUT1: (1, 5), (1, 2), (3, 2), (5, 4), (6, 4)
OUTPUT2: (1, 2), (1, 5), (3, 2), (5, 4), (6, 4)
A stable algorithm produces first output. You can see that (1, 5) comes before (1, 2) in the sorted order, which was the original order i.e. in the given input, (1, 5) comes before (1, 2).

Second output can only be produced by an unstable algorithm. You can see that in the second output, the (1, 2) comes before (1, 5) which was not the case in the original input.

Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, etc. And some sorting algorithms are not, like Heap Sort, Quick Sort, etc.
QuickSort is an unstable algorithm because we do swapping of elements according to pivot’s position (without considering their original positions).

Quicksort can be stable but it typically isn’t implemented that way. Making it stable either requires order N storage (as in a naive implementation) or a bit of extra logic for an in-place version.
In below implementation, we use extra space. The idea is to make two separate lists:
1) First list contains items smaller than pivot.
2) Second list contains items greater than pivot.

def quickSort(ar):

       

    # Base case

    if len(ar) <= 1:

        return ar

  

    # Let us choose middle element a pivot

    else:

        mid = len(ar)//2

        pivot = ar[mid]

  

        # key element is used to break the array

        # into 2 halves according to their values

        smaller,greater = [],[]

   

        # Put greater elements in greater list,

        # smaller elements in smaller list. Also,

        # compare positions to decide where to put.

        for indx, val in enumerate(ar):

            if indx != mid:

                if val < pivot:

                    smaller.append(val)

                elif val > pivot:

                    greater.append(val)

  

                # If value is same, then considering

                # position to decide the list.

                else:

                    if i < mid:

                        smaller.append(val)

                    else:

                        greater.append(val)

        return quickSort(smaller)+[pivot]+quickSort(greater)