Sorting algorithm: QuickSort

General Information

The very pragmatically and aptly named sorting algorithm QuickSort is one of the most time-efficient algorithms in its category. Its strength lies in the concept of divide and conquer.

Process

  1. Initially, an element from the list to be sorted is selected as the so-called “pivot” (point of division). The choice of the pivot is crucial for efficiency, but it cannot be guaranteed to be optimal, as this would require knowledge of the actual order of elements. Over the decades, numerous approaches have been developed to determine the pivot intelligently. In the code below, the Lomuto Partitioning Algorithm is used because it is the easiest to implement.
  2. Subsequently, all values smaller than the pivot are moved to its left side, while the values that are larger are moved to its right side.
  3. Next, steps 1 and 2 are applied recursively to the left and right subgroups of values until only a single element remains in each restricted list.

The graphic below illustrates this process using a practical example.

Source: https://www.techiedelight.com/wp-content/uploads/Quicksort.png

As Code

The following lines of code describe Quick-sort in Java:

class QuickSort
{
    public static void main(String args[])
    {
        int array[] = {10, 7, 8, 9, 1, 5};

        QuickSort sorter = new QuickSort();
        sorter.sort(array, 0, array.length - 1);

        for (int i = 0; i < array.length; ++i) {
            System.out.print(array[i] + " ");
        }
    }

    int partition(int array[], int scopeStart, int scopeEnd)
    {
        int pivot = array[scopeEnd]; 
        int i = (scopeStart - 1);
        for (int j = scopeStart; j < scopeEnd; j++)
        {
            if (array[j] <= pivot)
            {
                i++;
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }

        int temp = array[i + 1];
        array[i + 1] = a[high];
        array[high] = temp;

        return i + 1;
    }

    void sort(int array[], int scopeStart, int scopeEnd)
    {
        if (scopeStart < scopeEnd)
        {
            int partitionIndex = partition(array, scopeStart, scopeEnd);

            sort(array, scopeStart, partitionIndex - 1);
            sort(array, partitionIndex + 1, scopeEnd);
        }
    }
}

Source: https://www.geeksforgeeks.org/java-program-for-quicksort/