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.)

[dwarf]

Referring to the question 52 GR 9629 (As given in the first post of this thread),

The answer given in the test book (merge sort) to this question directly contradicts wikipedia's articles on selection sort and merge sort.

Check the Selection Sort article on Wikipedia,
["It can be seen as an advantage for some real-time applications that selection sort will perform identically regardless of the order of the array,..."]

Even if we analyse the algorithms, observe that algorithm MERGE used in merge sort that sorts two sorted lists makes between 'n' and '2n - 1' comparisons for merging two sorted lists of size 'n' each.

Try merging 1 2 3 4 and 5 6 7 8.
Now try merging 1 3 5 7 and 2 4 6 8.

This results in a best case recurrence
T(n) = 2T(n/2) + n/2

and a worst case recurrence
T(n) = 2T(n/2) + n - 1

Although the solutions to the recurrences will result in the same complexity class, they will differ by a constant factor if solved exactly by iteration.

As for selection sort, it makes the exactly the same number of comparisons no matter whatever the input (Reason: two for loops).

If the running time of an algorithm is dominated by the number of comparisons it makes, then the answer to this question is clearly SELECTION SORT. (This is how we decide the big-Oh complexity of almost all sorting algorithms, isn't it?)

ETS's answer is MERGE SORT.

Any comments? <No variants of these algorithms please>

[Enigma211]

I think ETS's answer is based one the fact that best, avg and worst case scenarios on multiple input for a merge sort is O(nlogn).

I agree that strictly based on comparisons, selection sort does n^2 comparisons regardless of the input. But the hidden constant cost required to swap the numbers could make the difference in the best and worst case scenario. The cost difference is n^2 vs n^2+n . The additional cost n for n swaps.

Thoughts ?