Re: Selection sort and bubble sort
- From: user923005 <dcorbit@xxxxxxxxx>
- Date: Mon, 22 Oct 2007 12:15:14 -0700
On Oct 20, 3:40 am, "cr88192" <cr88...@xxxxxxxxxxxxxxxxxx> wrote:
"user923005" <dcor...@xxxxxxxxx> wrote in message
news:1192837761.239691.303570@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
On Oct 19, 4:03 pm, "cr88192" <cr88...@xxxxxxxxxxxxxxxxxx> wrote:
"user923005" <dcor...@xxxxxxxxx> wrote in message
news:1192774610.213261.31130@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
On Oct 18, 4:15 pm, "cr88192" <cr88...@xxxxxxxxxxxxxxxxxx> wrote:
"user923005" <dcor...@xxxxxxxxx> wrote in message[snip]
I would think that Jon Bentley's article in "Unix Review" of August
1992 would have put a final end to anyone thinking of using ordinary
quicksort as a library function for the qsort() interface.
in my case, a paper from this timeframe is a little before my time...
I was alive then, but not much more can be said (this was before I
learned
programming, and I learned programming during my elem school
years...).
quicksort usually does pretty well IME.
The keyword here is 'usually'. On bad inputs (which are not uncommon
such as already sorted, reverse sorted, organ pipe, and some others)
qsort goes quadratic. In the noted article something that usually ran
in a couple hours ran for a week or two (citing from memory).
I think the main issue is how one chooses the median.
in that particular version (the one I had used in a BWT implementation,
and
a few others), 1 pass was used to determine the min and max, and the mid
point was calculated exactly.
This version will usually perform quite well, but loses some in
efficiency, since each recurive call will visit every item in the set
to calculate the median. Usually, a set is sampled randomly and the
median is estimated using the sample.
Unless you calculate the median exactly (and that cannot be done by
averaging min and max) then you can still have serious problems with
some distributions. Calculating the median is O(n) on average, but
there is a large constant of proportionaltiy.
yeah, I had used both approaches at different times (exact calculation, and
the '(min+max)/2' estimate).
It's a lot simpler to simply revert to heapsort if we see that we have
recursed farther than log(n) times.
yes, but note that heapsort is not the simplest of sorting methods (unlike
selection sort, or a modified bubble sort), which is why I had not done so
before...
/*
This version of heapsort is adapted from:
Data Structures and Algorithm Analysis in C (Second Edition)
by Mark Allen Weiss
Addison-Wesley, 1997
ISBN: 0-201-49840-5
Page 228.
It is simple and interesting, but quick-sort is better than heap-sort.
*/
#define LeftChild( i ) ( 2 * ( i ) + 1 )
void PERCDOWN(Etype A[], int i, int N)
{
int Child;
Etype Tmp;
for (Tmp = A[i]; LeftChild(i) < N; i = Child) {
Child = LeftChild(i);
if (Child != N - 1 && GT(A[Child + 1], A[Child]))
Child++;
if (LT(Tmp, A[Child]))
A[i] = A[Child];
else
break;
}
A[i] = Tmp;
}
void HEAPSORT(Etype A[], int N)
{
int i;
for (i = N / 2; i >= 0; i--)
/* BuildHeap */
PERCDOWN(A, i, N);
for (i = N - 1; i > 0; i--) {
SWAP(&A[0], &A[i]);
/* DeleteMax */
PERCDOWN(A, 0, i);
}
}
more often (since then) I use either the middle or a random element.
now, one could always fall back to bubble sort as well (in cases where
the
recursion depth is too deep, as opposed to selection sort as I had done
in
the past...).
Falling back to bubble sort will not solve the problem. Bubble sort
is O(N^2) and worst case quick sort is O(N^2) and so the fallback to
bubble sort won't change the behavior when it goes bad.
yes, it does change the behavior. how: bad inputs on large sets will not
cause the stack to overflow...
(with a 'pure' quicksort, I had ran into this problem more than a few
times).
No. WHen you switch to heapsort, you have no danger of stack overflow
either. So that is not an advantage.
well, also note that I had typically not used a pure bubble sort, but a
modified bubble sort (a general approach I had tweaked over the years to
make it faster).
This is always an interesting exercise.
the tweaks had consisted of going back and forth in both directions
(generally caused values to sort out much faster), and also eliminating the
min and max extremes (noting that the largest and smallest values tend to
move directly to the ends). likewise, I tended to cut out early, as very
often sorting would seem to get done much faster than the theoretical limit.
this was actually my preferred sorting method for years until I figured out
how to implement in-place quicksort...
but, it may not seem like much, but these approaches have held up fairly
well IME...
You can limit stack problems with quicksort to a large degree by
always searching the smallest partition first. And (of course) the
'introspective sort' approach completely eliminates the problem.
.
- References:
- Re: Selection sort and bubble sort
- From: cr88192
- Re: Selection sort and bubble sort
- From: user923005
- Re: Selection sort and bubble sort
- From: cr88192
- Re: Selection sort and bubble sort
- Prev by Date: Re: Converting interleaved data to planar?
- Next by Date: Re: Selection sort and bubble sort
- Previous by thread: Re: Selection sort and bubble sort
- Next by thread: Re: Selection sort and bubble sort
- Index(es):
Relevant Pages
|
