Selection-Sort in C

[Phil Carmody]

Sorting is O(1) if, rather than counting comparisons or swaps,
you count calls to qsort().

You seem to be overlooking the 'size of the input' aspect.

Phil

 

[Keith Thompson]

You seem to be overlooking the 'size of the input' aspect.

How so?

I was making a true statement, but it was (clearly, I thought)
a joke.

Sorting an array, of whatever size, requires exactly 1 call to
qsort(). Since 1 is O(1), sorting an array is O(1) if you count
calls to qsort(). It's obviously O(something bigger) if you count
comparisons, data movement, or anything reasonable.

 

[Ben Bacarisse]

[...]
Many years ago there was a crackpot posting here who claimed that
sorting was O(n). It turns out that if you think about it
properly, it is.

Sorting is O(1) if, rather than counting comparisons or swaps,
you count calls to qsort().


True, but no cigar. A more precise statement is that the time
required for sorting is O(n) - omega(n) if you prefer.

I don't see how your statement is more precise than mine; it's just
a different statement. (My statement is admittedly silly.)

My apologies, the relevant measure is big theta. That is, there
are algorithms such that the worst case cost of sorting is
THETA(n), i.e., if C(n) is the worst case sorting time cost for
data sets of size n, there are constants c1, c2, and n0 such that
c1*n < C(n) <c2*n for n>n0.

Will that do?

Not for me. Lots of things are missing: the model of computation; the
unit of measure used for "cost"; the representation of the problem
and, by implication, of the solution; what n denotes...[*] Lots of
apparently surprising remarks can be made about computations when
these sorts of things are omitted.

I think Keith was pointing to one of these ambiguities by suggesting a
new unit of measure for the cost.

BTW, you almost certainly don't need THETA to make the claim
interesting. Big O is an upper bound, so O(n) is the key complexity
measure. That the lower bound is also linear does not seem to add
much.

[*] Typing this was like the Monty Python sketch. I started by
stating that two things were missing, then I added a third... and then
a fourth. I've opted for "lots" and a trailing ellipsis because I bet
I've forgotten some others.

 

[Ben Bacarisse]

On Sat, 03 Oct 2009 10:55:15 -0700, Keith Thompson

(e-mail address removed) (Richard Harter) writes:
[...]
Many years ago there was a crackpot posting here who claimed that
sorting was O(n). It turns out that if you think about it
properly, it is.

Sorting is O(1) if, rather than counting comparisons or swaps,
you count calls to qsort().


True, but no cigar. A more precise statement is that the time
required for sorting is O(n) - omega(n) if you prefer.

I don't see how your statement is more precise than mine; it's just
a different statement. (My statement is admittedly silly.)

My apologies, the relevant measure is big theta. That is, there
are algorithms such that the worst case cost of sorting is
THETA(n), i.e., if C(n) is the worst case sorting time cost for
data sets of size n, there are constants c1, c2, and n0 such that
c1*n < C(n) <c2*n for n>n0.

Will that do?

Not for me. Lots of things are missing: the model of computation; the
unit of measure used for "cost"; the representation of the problem
and, by implication, of the solution; what n denotes...[*] Lots of
apparently surprising remarks can be made about computations when
these sorts of things are omitted.

Well no, you don't need all of those things; you only need one of
them and you've actually been given the one you need, albeit with
no attention called to it. Think of this as a challenge: there
is a quite natural interpretation of the statement, sorting is
O(n).

For the moment I must simply take your word for it. I suspect we have
very different notions of how the term "natural" applies to theoretical
concepts like asymptotic bounds of algorithms. Still, I stand by
ready to be amazed!

The challenge is to realize what that interpretation is.
There is an important principle involved.

I hope you won't keep us in the dark too long.

It's a way of dissing O(1) claims.

I don't see how. Any O(1) algorithm can be made THETA(n) with a
simple loop, can't it?

[*] Typing this was like the Monty Python sketch. I started by
stating that two things were missing, then I added a third... and then
a fourth. I've opted for "lots" and a trailing ellipsis because I bet
I've forgotten some others.

