Is Quick Sort a Stable Sorting Algorithm?

Quick sort is not a stable sorting algorithm. Stability in sorting algorithms means that if two elements have equal keys, their relative order is preserved in the sorted output. However, quick sort, in its standard implementation, does not guarantee this order because it can swap elements in a way that may change the relative positions of equal elements. While it is possible to implement a stable version of quick sort, this typically involves additional overhead and complexity which can negate some of the performance benefits of the standard quick sort algorithm.

Overview of Quick Sort and Stability

Quick sort is a divide-and-conquer sorting algorithm. It works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted using the same process until the entire array is sorted. A sorting algorithm is said to be stable if it preserves the relative order of records with equal keys. This means that if two elements have the same key, the order in which they appear in the sorted output will be the same as the order in which they appeared in the original input.

Why Quick Sort is Not Stable

Quick sort is not a stable sorting algorithm because the partitioning step of the algorithm can rearrange elements without guaranteeing the preservation of their original order. For example, consider the following input array:

[5 3 3 1 2]

If we choose the first element 5 as the pivot, the partitioning step will produce the following two sub-arrays:

[3 3 1 2]n[5]

The two elements with the key 3 will be placed in the left sub-array even though they appeared in the right order in the original input array.

Modifying Quick Sort for Stability

There are a few ways to make quick sort stable. One way is to use a different partitioning algorithm. Another way is to track the original order of the elements and use it to restore their order after the partitioning step. However, these modifications can add overhead to the algorithm, making it less efficient. In many cases, the benefits of quick sort's speed outweigh the drawbacks of its instability.

Examples of Instability in Quick Sort

Example 1

Input array:

[1 5 3 3 2]

Pivot:

5

Partitioning:

[1 3 3 2]n[5]

Recursive sorting:

[1 2 3 3]n[5]

Sorted output:

[1 2 3 3 5]

As you can see, the two elements with the key 3 are now in reverse order even though they were in the right order in the original input array.

Example 2

Input array:

[4 5 1 1 2]

Pivot:

5

Partitioning:

[4 1 1 2]n[5]

Recursive sorting:

[1 1 2 4]n[5]

Sorted output:

[1 1 2 4 5]

Again, the two elements with the key 1 are in reverse order in the sorted output.

When to Use Quick Sort vs. Stable Sorting Algorithms

While quick sort is not a stable sorting algorithm, it is still one of the most widely used sorting algorithms due to its efficiency. In most cases, the benefits of quick sort's speed outweigh the drawbacks of its instability. However, in some cases, it is important to use a stable sorting algorithm. For example, if you are sorting a list of database records, you may want to preserve the original order of the records so that you can easily identify which records have changed. However, in many cases, quick sort's efficiency is more important than its stability.