Question

Which of the following sorting algorithms are stable: insertion sort, selection sort, merge sort and quick sort? Give a simple scheme that makes any sorting algorithm stable. How much additional time and space does your scheme entail?

Answer 1

Question 1

Answer 1. Sorting algorithum is consider to be stable when  number are in same order and input and output array is consider to be sorted

In the above given example the Insertion and Merge sort are consider as stable

As we know that :-

A[i] comes after A[j]

A[j] > A[i] (in this case i and j are indices )

if ( i < j )

if ( A[i] == A[j] ) ( order is preserved )

For suppose if we have two element such as B and C in wich ( B == c ) then for sure two element B and c will be in same ored in unsorted array .

-->> To make any sorting algorithum stable we need to do following.

to make any sorting algorithum we needd to modified the given algo As we know that their are many ways in which we can make sorting algo to be stable are

Step 1 :- Change the key

Step 2:- Then the position of two key are defined as factor of same key

Algo to deffine that given sorting algo is stable

if we have an array A[ ]

and ( i < j )

and A[i] == A[j] ( pie(i) < pie(j) ) where pie is the called as sorting permutation .