Quick sort - Not a stable sort

Question

Stable sort talks about equal keys NOT getting past each other, after sorting

Consider duplicate key 4 at array index 8 & 9, in the below sequence,

a = [5 20 19 18 17 8 4 5 4 4] where pivot = 0, i = 1, j = 9

Partition logic says,

i pointer moves left to right. Move i as long as a[i] value is ≤ to a[pivot]. swap(a[i], a[j])

j pointer moves right to left. Move j as long as a[j] value is ≥ to a[pivot]. swap(a[i], a[j])

After following this procedure two times,

a = [5 4 19 18 17 8 4 5 4 20] Swap done at i = 1 & j = 9.

a = [5 4 19 18 17 8 4 5 4 20] Stops at i = 2 & j = 8

a = [5 4 4 18 17 8 4 5 19 20] Swap done at i = 2 & j = 8

My understanding is, as duplicate key 4 lost their order after two swaps, Quick sort is not stable sort.

Question:

As per my understanding, Is this the reason for Quick sort not being stable? If yes, Do we have any alternative partition approach to maintain the order of key 4 in the above example?

Answer 1

There's nothing in the definition of Quicksort per se that makes it either stable or unstable. It can be either.

The most common implementation of Quicksort on arrays involves partitioning via swaps between a pair of pointers, one progressing from end to beginning and the other from beginning to end. This does produce an unstable Quicksort.

While this method of partitioning is certainly common, it's not a requirement for the algorithm to be a Quicksort. It's just a method that's simple and common when applying Quicksort to an array.

On the other hand, consider doing a quicksort on a singly linked list. In this case, you typically do the partitioning by creating two separate linked lists, one containing those smaller than the pivot value, the other containing those larger than the pivot value. Since you always traverse the list from beginning to end (not many other reasonable choices with a singly linked list). As long as you add each element to the end of the sub-list, the sub-lists you create contain equal keys in their original order. Thus, the result is a stable sort. On the other hand, if you don't care about stability, you can splice elements to the beginnings of the sub-lists (slightly easy to do with constant complexity). in this case, the sort will (again) be unstable.

The actual mechanics of partitioning a linked list are pretty trivial, as long as you don't get too fancy in choosing the partition.

node *list1 = dummy_node1;
node *add1 = list1;
node *list2 = dummy_node2;
node *add2 = list2;

T pivot = input->data; // easiest pivot value to choose

for (node *current = input; current != nullptr; current = current->next)
    if (current->data < pivot) {
        add1->next = current;
        add1 = add1 -> next;
    }
    else {
        add2->next = current;
        add2 = add2->next;
    }
add1->next = nullptr;
add2->next = nullptr;