How QuickSort works

Quicksort is a sorting method according to the principle "divide and conquer" with an effort in best case $O(n Log(n))$ in avg case $O(n Log(n))$ and in worst case $O(n^2)$

The Quicksort procedure is to select an element from an unsorted list as a pivot element. This is selected either at the beginning, end or center. The list is then divided at the pivot element and all elements that are smaller than the pivot element are brought to the left side of the pivot in the list to be sorted and all elements that are larger are brought to the right side. Then a pivot is selected for both sublists and the process is repeated until the list is sorted. You can see the process again for clarification below on the graphic.

The selection of the pivot is one of the most important, because the selection can also have a negative effect on Quicksort.

Selecting the pivot at the beginning or end of the list So we would have a worst case $O(n^2)$, if the first or last element of the list is chosen as pivot and the list itself:

• The list is already sorted
• The list is sorted exactly the other way round
• All elements of the list are the same.

Selection of the pivot by three elements to determine the median. When selecting a pivot using the median method, a few worst cases are eliminated but still exist. The worst cases are:

• All elements of the list are equal.

void QuickSort(vector &arr, int low, int high)
{
    if(low < high)
    {
        int x = partition_qs(arr, low, high);
        QuickSort(arr, low, x - 1);
        QuickSort(arr, x + 1, high);
    }
}

If you look at the code, you can see that the QuickSort method is similar to Mergesort. The passing parameters are the list $arr$ that has to be sorted, the start position $low$ and the end position $high$. First of all it is checked if the end position is greater than the start position. If this is the case, then a sort is performed. First the partition index $x$ is selected with the method partition_qs and sorted internally. Then 2 recursive calls are made. The first call takes place before the partition index which must be sorted. The array $arr$ with the two positions $low$ and $x - 1$ is passed which ensures that everything from the $low$ to the partion index is sorted again. The same is the case with the second call, only that everything is sorted from the partition index to the $high$ position.

int partition_qs(vector &arr, int left, int right)
{
    median_qs(arr, left, right);
    int temp = arr[right];
    int i = left - 1;
    for(int j = left; j < right; j++)
    {
        if(arr[j] <= temp)
        {
            i++;
            swap(arr, i, j);
        }
    }

    swap(arr, i + 1, right);
    return i + 1;
}

If you look at the method partition_qs, you see that it gets three parameters from the method QuickSort. Once the list $arr$ and the $low$ and high positions which are now called left and right. This is for a better overview. First the median is determined as pivot element. In the further course of the code, the median is sorted according to the pivot element. After determining the median, the element in the list at the position right is stored in the variable temp for later. The element in temp is our pivot. Then a new index is calculated $left -1$, as index for the smaller element in the list.

Then, from the position left to right, each element arr[j] ($arr_j$) is compared with the pivot temp and shifted either to the left or to the right accordingly. The index $i$ is increased by 1 per swap to the left to go one to the right in the list. This process is repeated in the for loop until the position right is reached. After that, everything that did not apply in the previous loop is sorted to the right. The index $i$ is also the partition index only that it is incremented by 1 at the end of the method and returned.

void median_qs(vector &arr, int left, int right)
{
    int median = (left + right) / 2;
    if(arr[median] < arr[left])
    {
       	swap(arr, median, left);
    }
    
    if(arr[right] < arr[left])
    {
        swap(arr, right, left);
    }

    if(arr[right] > arr[median])
    {
        swap(arr, median, right);
    }

}

The method median_qs is used to determine the median as a pivot element. The method gets the list and the left and right position to determine the median. The median is always swapped to the right position. The index median is determined from the average left and right. Then it is checked if the element at the median index is smaller than the element at the left position. If this is the case, it is swapped so that the median element is at the left position. Then both cases are checked if the element at the left position is smaller than the element at the right position. And whether the element at the right position is larger than the one at the median position. In both cases the pivot element is to be found on the position right after a swap calculation.

void swap(vector &arr, int pos1, int pos2)
{
    int tmp = arr[pos1];
    arr[pos1] = arr[pos2];
    arr[pos2] = tmp;
}

The swap method is used to swap two elements from the list. The element at position 1 is cached in a temporary variable to perform a complete swap. The element at the 2nd position now moves to the first position and the cached element is inserted at the 2nd position.

info

Important things about Quicksort!

• Quicksort is almost in-place, since hardly any additional storage space is needed.
• The probability for the worst case can be kept low.
• Standard sorting method in Unix systems.
• Inefficient with already sorted lists.
• Unstable algorithm, but can be stabilized.