But you see only one of all your things are relevant, just as
they aren't relevant to the claim that sorting is O(n*log n);

That's another matter altogether. Sorting is a problem not an
algorithm. Personally, I'd never say that sorting is O(f) for any f
since I don't know of any results of that kind for this class of
problem (I am sure there are some, I just don't know any). Whilst I
agree one can allow some of the things I listed to be unstated for an
/algorithm/[1], I don't think any can left out when discussing a
/problem/.

BTW, I will be mildly peeved if the big assumption you think I am
making is to assume that all sorting algorithms are comparison sorts.
Your posting history suggest to me that you might have something more
interesting in mind, but I honestly have no idea what is encompassed
by your notion of "natural".

[1] The reason being (in my narrow-minded view of these things) that
the specification of the algorithm pins several of them down -- maybe
not entirely, but enough to be able to move on to an analysis. For a
problem, a one-word description ("sorting") leaves them all up in the
air.

 

[Eric Sosman]

[...]
Heap sort isn't easy to understand, isn't nearly so easy
to program, is easy to get wrong, and /always/ is doing
non-local operations; it also isn't stable. Heap sort
is a great sorting algorithm.

Something you forgot to mention is that Heapsort is
O(N*logN) even in the worst case. Heapsort's worst case
isn't "degenerate," unlike that of Quicksort, say.

Merge sort is usually dismissed because of needing extra
space. Yes it's possible to do a stable merge sort on an
array and use only O(1) extra space, but programming that is
horrendous.

On the other hand, merge sort is flat-out beautiful for
linked lists, where the O(N) space for the links is "free"
because it's already there.

 

[Phil Carmody]

(e-mail address removed) (Richard Harter) replied to Ben Bacarisse:
....

After all, we need to establish whether sorting actually is
Theta(n) where n is the number of bits in the data set. The
lower bound is clear enough - whatever the algorithm an oracle
can force it to examine every bit. The upper bound is a bit
murkier. The simple argument runs like this:

Let m be the number of elements and n be the total data set size.
Comparison sorts require O(m * log m) operations. However if
there are m distinct elements then the average size of an element
has to be >= log m.

And therefore the cost of those operations is theta(log(m)) elementary
operations. Therefore comparison sorts require O(m*log(m)^2).

Ergo n >= m * log m. Ergo O(n) is an upper bound.

This no longer follows. Comparison sorts were never going to provide
the tight bound. See threads between Dan Bernstein and, IIRC, Nick
McLaren on sorting for more - probably comp.programming, not so sure
though.

Phil

 

[Ben Bacarisse]

On Sun, 04 Oct 2009 13:52:48 +0100, Ben Bacarisse


[snip a lot of stuff - look at the previous postings if you want
background]

That's another matter altogether. Sorting is a problem not an
algorithm.

None-the-less it makes sense to speak of order functions for
problems. Given a problem, there will be a wide variety of
algorithms that can be used to solve it. The intrinsic cost of
solving that problem is the cost of the best algorithms. Thus it
makes sense to say that the traveling salesman problem is
exponential. There is an implicit assumption here that the
algorithms run on a Turing machine equivalent.

That's way too vague for me. We are not talking about computability
but sub-polynomial complexity here and I don't know what else might be
"Turing machine equivalent" in that context. What other models have
exactly the same class of "linear-time" problems as TMs?

Personally, I'd never say that sorting is O(f) for any f
since I don't know of any results of that kind for this class of
problem (I am sure there are some, I just don't know any). Whilst I
agree one can allow some of the things I listed to be unstated for an
/algorithm/[1], I don't think any can left out when discussing a
/problem/.

But they can - it's just a matter of abstraction.

BTW, I will be mildly peeved if the big assumption you think I am
making is to assume that all sorting algorithms are comparison sorts.
Your posting history suggest to me that you might have something more
interesting in mind, but I honestly have no idea what is encompassed
by your notion of "natural".

I'm wasn't but prepare to be disappointed - I expect your
reaction will be "Is that all?". You asked, quite properly, what
does n denote. And the answer is, and I quote, "data sets of
size n". But what how do you measure size? The natural
measurement of the size of a data set is the amount of storage it
occupies. For specialized data sets such as arrays of elements
it is convenient to use the number of elements as a measure of
size, but it the actual number of bits that is primary. (Don't
argue with me on this point; I'm right by definition. )

And, better, you are right by virtue of being right! The size of the
input is the usual measure for a problem and the usual unit is bits
(which is why the encoding can be so important).

Yes, I am disappointed, but there is enthusiasm as well. The last I
knew anything of the state of the art in this area (more than a decade
ago) it was widely thought that sorting m numbers encoded in (on
average) r bits would be found to be O(mr) but it had not, at the
time, been show to be so. Are you saying that it now is? Is there
any reference to this work that is accessible to someone without a
good library?

Please forgive me for not just talking your argument as a proof. It
seems to be worded as an argument about an abstract model far removed
from a TM. What model is it and how do you know that is it equivalent
to a TM as far as the class of linear problems is concerned?

<snip argument about O(n = mr) sort>

 

[Tim Rentsch]

[...]
Heap sort isn't easy to understand, isn't nearly so easy
to program, is easy to get wrong, and /always/ is doing
non-local operations; it also isn't stable. Heap sort
is a great sorting algorithm.

Something you forgot to mention is that Heapsort is
O(N*logN) even in the worst case. Heapsort's worst case
isn't "degenerate," unlike that of Quicksort, say.

Right. It isn't that I forgot really, just that the mention was
rather cryptic (calling it "a great sorting algorithm").
Something of a playful posting, I took a few liberties.

I also didn't mention (at least not directly) Quicksort's
average-case running time of O(N log N), which is a very
important plus.

Speaking of which, I also left out Shell sort, which has a
running time more like O( N**1.5 ). If you're looking for a
suboptimal-but-not-too-suboptimal sorting algorithm, Shell sort
is a good candidate!

On the other hand, merge sort is flat-out beautiful for
linked lists, where the O(N) space for the links is "free"
because it's already there.

Merge sort on linked lists is rather nice. It's not so
satisfying in C though, because it's inconvenient to write a C
routine to perform this algorithm for different kinds of linked
lists. C provides arrays in a form that allows arrays with
different element types to be dealt with easily (by means of
(void*) pointers and an extra argument giving element size, etc).
Analogous code for linked lists is rather clunky, requiring
functions to access and update the "next element" link value.
I suspect this has a lot to do with why a linked list sort
function hasn't made its way into the standard library.

 

[user923005]

(e-mail address removed) (Richard Harter) writes:
[...]

Many years ago there was a crackpot posting here who claimed that
sorting was O(n).  It turns out that if you think about it
properly, it is.

Sorting is O(1) if, rather than counting comparisons or swaps,
you count calls to qsort().

You seem to be overlooking the 'size of the input' aspect.

FTSI:
;-)

P.S. (for the seriously smiley impaired):
Calls to qsort() will undoubtably be O(log(N)) for random data, unless
qsort() has been converted from recursion to iteration.

 

[Keith Thompson]

(e-mail address removed) (Richard Harter) writes:
[...]
Many years ago there was a crackpot posting here who claimed that
sorting was O(n).  It turns out that if you think about it
properly, it is.

Sorting is O(1) if, rather than counting comparisons or swaps,
you count calls to qsort().

You seem to be overlooking the 'size of the input' aspect.

FTSI:
;-)

Googling "FTSI" doesn't give me anything useful. I'm probably missing
an obvious joke.

P.S. (for the seriously smiley impaired):
Calls to qsort() will undoubtably be O(log(N)) for random data, unless
qsort() has been converted from recursion to iteration.

Right, I didn't think about recursion. Of course qsort() itself
needn't be recursive; it could call some other recursive function
that does the actual work. And of course qsort() needn't use Quicksort.

glibc's qsort() uses a non-recursive version of Quicksort, falling
back to insertion sort for small partitions.

 

[user923005]

(e-mail address removed) (Richard Harter) writes:
[...]
Many years ago there was a crackpot posting here who claimed that
sorting was O(n).  It turns out that if you think about it
properly, it is.
Sorting is O(1) if, rather than counting comparisons or swaps,
you count calls to qsort().
You seem to be overlooking the 'size of the input' aspect.

FTSI:
;-)

