changing a black box array sorting algorithm to be a stable algorithm

Question

let Sort1 be a given algorithm and A a given array. Sort1 run in time of f(n). I need to create a new stable algorithm, Sort2, using Sort1 that will run in time of f(n)+O(n).

I have a solution my friend suggested:

Creating a clone array B of A.
Changing every number in B to a couple (number,index) where number is the number (the element), and index is it's index (location in A).
every element in B points to it's corresponding element in A.
run Sort1 on A.
for every sequence of same numbers in sorted A, run Sort1 on the flash that will sort the flash by the index of every element.

is his solution right? do you have any suggestions? thanks!

I'm sorry, but what's a flash?

B. D
– B. D

2011-06-30 16:08:00 +00:00
Commented Jun 30, 2011 at 16:08 — B. D
– B. D, Commented Jun 30, 2011 at 16:08

Jerry Coffin · Accepted Answer · 2011-06-30 15:11:34Z

5

Make your copy, but then create a new comparison function that uses the original data as the primary key (probably even using the original comparison function to do the comparison), and if that's equal, have it do a secondary comparison based on the original position in the array.

answered Jun 30, 2011 at 15:11

Jerry Coffin

494k83 gold badges656 silver badges1.2k bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

changing a black box array sorting algorithm to be a stable algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related