Question

Is quicksort a stable sorting algorithm? If yes, prove it, if not, give an example

Answer 1

Quick Sort is an Unstable sorting algorithm

Proof:

Stable Sorting algorithm is that maintains the relative position of element after sorting i.e. if we have following elements 1,9 8,8,9,2,4,5, we can represent as

a-1,b-9, c-8,d-8,e-9,f-2,g-4,h-5 the sorting order will be 1,2,4,5,8,8,9,9 which is clearly explained in the picture.

In the Stable sort elemets will be sorted and it also maintains order, in this example we can see 8 comes two times which is in the position c & d. In the stable sort the c comes before d even though the elements are same, Whereas in the Unstable sort order is not maintained, i.e., d comes before c.

why quick sort is unstable sorting ?

Let us take example 1,9 8,8,9,2,4,5 now we have to sort using quick sort.

first we will consider the pivotal element is last element i.e. 5

pivot=a[end]

now two indices i=start-1; j=start i.e. i=-1 and j=0 now from left of array keep seeing element if it is less then pivot i.e. 5 swap with left most element index by i and finally place the pivot element at position where all the element left to pivot is less then pivot and right greater. Now start

1,9 8,8,9,2,4,5

1<5 so swapping i=0,j=1

next 9,8,8,9 are not less 5 so no swapping so j will be 4. now next 2 <5 so swapping so not

1,2,8,8,9,9,4,5 i=1 and j=5 so now the 9 was before is swapped after 9 which was relative behind of first 9 so unstable again 4<5 so swapping 1,2,4,8,9,8,9,8,5

finally swap the pivot with i=3 so 1,2,4,5,8,9,8,9.

now see 8 and 9 are swapped with the later 8,9 which is relative order has changed.

Since the relative order is not followed, we can say that quick sort is UNSTABLE SORTING ALGORITHM.