Googling "FTSI" doesn't give me anything useful.  I'm probably missing
an obvious joke.

(F)or (T)he (S)miley (I)mpaired

Similar to:
FTSSI (for the seriously smiley impaired)

 

[Keith Thompson]

(F)or (T)he (S)miley (I)mpaired

Similar to:
FTSSI (for the seriously smiley impaired)

Yeah, that should have been obvious, epecially given the immediately
following line:

*sigh*

[...]

 

[Richard Bos]

Tim Rentsch wrote:

On the other hand, merge sort is flat-out beautiful for
linked lists, where the O(N) space for the links is "free"
because it's already there.

For the links, yes; but even for linked lists, it needs at least one
extra head node per level of recursion, unless I've been missing a
trick. This is not a lot, though, and it's still by far the most elegant
way I know of sorting a linked list.

Richard

 

[Eric Sosman]

I don't know what you mean by
"it needs at least one extra head node per level of recursion".

He means that a list merge sort operates by merging short
ordered sublists into longer sublists, and then merging those
into still longer sublists, and so on until the final merge
puts the entire original list into order. Keeping track of
all those sublists (whether by recursion or by other means)
needs O(log N) additional storage.

But since O(N) + O(log N) = O(N), this makes no difference
at all asymptotically. Even in practice it makes not enough
difference to fret about: sixty-four 64-bit pointers are more
than enough for any machine you or your children are likely
to encounter. If your grandchildren encounter even bigger
machines, they'll have no trouble finding some extra space.

 

