Apparently, someone does love qsort.
Akira Wada wrote:
| I think it would be difficult, not impossible, to decide the threshold
| (Christopher Seiwald said, "# swaps >= 1024", and Tim Vanderhoek suggested,
| "a ratio: #comparisons : # swaps") and to what point of qsort, to make
| isort bail back,
Apparently, someone does love qsort.
Akira Wada wrote:
| I think it would be difficult, not impossible, to decide the threshold
| (Christopher Seiwald said, "# swaps >= 1024", and Tim Vanderhoek suggested,
| "a ratio: #comparisons : # swaps") and to what point of qsort, to make
| isort bail back
Christopher Seiwald wrote...
>Archie's mod to qsort:
>
>| >- if (swap_cnt == 0) { /* Switch to insertion sort */
>| >+ if (n <= 32 && swap_cnt == 0) { /* Switch to insertion sort */
>
>As Akira Wada points out, this eliminates the benefit of the optimization
>in the first place, which i
Christopher Seiwald wrote...
>Archie's mod to qsort:
>
>| >- if (swap_cnt == 0) { /* Switch to insertion sort */
>| >+ if (n <= 32 && swap_cnt == 0) { /* Switch to insertion sort */
>
>As Akira Wada points out, this eliminates the benefit of the optimization
>in the first place, which
On Mon, Aug 23, 1999 at 12:28:32AM -0700, Christopher Seiwald wrote:
>
> The alteration that I've tried and tested is to have the isort bail
> back to qsort if it does more than N swaps. I put N at 1024, which
Perhaps a ratio: #comparisons : # swaps
If the ratio gets too high, then bail.
--
On Mon, Aug 23, 1999 at 12:28:32AM -0700, Christopher Seiwald wrote:
>
> The alteration that I've tried and tested is to have the isort bail
> back to qsort if it does more than N swaps. I put N at 1024, which
Perhaps a ratio: #comparisons : # swaps
If the ratio gets too high, then bail.
--
gurne...@efn.org (John-Mark Gurney) writes:
> Christopher Seiwald scribbled this message on Aug 18:
> > It's a pretty straightforward change to bypass the insertion sort for
> > large subsets of the data. If no one has a strong love for qsort, I'll
> > educate myself on how to make and contribut
[EMAIL PROTECTED] (John-Mark Gurney) writes:
> Christopher Seiwald scribbled this message on Aug 18:
> > It's a pretty straightforward change to bypass the insertion sort for
> > large subsets of the data. If no one has a strong love for qsort, I'll
> > educate myself on how to make and contrib
Archie's mod to qsort:
| >- if (swap_cnt == 0) { /* Switch to insertion sort */
| >+ if (n <= 32 && swap_cnt == 0) { /* Switch to insertion sort */
As Akira Wada points out, this eliminates the benefit of the optimization
in the first place, which is to let isort take over if the data is
Archie's mod to qsort:
| >- if (swap_cnt == 0) { /* Switch to insertion sort */
| >+ if (n <= 32 && swap_cnt == 0) { /* Switch to insertion sort */
As Akira Wada points out, this eliminates the benefit of the optimization
in the first place, which is to let isort take over if the data is
Following my previous post:
I wrote ..
>I believe a reversed dataset would be partitioned
>into two subpartitions sorted in order at the 1'st pass of
>the partitionings. Is this incorrect ?
>
Sorry, I'd confirmed BSD qsort's partitioning logic does not
guarantee that "a reversed dataset would be p
Following my previous post:
I wrote ..
>I believe a reversed dataset would be partitioned
>into two subpartitions sorted in order at the 1'st pass of
>the partitionings. Is this incorrect ?
>
Sorry, I'd confirmed BSD qsort's partitioning logic does not
guarantee that "a reversed dataset would be
Archie Cobbs wrote...
>Christopher Seiwald writes:
>> But as I'm proposing a change to a fairly sensitive piece of code, I'd
>> like to keep the change as modest as possible.
>
>How about this?
>
>Index: qsort.c
>===
>RCS fil
Archie Cobbs wrote...
>Christopher Seiwald writes:
>> But as I'm proposing a change to a fairly sensitive piece of code, I'd
>> like to keep the change as modest as possible.
>
>How about this?
>
>Index: qsort.c
>===
>RCS fi
Archie Cobbs wrote...
>Christopher Seiwald writes:
>> But as I'm proposing a change to a fairly sensitive piece of code, I'd
>> like to keep the change as modest as possible.
>
>How about this?
>
>Index: qsort.c
>===
>RCS fil
Archie Cobbs wrote...
>Christopher Seiwald writes:
>> But as I'm proposing a change to a fairly sensitive piece of code, I'd
>> like to keep the change as modest as possible.
>
>How about this?
>
>Index: qsort.c
>===
>RCS fi
You can check the change by recompiling a few utils with the change:
(find . -name \*.c | xargs grep -l qsort)
./bin/ps/ps.c
./contrib/gcc/*.c
./contrib/top/commands.c
./games/fortune/strfile/strfile.c
./gnu/usr.bin/sort/sort.c
./sbin/fsck/pass2.c
The fsck one is a nice one. Just wack your /usr
You can check the change by recompiling a few utils with the change:
(find . -name \*.c | xargs grep -l qsort)
./bin/ps/ps.c
./contrib/gcc/*.c
./contrib/top/commands.c
./games/fortune/strfile/strfile.c
./gnu/usr.bin/sort/sort.c
./sbin/fsck/pass2.c
The fsck one is a nice one. Just wack your /usr
Christopher Seiwald writes:
> But as I'm proposing a change to a fairly sensitive piece of code, I'd
> like to keep the change as modest as possible.
How about this?
Index: qsort.c
===
RCS file: /home/ncvs/src/lib/libc/stdlib/qsort.c
Christopher Seiwald writes:
> But as I'm proposing a change to a fairly sensitive piece of code, I'd
> like to keep the change as modest as possible.
How about this?
Index: qsort.c
===
RCS file: /home/ncvs/src/lib/libc/stdlib/qsort.
| How about the code following sig. ?
| And the other codes and information on:
|
| http://www.mars.dti.ne.jp/~a-wada/qsortlib.html
Unfortunately, I only use about 5% of my brain, and am incapable of
convincing myself (or anyone else) of the correctness or efficiency
of your qsort algorithm.
In
| How about the code following sig. ?
| And the other codes and information on:
|
| http://www.mars.dti.ne.jp/~a-wada/qsortlib.html
Unfortunately, I only use about 5% of my brain, and am incapable of
convincing myself (or anyone else) of the correctness or efficiency
of your qsort algorithm.
I
Christopher Seiwald writes:
> The FreeBSD qsort implementation has a rather nasty degenerate case.
> If you have data that partitions exactly about the median pivot, yet
> which is unsorted in either partition, you get get treated to an insertion
> sort. Example:
>
> 1 2 3 4 5 6 7 8 9 10 19
Christopher Seiwald writes:
> The FreeBSD qsort implementation has a rather nasty degenerate case.
> If you have data that partitions exactly about the median pivot, yet
> which is unsorted in either partition, you get get treated to an insertion
> sort. Example:
>
> 1 2 3 4 5 6 7 8 9 10 1
Answers to sundry comments:
| why don't you implement this w/ the 5 element median selection qsort
| algorithm? my professor for cis413 talked about this algorithm and
| that it really is the fastest qsort algorithm...
qsort algorithms are like stock market tips: only good in retrospect.
The
Answers to sundry comments:
| why don't you implement this w/ the 5 element median selection qsort
| algorithm? my professor for cis413 talked about this algorithm and
| that it really is the fastest qsort algorithm...
qsort algorithms are like stock market tips: only good in retrospect.
The
Narvi writes:
> Doesn't the qsort just switch to isort *if* the partition to sort is short
> enough?
That's exactly Christopher's point. It should do this but it doesn't.
The code is complex but from a quick glance it appears that the decision
to switch to insertion sort does not depend on the to
Narvi writes:
> Doesn't the qsort just switch to isort *if* the partition to sort is short
> enough?
That's exactly Christopher's point. It should do this but it doesn't.
The code is complex but from a quick glance it appears that the decision
to switch to insertion sort does not depend on the t
Doesn't the qsort just switch to isort *if* the partition to sort is short
enough?
Got to check it out, but afaik the size at that qsorts switch to isort is
usually between 8 and 24, with 16 being most common - both halfs are
shorter than 16, so they get isorted.
Sander
There i
Doesn't the qsort just switch to isort *if* the partition to sort is short
enough?
Got to check it out, but afaik the size at that qsorts switch to isort is
usually between 8 and 24, with 16 being most common - both halfs are
shorter than 16, so they get isorted.
Sander
There
Christopher Seiwald scribbled this message on Aug 18:
> It's a pretty straightforward change to bypass the insertion sort for
> large subsets of the data. If no one has a strong love for qsort, I'll
> educate myself on how to make and contribute this change.
why don't you implement this w/ the 5
Christopher Seiwald scribbled this message on Aug 18:
> It's a pretty straightforward change to bypass the insertion sort for
> large subsets of the data. If no one has a strong love for qsort, I'll
> educate myself on how to make and contribute this change.
why don't you implement this w/ the 5
Christopher Seiwald writes:
> The FreeBSD qsort implementation has a rather nasty degenerate case.
> If you have data that partitions exactly about the median pivot, yet
> which is unsorted in either partition, you get get treated to an insertion
> sort. Example:
>
> 1 2 3 4 5 6 7 8 9 10 19
The FreeBSD qsort implementation has a rather nasty degenerate case.
If you have data that partitions exactly about the median pivot, yet
which is unsorted in either partition, you get get treated to an insertion
sort. Example:
1 2 3 4 5 6 7 8 9 10 19 18 17 16 14 14 13 12 11
qsort picks
Christopher Seiwald writes:
> The FreeBSD qsort implementation has a rather nasty degenerate case.
> If you have data that partitions exactly about the median pivot, yet
> which is unsorted in either partition, you get get treated to an insertion
> sort. Example:
>
> 1 2 3 4 5 6 7 8 9 10 1
The FreeBSD qsort implementation has a rather nasty degenerate case.
If you have data that partitions exactly about the median pivot, yet
which is unsorted in either partition, you get get treated to an insertion
sort. Example:
1 2 3 4 5 6 7 8 9 10 19 18 17 16 14 14 13 12 11
qsort picks
36 matches
Mail list logo
