search
Log In
1 vote
477 views
Show that any comparison based sorting algorithm can be made stable without increasing its complexity beyond a constant factor.
in Algorithms 477 views
0
Don't swap when numbers are equal ...is nt that the idea ?

2 Answers

1 vote

Any given sorting algo which is not stable can be modified to be stable. There can be sorting algo specific ways to make it stable, but in general, any comparison based sorting algorithm which is not stable by nature can be modified to be stable by changing the key comparison operation so that the comparison of two keys considers position as a factor for objects with equal keys.

Key comparison operation is always satisfies transitivity property. So, complexity of stable sort shouldnot increase more than a constant factor.

http://www.geeksforgeeks.org/stability-in-sorting-algorithms/

https://en.wikipedia.org/wiki/Sorting_algorithm#Stability

https://en.wikipedia.org/wiki/Comparison_sort

0
Plz correct me if wrong

Related questions

0 votes
1 answer
1
0 votes
2 answers
2
314 views
Which of the following sorting techniques have best time complexity, if complexity is measured in terms of number of comparison? A Insertion sort B Selection sort C Merge sort D QuickSort
asked Dec 8, 2017 in Algorithms rahul sharma 5 314 views
1 vote
1 answer
3
886 views
What is the ascending wise order of sorting algorithms which takes least time and least space to sort the elements?
asked Sep 12, 2017 in Programming LavTheRawkstar 886 views
2 votes
1 answer
4
470 views
// func() is any constant root function for (int i = n; i > 0; i = func(i)) { // some O(1) expressions or statements } "In this case, i takes values n, n1/k, (n1/k)1/k = n1/k2, n1/k3, , n1/klogk(log(n)), so ... the above statement? How do we calculate that there are logk(log(n)) iterations? Source: http://www.geeksforgeeks.org/time-complexity-loop-loop-variable-expands-shrinks-exponentially/
asked Nov 7, 2017 in Algorithms Narasimhan 470 views
...