The Gateway to Computer Science Excellence

0 votes

Stable sorting algorithms maintain the relative order of records with equal keys (*i.e.* values). That is, a sorting algorithm is *stable* if whenever there are two records *R* and *S* with the same key and with *R* appearing before *S* in the original list, *R* will appear before *S* in the sorted list.

**Stable sorting algorithms** : Insertion sort, Merge sort, Counting sort, Bubble sort

**Unstable sorting algorithms** : Quick sort, Selection sort, Heap sort

I did not found any standard algorithm to make a non stable algorithm stable, so I think we need to write our own algorithm for this. For maintaining the relative order we need to keep track of the position of element, following is one way to do so :-

Let us assume we need to sort a given array A[i]

**step 1)** Create an array say B[i] of a new data structure which will store pair of elements VALUE= A[i] and POSITION= i.

**step 2)** Sort the array B[i] using any non stable sorting algorithm, by comparing VALUE, if we find VALUE to be equal, then compare and sort those elements using POSITION therefore maintaining the relative order of the elements.

**step 3)** After sorting store the array elements(VALUE) of B[i] to A[i].

**step 4)** Exit

In worst case using the above algorithm we have to make n extra comparison therefore in worst case it will take **O(n) additional time **and because of B[i] it takes** O(n) additional space.**

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,378 answers

198,523 comments

105,317 users