which sort is more independent of its input
David Eppstein
> I came across a question from the CS GRE test that
> asked which sort is Most independent of its input.
> a)quick sort b)insertion sort c)merge sort d)selection sort e)Shell's sort
What a stupid question.
Even if it made sense to teach all of these algorithms (the only ones I
cover in my algorithms class are a and c, unless you count heap sort as
a form of selection sort) none of them are in any way independent of
their input -- how could any useful program be?
Several of them have (or could easily be made to have) running times
that are nearly independent of the input, so that's not it either. And
anyway having a time that's independent of the input is only a useful
property if the time is fast, and several of these algorithms' times
aren't (which is why I don't teach them).
Are you sure that's exactly how it was phrased on the GRE?
I don't know about other departments, but we don't pay a lot of
attention to the GRE subject in our graduate admissions. The generals
are much more important...(not to mention transcripts and letters).
This sort of question might explain why.
--
David Eppstein UC Irvine Dept. of Information & Computer Science
epps...@ics.uci.edu http://www.ics.uci.edu/~eppstein/
Jakob Pagter
> The question is MOST independent. A quicksort with poor pivot will yield
> O(n^2) time. Insertion sort with everything already sorted is O(n) time.
> Merge sort always splits the list in half, so it seems faily independent
> of the inputs. Selection sort.. well, I think is even more because of the
> following code:
> for (i = 0 ; i<n; i++) {
> for (j = 0; j<n; j++) {
> compare and find smallest
> }
> swap (A[i], smallest);
> }
> Seems pretty O(n^2) to me no matter what the input is. Anyone know of
> a different version?
Tree Selection.
BTW, What's a GRE?
Cheers, Jakob
--
Jakob Pagter - pag...@brics.dk
<URL:http://www.brics.dk/~pagter/>
Chen Wang
asked which sort is Most independent of its input.
a)quick sort
b)insertion sort
c)merge sort
d)selection sort
e)Shell's sort
I picked d but the answer says c. After thinking
about it a bit I feel both answers are correct...
Unless there is a clever version of selection sort?
Anyone can help?
-Chen
--
--------------------------------------------------
The most incomprehensible thing about the universe
is that it is comprehensible. -A. Einstein
http://www.glue.umd.edu/~chenman
--------------------------------------------------
Nick Maclaren
In article <6uv360$b...@euclid.ics.uci.edu>, epps...@euclid.ics.uci.edu (David Eppstein) writes:
|> In <6uv1nl$9t5$1...@hecate.umd.edu> che...@Glue.umd.edu (Chen Wang) writes:
|> > asked which sort is Most independent of its input.
|> > a)quick sort b)insertion sort c)merge sort d)selection sort e)Shell's sort
|>
|>
|> Even if it made sense to teach all of these algorithms (the only ones I
|> cover in my algorithms class are a and c, unless you count heap sort as
|> a form of selection sort) none of them are in any way independent of
|> their input -- how could any useful program be?
|>
|> Several of them have (or could easily be made to have) running times
|> that are nearly independent of the input, so that's not it either. And
|> anyway having a time that's independent of the input is only a useful
|> property if the time is fast, and several of these algorithms' times
|> aren't (which is why I don't teach them).
Hmm. I am not sure that I am impressed by that, unless your class is
for non-specialists. There are good reasons to use (and teach) many
of the less obvious ones. For example, the 2^n*3^n Shell sort is
the FASTEST on many highly parallel computers (e.g. vector systems),
as each pass can be decomposed into independent operations.
And the ordinary Shell sort (done right) is usually the best sort for
when it has to be typed in from memory, or when code size is the
critical constraint. There are also circumstances where even bubble
sort can be the best sort for the purpose.
But I take your point that quicksort and merge sort are by far the
best sorts for libraries and, in general, the ones to use.
Regards,
Nick Maclaren,
University of Cambridge Computing Service,
New Museums Site, Pembroke Street, Cambridge CB2 3QG, England.
Email: nm...@cam.ac.uk
Tel.: +44 1223 334761 Fax: +44 1223 334679
Peter L. Montgomery
che...@Glue.umd.edu (Chen Wang) writes:
>David Eppstein (epps...@euclid.ics.uci.edu) wrote:
>: In <6uv1nl$9t5$1...@hecate.umd.edu> che...@Glue.umd.edu (Chen Wang) writes:
>: > I came across a question from the CS GRE test that
>: > asked which sort is Most independent of its input.
>: > a)quick sort b)insertion sort c)merge sort d)selection sort e)Shell's sort
>: What a stupid question.
>The question is MOST independent. A quicksort with poor pivot will yield
>O(n^2) time. Insertion sort with everything already sorted is O(n) time.
>Merge sort always splits the list in half, so it seems faily independent
>of the inputs. Selection sort.. well, I think is even more because of the
>following code:
> for (i = 0 ; i<n; i++) {
> for (j = 0; j<n; j++) {
> compare and find smallest
> }
> swap (A[i], smallest);
> }
>Seems pretty O(n^2) to me no matter what the input is. Anyone know of
>a different version?
There is no mention of time in `Most independent of its input'.
Do they mean a sort capable of sorting different data types equally well?
Radix sort (not a candidate) needs to know about the internal representation
of its key. Whether we can use the same code to sort integers and reals
depends more upon the programming language than the algorithm chosen.
If we are supposed to measure time, then a constant-time
sort will have comparable performance whatever the length of the input.
Alas, it's hard to sort n items without inspecting each item at least
once. On a sequential machine this is at least O(n) steps.
If we further fix the size of the input,
then Chen Wang's algorithm makes consistently many comparisons
(although his loop on j should start at j=i).
Modern RISC processors depend heavily upon good branch prediction.
Depending upon the order of the records,
the branch miss penalties will vary considerably --
an ordered input will lead to good prediction.
An architecture with a conditional move instruction may not
incur those penalties, but the GRE test answers make no
mention of this instruction.
I agree, this is a very poor question.
--
Peter-Lawren...@cwi.nl San Rafael, California
The bridge to the 21st century is being designed for the private autombile.
The bridge to the 22nd century will forbid private automobiles.
Louis Glassy
> I came across a question from the CS GRE test that
> asked which sort is Most independent of its input.
> a)quick sort b)insertion sort c)merge sort d)selection sort
> e)Shell's sort
[...]
An interesting question. Some more observations, some of which are
similar to yours:
- quicksort without extra work handles ordered- or nearly-ordered data
poorly (O(n^2)), and other data well (O(n lg n)).
(as you've already observed.)
- insertion sort handles ordered data very well (O(n)) and other
data poorly (O(n^2)). (as you've observed)
- merge sort seems to eat everything in n lg n time.
- selection sort seems to eat everything in n^2 time.
- shell's sort ... hmm. which one? Donald Shell's? Donald Knuth's?
Hibbard's increments? Sedgewick's increments? In general, shellsort
will handle ordered data well (O(n)) and other data less well (maybe
O(n^1.5) or better, depending on the increment sequence used).
So the two candidates you've picked (merge sort, selection sort) both
look reasonable. In a test situation, I'd have probably put down (d)
(selection sort). Here's one argument for why that would have been
the "wrong" answer- ignoring the *relative order* of the elements,
selection sort fares particularly well when the elements to be moved
are large, because each element only gets moved *once*. So merge
sort in some sense does "equally badly" (cost of moves-wise)
for any size of individual data elements, while selection sort is
optimal (cost of moves-wise) for large-sized data elements.
Just a thought.
-lou
Chen Wang
David Eppstein (epps...@euclid.ics.uci.edu) wrote:
: In <6uv1nl$9t5$1...@hecate.umd.edu> che...@Glue.umd.edu (Chen Wang) writes:
: > asked which sort is Most independent of its input.
: > a)quick sort b)insertion sort c)merge sort d)selection sort e)Shell's sort
: What a stupid question.
: Even if it made sense to teach all of these algorithms (the only ones I
: cover in my algorithms class are a and c, unless you count heap sort as
: a form of selection sort) none of them are in any way independent of
: their input -- how could any useful program be?
The question is MOST independent. A quicksort with poor pivot will yield
O(n^2) time. Insertion sort with everything already sorted is O(n) time.
Merge sort always splits the list in half, so it seems faily independent
of the inputs. Selection sort.. well, I think is even more because of the
following code:
for (i = 0 ; i<n; i++) {
for (j = 0; j<n; j++) {
compare and find smallest
}
swap (A[i], smallest);
}
Seems pretty O(n^2) to me no matter what the input is. Anyone know of
a different version?
: Several of them have (or could easily be made to have) running times
: that are nearly independent of the input, so that's not it either. And
: anyway having a time that's independent of the input is only a useful
: property if the time is fast, and several of these algorithms' times
: aren't (which is why I don't teach them).
: Are you sure that's exactly how it was phrased on the GRE?
Yes.
: I don't know about other departments, but we don't pay a lot of
: attention to the GRE subject in our graduate admissions. The generals
: are much more important...(not to mention transcripts and letters).
: This sort of question might explain why.
I find that really puzzling (but true in many CS departments). The general
GRE can be practiced to death and getting a high score on it IMHO does not
take too much ingeniuity. 1)verbal: memorize to death 2)math: insults a
to-be-grad student (in science) 3)analytical: practice and have fun.
The CS GRE on the other hand really tests a whole breathe of computer
material that makes me nervous about the Nov. test date. :-) To do well
on that (with ETS unwilling to publish that many past tests) means you had
to know some stuff.
Okay, enough about side discussions, someone please shed some light on
this problem.
-Chen
Justin Cormack
>
> David Eppstein (epps...@euclid.ics.uci.edu) wrote:
> : In <6uv1nl$9t5$1...@hecate.umd.edu> che...@Glue.umd.edu (Chen Wang) writes:
> : > I came across a question from the CS GRE test that
> : > asked which sort is Most independent of its input.
> : > a)quick sort b)insertion sort c)merge sort d)selection sort e)Shell's sort
>
> : What a stupid question.
>
> : Even if it made sense to teach all of these algorithms (the only ones I
> : cover in my algorithms class are a and c, unless you count heap sort as
> : a form of selection sort) none of them are in any way independent of
> : their input -- how could any useful program be?
Lots of useful programs are: even sorting algorithms. eg bitonic sort.
None of the listed ones were though.
Justin
Glenn
>I came across a question from the CS GRE test that
>asked which sort is Most independent of its input.
>a)quick sort
>b)insertion sort
>c)merge sort
>d)selection sort
>e)Shell's sort
>I picked d but the answer says c. After thinking
>about it a bit I feel both answers are correct...
>Unless there is a clever version of selection sort?
>Anyone can help?
>-Chen
I would pick d because selection sort makes the same number of comparisons
and data moves for a fixed number of inputs regardless of the input
permutation. By this criteria merge sort would be the second choice.
To me this is the most natural interpretation of the question so I
would say that the test makers made a mistake. They might possibly
have some other interpretation of "independent" in which case the
question is rather poorly worded (in any case the question is not
worded all that well).
Nick Maclaren
In article <6v0svd$fhc$1...@magpie.doc.ic.ac.uk>, jp...@lobster.doc.ic.ac.uk (Justin Cormack) writes:
|> In article <6v085v$v53$1...@hecate.umd.edu>, che...@Glue.umd.edu (Chen Wang) writes:
|> >
|> > David Eppstein (epps...@euclid.ics.uci.edu) wrote:
|> > : > I came across a question from the CS GRE test that
|> > : > asked which sort is Most independent of its input.
|> > : > a)quick sort b)insertion sort c)merge sort d)selection sort e)Shell's sort
|> >
|> >
|> > : Even if it made sense to teach all of these algorithms (the only ones I
|> > : cover in my algorithms class are a and c, unless you count heap sort as
|> > : a form of selection sort) none of them are in any way independent of
|> > : their input -- how could any useful program be?
|>
|> Lots of useful programs are: even sorting algorithms. eg bitonic sort.
|> None of the listed ones were though.
Eh? Because the very nature of a sort is to rearrange its input,
which will depend on its data values, a sort that is independent of
its input isn't going to work. If you mean that its execution time
is independent of the order of its input, that is not what the
question asked. And, in any case, merge sort is (to a first
approximation) and shellsort and several of the O(N^2) sorts are
in some of their forms.
I do have some useful programs that take no input, but they are all
the 'sources' for 'filters', and the word "specialised" springs to
mind. Pseudorandom number generators are perhaps the most common
example, but a prime number generator would also be one. In general,
programs that are independent of their input are NOT useful.
Yes, it IS a stupid question. It could be rephrased so that it
isn't but, as it stands, it is.
Nick Maclaren
Isaac To <kk...@csis.hku.hk> wrote:
>>>>>> "Nick" == Nick Maclaren <nm...@cus.cam.ac.uk> writes:
>
> Justin> Lots of useful programs are: even sorting algorithms. eg bitonic
> Justin> sort. None of the listed ones were though.
>
> Nick> Eh? Because the very nature of a sort is to rearrange its input,
> Nick> which will depend on its data values, a sort that is independent
> Nick> of its input isn't going to work.
>
>I think Justin is referring to the fact that some algorithm can be
>represented by a sequence of operations saying "compare x1 and x2", where x1
>and x2 can only be either "the k-th input", or "the larger/smaller one of
>the k-th comparison", for a constant k. That is, the target of comparisons
>are completely independent on the input. This is equivalent to saying that
>the algorithm can be represented by a sorting network. Example: I can sort
>4 numbers A,B,C,D by 6 comparisons using bubble sort, comparing E=(A,B),
>F=(Es,C), G=(Fs,D), H=(El,Fl), I=(Gl,Hs), J=(Hl,Il). The sorted sequence is
>always (Jl,Js,Is,Gs), independent of the input.
>
>Bitonic sort is definitely one such algorithm. In fact, bubble sort can be
>implemented like this (without doing the normal optimization to stop when a
>phase contain no comparion), and insertion sort can also be done like this
>(without doing the normal optimization to stop when one find the correct
>place to insert an element). I think Merge sort, quick sort and selection
>sort probably can't be expressed this way, but I don't know for sure.
Merge sort, selection sort and shellsort can. I would need to think
about quicksort, but I believe that I could produce such a variant.
It wouldn't look much like any quicksort that most people are familiar
with, but it would use only published techniques and would still be
quicksort.
>But of course, I wonder why we want this particularly narrow definition of
>"independence on input".
The only use that I know of is when you need to build sorting code into
silicon and you have a fixed number of items as input. Yes, this does
occur, especially in things like very fast multiplexors.
However, if you are going to consider such specialised uses, you are
not talking about ordinary degree courses, and most definitely not
school (UK usage) courses! So they are completely irrelevant to the
original question.
Isaac To
Justin> Lots of useful programs are: even sorting algorithms. eg bitonic
Justin> sort. None of the listed ones were though.
Nick> Eh? Because the very nature of a sort is to rearrange its input,
Nick> which will depend on its data values, a sort that is independent
Nick> of its input isn't going to work.
I think Justin is referring to the fact that some algorithm can be
represented by a sequence of operations saying "compare x1 and x2", where x1
and x2 can only be either "the k-th input", or "the larger/smaller one of
the k-th comparison", for a constant k. That is, the target of comparisons
are completely independent on the input. This is equivalent to saying that
the algorithm can be represented by a sorting network. Example: I can sort
4 numbers A,B,C,D by 6 comparisons using bubble sort, comparing E=(A,B),
F=(Es,C), G=(Fs,D), H=(El,Fl), I=(Gl,Hs), J=(Hl,Il). The sorted sequence is
always (Jl,Js,Is,Gs), independent of the input.
Bitonic sort is definitely one such algorithm. In fact, bubble sort can be
implemented like this (without doing the normal optimization to stop when a
phase contain no comparion), and insertion sort can also be done like this
(without doing the normal optimization to stop when one find the correct
place to insert an element). I think Merge sort, quick sort and selection
sort probably can't be expressed this way, but I don't know for sure.
But of course, I wonder why we want this particularly narrow definition of
"independence on input".
Isaac.