Category: Sorting

Flashcard: Quicksort

In this flashcard, we are going to look at the Quicksort algorithm.

What is Quicksort?

  • Quicksort is an efficient, recursive, divide-and-conquer sorting algorithm.

How does the Quicksort algorithm work?

  • First, the algorithm selects a pivot element.
  • Next, the algorithm sorts the two sub-arrays that lay to the left and the right from the pivot element. The algorithm iterates through the elements of the sub-arrays and places them either to the left or the right from the pivot depending on whether they are greater or less than the pivot element.
  • Finally, the sub-arrays are sorted similarly (recursion).

What is the time complexity of the Quicksort algorithm?

  • Best O (n log n)
  • Average O (n log n)
  • Worst O (n^2)

What is the space complexity of the Quicksort algorithm?

  • O (n log n)

Is Quicksort a stable algorithm?

  • No, Quicksort belongs to the group of unstable sorting algorithms.

What does a “stable sorting algorithm” mean?

  • Stable sorting algorithms preserve the order of input elements.

Provide an implementation of the Quicksort algorithm in C#.

void quicksort(ref int[] array, int firstIndex, int lastIndex)
{
    if (array == null || array.Length < 2 || firstIndex == lastIndex) return;

    // select pivot
    int pivot = lastIndex;

    // sort against pivot
    for (int i = firstIndex; i < pivot; i++)
    {
        if (array[i] >= array[pivot])
        {
            int tmp = array[i];
            array[i] = array[pivot - 1];
            array[pivot - 1] = array[pivot];
            array[pivot] = tmp;
            pivot--;
            i--;
        }
    }

    // sort left side
    if (pivot > firstIndex)
        quicksort(ref array, firstIndex, pivot - 1);

    // sort right side
    if (pivot < lastIndex)
        quicksort(ref array, pivot + 1, lastIndex);

}

The implementation is pretty simple. We work with the original array without copying during the sorting. Therefore, we need two pointers (firstIndex and lastIndex) that indicate which part of the array we are currently sorting.

At the very beginning, we check the validity of the input. If the check fails, then we return without doing anything.

In the next step, we define the pivot element by simply selecting the last one. Subsequently, we sort the left sub-array against the pivot element. If an element is less than the pivot element, then we keep it where it is. Otherwise, we put it right behind the pivot.

Finally, we sort the sub-arrays that lay to the left and the right from the pivot element using the same method.

%d