Recall that a sorting algorithm is said to be stable if the original ordering fo
ID: 3605212 • Letter: R
Question
Recall that a sorting algorithm is said to be stable if the original ordering for duplicate keys is preserved. We can make any algorithm stable if we alter the input keys so that (potentially) duplicate key values are made unique in a way that the first occurrence of the original duplicate value is less than the second occurrence, which in turn is less than the third, and so on. In the worst case, it is possible that all n input records have the same key value. Give an algorithm to modify the key values such that every modified key value is unique, the resulting key values give the same sort order as the original keys, the result is stable (in that the duplicate original key values remain in their original order), and the process of altering the keys is done in linear time using only a constant amount of additional space per key.
Note: This is a long question but the answer is short.
Explanation / Answer
One way of doing this is to append a positional component with each key. The number of possitional digits must be same for all the keys. For example, if there are 100 keys the positional components will be 001, 002, 003 ...,100.
Example keys : 30, 10, 2, 48, 2, 3, 90
After adding position keys we have, 301, 102, 23, 484, 24, 35, 906 (positional components are in bold and it ensures unique keys generated)
After sorting these modified keys we have 23, 24, 35, 102, 301, 484, 906
Observe that the relative order of the keys are unchange while it preserves the stability of 2 in terms of 23 and 24
Note that the append of positional component can be done in O(n) i.e. linear.
First of all we need to find number of digits to encode n number of keys. The algorithm is
int getNoOfDigits(int n){
int digit = 0;
while(n != 0)
{
n /= 10;
digit++;
}
return digit;
}
The algorithm to concatenate a key with a position having no of digit to encode a key being digit:
int concatenate(int key, int position, int digit) {
for(int i=1;i<=digit;i++){
key = key*10;
}
return key+position;
}
Finally, the algorithm to modify the array of n number of keys:
void modifyKeys(int key[], ine size){
int digit = getNoOfDigits(size);
for(int i=0;i<size;i++)
key[i]=concatenate(key[i],i,digit);
}
NB: Hope it helps to het your answer. Please let me know if anything else is needed. Please provide feedback to help you better.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.