GRE Practice Test Q 52 - Sort Run Time wrt Input Ordering

[nonevent99]

Of the following sorting algorithms, which has a running time that is LEAST dependent on the initial ordering of the input?

(a) Insertion Sort
(b) Quick Sort
(c) Merge Sort
(d) Selection Sort
(e) Shell Sort



Insertion sort is O(n) best case, O(n^2) worst case.
Quick sort is O(n lg n) best case, O(n^2) worst case.
Merge sort is O(n lg n) best case, O(n lg n) worst case.
Selection sort is O(n^2) best case, O(n^2) worst case.
Shell sort is at least as good as O(n^1.25) best case, O(n^1.5) worst case.

So best[merge] = worst[merge] and best[selection] = worst[selection]. Why aren't they equally good answers?

[Laks]

Hey there... selection does depend on the ordering of the input does it not???

Cheers'
Laks

Nothing endures but change

[The_Wonderful_Vipul]

Hey ,

the thing is that take 2 cases : 1, where the input is sorted and the other where it is the worst case .

Which of the algos' running time varies the least between the two cases i.e. doesn't depend if the input is sorted in any way or not./

Vipul/

[jobel]

The answer is selection sort because it ALWAYS runs the same, regardless of input. Look at the code, for sorting integers:

void
selection( int *items, int length )
{
for ( int I = 0; I < length - 1; ++i )
{

int low = i;
for ( int j = i+1; j < length; ++j )
{
if ( items[ j ] < items[ low ] ) low = j;
}

int tmp = items[ low ];
items[ low ] = items[ I ];
items[ I ] = tmp;
}
}

You can see the number of operations is independent of the order of the initial ordering. It first searches items 1..n for the smallest, puts it in slot 0, then searches 2..n, puts it in slot 1, etc.

[nonevent99]

That's very interesting, because ETS's answer key claims that the answer is merge sort (c)

How can this be?

[vik]

you guys are right. I have an idea but it's kinda extreme:
assume an input where all values are identical. Obviously, it's already sorted.
The selection sort with a tiny improvement can run O(n) on this input, while merge sort still runs its O(n log n).

The improvement - remember the last element of the sorted part of the input. Inside the selection run, stop if you find an equal element.

What do you think?

[The_Wonderful_Vipul]

now look guyz,

the answer merge sort is indeed correct.

suppose you use insertion sort. if the array is already sorted, you dont have to shift any elements and it runs in O(n) time. however, if the array is in descending order, you have to shift for each element and the complexity is O(n^2).

consider merge sort. it is a divide n conquer technique and it keeps on dividing the input into smaller sets of elements until only one element in each set remains. it doesn't matter if the input was sorted o not because the number of operations performed would be the same. Divide into n sets and merge them.

pls assk if you hv any doubts.
hth,
Vipul.

[nonevent99]

Originally posted by vik

you guys are right. I have an idea but it's kinda extreme:
assume an input where all values are identical. Obviously, it's already sorted.
The selection sort with a tiny improvement can run O(n) on this input, while merge sort still runs its O(n log n).

The improvement - remember the last element of the sorted part of the input. Inside the selection run, stop if you find an equal element.

What do you think?

That seems like a reasonable improvement, though I don't remember ever seeing it in a textbook. (I have seen a roughly equivalent enhancement to bubble.)