The Gateway to Computer Science Excellence
0 votes
36 views
Which of the following sorting algorithms are stable: insertion sort, merge sort, heapsort, and quicksort? Give a simple scheme that makes any sorting algorithm stable. How much additional time and space does your scheme entail?
in Algorithms by Boss (41.9k points) | 36 views

2 Answers

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.

by (473 points)
edited by
0 votes

simple & elegant

by Active (1.3k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,492 answers
195,439 comments
100,707 users