[Tim Rentsch]

For the links, yes; but even for linked lists, it needs at least one
extra head node per level of recursion, unless I've been missing a
trick. This is not a lot, though, and it's still by far the most elegant
way I know of sorting a linked list.

Although not immediately obvious, it is possible to
do a merge sort on linked lists without using
recursion and using only O(1) additional storage
(not counting the O(n) space for the links of course):

extern void
list_merge_sort( ListNode **head, int (*order_f)( ListNode *, ListNode *) ){
Count length = list_length( *head );
ListNode *a, *b;
Count remaining, sorted_length, a_n, b_n;
ListNode **last;
Index i;

for(
sorted_length = 1;
sorted_length < length;
sorted_length += MIN( sorted_length, length - sorted_length )
){
remaining = length;
last = head;
while( remaining > 0 ){
remaining -= a_n = MIN( sorted_length, remaining );
remaining -= b_n = MIN( sorted_length, remaining );
a = b = *last;
for( i = 0; i < a_n; i++ ) b = b->next;

while( a_n > 0 || b_n > 0 ){
if( b_n == 0 || a_n > 0 && order_f( a, b ) < 1 ){
*last = a;
last = & a->next;
a = a->next;
a_n --;
} else {
*last = b;
last = & b->next;
b = b->next;
b_n --;
}
}
*last = b;
}
}
}

 

[Tim Rentsch]

He means that a list merge sort operates by merging short
ordered sublists into longer sublists, and then merging those
into still longer sublists, and so on until the final merge
puts the entire original list into order. Keeping track of
all those sublists (whether by recursion or by other means)
needs O(log N) additional storage.

Actually it doesn't -- it can be done with O(1) additional
storage (algorithm shown elsethread).

But since O(N) + O(log N) = O(N), this makes no difference
at all asymptotically. [snip practical comments.]

Even with arrays, without any space for links, stable mergesort
can be done using only O(1) extra space. Those algorithms
aren't really very practical, but not by as much as one
might think. For linked lists the O(1)-space algorithms
are both theoretically interesting and practically useful.