A sorting method is stable if equal keys remain in the same relative order in the sorted sequence as they were in the original sequence. (That is, a sort is stable if for any i < j such that initially E[i] = E[j], the sort moves E[i] to E[k] and E[j] to E[m] for some k and m such that k < m.) Which of the following algorithms are stable? For each that is not stable, give the relative order of two equal keys is changed.

 

a) Insertion Sort.

b)Maxsort (Exercise 4.1).

c)Bubble Sort (Exercise 4.2).

d)Quicksort.

e)Heapsort.

f)Mergesort.

g)Shellsort.

h)Radix Sort.

below I have solved the required Question in step by step fashion.

Step-by-step explanation

Any non-stable algorithm can be transformed to a stable one. We simply need to take a few steps to achieve this in a particular manner.

Some algorithms, such as bubble sort, insertion sort, merge sort, and count sort, are known to be stable.

Merge and Insertion type, for example, have some sort of blue print or formula associated with their contrast.

E[j] the element comes before E[i] only if E[j] < E[i]

where i and j and index of array

E is the name of array.

Apart from comparison algorithms , there also are algorithms that maintains stability.It is finished by ensuring that array which kinded in reverse order in order that parts of the array would be in relevant position.

And some miscellaneous algorithms like base sort , the steadiness of those algorithms depends on another sort which ought to be stable.

The algorithms like heap sort , fast sort may be created into stable algorithms .We will treat adjusting the position of the element s into thought .But this can consume an very little overtime for adjusting the positions of the weather .So , it'll possibly takes letter of the alphabet of n time to try to to stable.

stability of algorithms :

with respect to the time complexity :

Count sort , Merge sort ,Heap sort , quick sort , radix sort , selection sort,insertion sort, bubble sort:

But if we don't think about time , then obviously the bubble, insertion ,selection ,merge sort and Counting sorting algorithms are the best.