Selection sort and bubble sort

[lovecreatesbea...]

Selection sort and bubble sort have same performance always, right?
Are the following correctly implemented the both functions. Comments
are welcome.


Selection sort an array of intergers range between index l and r in
ascending order. For example, sort "312" into "123"

void sort_sel(int a, int l, int r)
{
int i, j, n;

for (i = l; i < r; i++)
for (j = i + 1; j <= r; j++)
if (a > a[j]){
n = a;
a = a[j];
a[j] = n;
}
}


Bubble sort an array of intergers range between index l and r in
ascending order. For example, sort "312" into "123"

void sort_bub(int a, int l, int r)
{
int i, n;

for (; l < r; r--)
for (i = l; i < r; i++)
if (a > a[i + 1]){
n = a;
a = a[i + 1];
a[i + 1] = n;
}
}

 

[Eric Sosman]

(e-mail address removed) wrote On 10/16/07 15:32,:

Selection sort and bubble sort have same performance always, right?

Are the following correctly implemented the both functions. Comments
are welcome.


Selection sort an array of intergers range between index l and r in
ascending order. For example, sort "312" into "123"

void sort_sel(int a, int l, int r)
{
int i, j, n;

for (i = l; i < r; i++)
for (j = i + 1; j <= r; j++)
if (a > a[j]){
n = a;
a = a[j];
a[j] = n;
}
}

<off-topic> This is a bubble sort, implemented

Bubble sort an array of intergers range between index l and r in
ascending order. For example, sort "312" into "123"

void sort_bub(int a, int l, int r)
{
int i, n;

for (; l < r; r--)
for (i = l; i < r; i++)
if (a > a[i + 1]){
n = a;
a = a[i + 1];
a[i + 1] = n;
}
}

<off-topic> This is also a bubble sort, whose
implementation efficiency rivals that of the first
example. </off-topic>

Did you have a C question?

 

[user923005]

Selection sort and bubble sort have same performance always, right?

Sort of. They are both O(n*n) but bubble sort has a larger constant
of proportionality.

Are the following correctly implemented the both functions. No.

Comments
are welcome.

is the appropriate place for your question.

[snip of icky[tm] sorts, insertion of nearly equally icky[tm] sorts:]

#include <stdlib.h>
#ifdef UNIT_TEST
typedef int e_type;
#else
#include "e_type.h"
#endif

void selection_sort(e_type array[], size_t size)
{
size_t i,
j,
smallest;
e_type tmp;
for (i = 0; i < size - 1; i++) {
smallest = i;
for (j = i + 1; j < size; j++) {
if (array[j] < array[smallest]) {
smallest = j;
}
}
tmp = array;
array = array[smallest];
array[smallest] = tmp;
}
}

void bubble_sort(e_type * array, size_t length)
{
size_t i,
j;
e_type tmp;
for (i = 0; i < length; i++) {
for (j = 0; j < i; j++) {
if (array < array[j]) {
tmp = array;
array = array[j];
array[j] = tmp;
}
}
}
}

#ifdef UNIT_TEST
#include <stdio.h>
#include <time.h>

static e_type arr[65535];
static size_t e_size = sizeof arr / sizeof arr[0];

void sort_check(void)
{
size_t index;
int failed = 0;
for (index = 1; index < e_size; index++) {
if (arr[index - 1] > arr[index]) {
printf("Out of sort at %d where arr[%d]=%d > arr[%d]=%d
\n", index, index - 1, arr[index - 1], index, arr[index]);
failed = 1;
}
}
if (failed)
puts("Sort failed.");
else
puts("Sort succeeded.");

}

void mk_rand_arr(void)
{
size_t index;
for (index = 0; index < e_size; index++) {
arr[index] = rand();
}
}

int main()
{
time_t start;
double delta;
mk_rand_arr();
puts("Selection Sort:");
start = time(NULL);
selection_sort(arr, e_size);
delta = difftime(time(NULL), start);
sort_check();
printf("Elapsed time is %f\n", delta);
mk_rand_arr();
puts("Bubble Sort:");
start = time(NULL);
bubble_sort(arr, e_size);
delta = difftime(time(NULL), start);
printf("Elapsed time is %f\n", delta);
sort_check();
return 0;
}
#endif

 

[pete]

(e-mail address removed) wrote On 10/16/07 15:32,:

Selection sort and bubble sort have same performance always, right?

Are the following correctly implemented the both functions. Comments
are welcome.


Selection sort an array of intergers range between index l and r in
ascending order. For example, sort "312" into "123"

void sort_sel(int a, int l, int r)
{
int i, j, n;

for (i = l; i < r; i++)
for (j = i + 1; j <= r; j++)
if (a > a[j]){
n = a;
a = a[j];
a[j] = n;
}
}

<off-topic> This is a bubble sort, implemented

Bubble sort an array of intergers range between index l and r in
ascending order. For example, sort "312" into "123"

void sort_bub(int a, int l, int r)
{
int i, n;

for (; l < r; r--)
for (i = l; i < r; i++)
if (a > a[i + 1]){
n = a;
a = a[i + 1];
a[i + 1] = n;
}
}

<off-topic> This is also a bubble sort, whose
implementation efficiency rivals that of the first
example. </off-topic>

Did you have a C question?

int a, should probably be int *a, instead.

 

[lovecreatesbea...]

(e-mail address removed) wrote On 10/16/07 15:32,:

<off-topic> Wrong. </off-topic>

Are the following correctly implemented the both functions. Comments
are welcome.
Selection sort an array of intergers range between index l and r in
ascending order. For example, sort "312" into "123"
void sort_sel(int a, int l, int r)
{
int i, j, n;
for (i = l; i < r; i++)
for (j = i + 1; j <= r; j++)
if (a > a[j]){
n = a;
a = a[j];
a[j] = n;
}
}

<off-topic> This is a bubble sort, implemented
inefficiently even by B.S. standards. </off-topic>

Bubble sort an array of intergers range between index l and r in
ascending order. For example, sort "312" into "123"
void sort_bub(int a, int l, int r)
{
int i, n;
for (; l < r; r--)
for (i = l; i < r; i++)
if (a > a[i + 1]){
n = a;
a = a[i + 1];
a[i + 1] = n;
}
}

<off-topic> This is also a bubble sort, whose
implementation efficiency rivals that of the first
example. </off-topic>

Did you have a C question?

int a, should probably be int *a, instead.

Yes, they're removed carelessly when the code was posted.

 

[lovecreatesbea...]

Sort of. They are both O(n*n) but bubble sort has a larger constant
of proportionality.


is the appropriate place for your question.

People use different language there, and I like the C code.

[snip of icky[tm] sorts, insertion of nearly equally icky[tm] sorts:]

#include <stdlib.h>
#ifdef UNIT_TEST
typedef int e_type;
#else
#include "e_type.h"
#endif

void selection_sort(e_type array[], size_t size)
{
size_t i,
j,
smallest;
e_type tmp;
for (i = 0; i < size - 1; i++) {
smallest = i;
for (j = i + 1; j < size; j++) {
if (array[j] < array[smallest]) {
smallest = j;
}
}
tmp = array;
array = array[smallest];
array[smallest] = tmp;
}

}

Your code does less exchange than mine (though an asterisk missed for
the parameter a).

void bubble_sort(e_type * array, size_t length)
{
size_t i,
j;
e_type tmp;
for (i = 0; i < length; i++) {
for (j = 0; j < i; j++) {
if (array < array[j]) {
tmp = array;
array = array[j];
array[j] = tmp;
}
}
}

}

#ifdef UNIT_TEST
#include <stdio.h>
#include <time.h>

static e_type arr[65535];
static size_t e_size = sizeof arr / sizeof arr[0];

void sort_check(void)
{
size_t index;
int failed = 0;
for (index = 1; index < e_size; index++) {
if (arr[index - 1] > arr[index]) {
printf("Out of sort at %d where arr[%d]=%d > arr[%d]=%d
\n", index, index - 1, arr[index - 1], index, arr[index]);
failed = 1;
}
}
if (failed)
puts("Sort failed.");
else
puts("Sort succeeded.");

}

void mk_rand_arr(void)
{
size_t index;
for (index = 0; index < e_size; index++) {
arr[index] = rand();
}

}

int main()

If UNIT_TEST isn't defined, the main() function is skipped. Your .c
file can compile but can't link, am I right?

 

[user923005]

Eric Sosman wrote:

(e-mail address removed) wrote On 10/16/07 15:32,:
Selection sort and bubble sort have same performance always, right?
<off-topic> Wrong. </off-topic>
Are the following correctly implemented the both functions. Comments
are welcome.
Selection sort an array of intergers range between index l and r in
ascending order. For example, sort "312" into "123"
void sort_sel(int a, int l, int r)
{
int i, j, n;
for (i = l; i < r; i++)
for (j = i + 1; j <= r; j++)
if (a > a[j]){
n = a;
a = a[j];
a[j] = n;
}
}
<off-topic> This is a bubble sort, implemented
inefficiently even by B.S. standards. </off-topic>
Bubble sort an array of intergers range between index l and r in
ascending order. For example, sort "312" into "123"
void sort_bub(int a, int l, int r)
{
int i, n;
for (; l < r; r--)
for (i = l; i < r; i++)
if (a > a[i + 1]){
n = a;
a = a[i + 1];
a[i + 1] = n;
}
}
<off-topic> This is also a bubble sort, whose
implementation efficiency rivals that of the first
example. </off-topic>
Did you have a C question?

int a, should probably be int *a, instead.

Yes, they're removed carelessly when the code was posted.

As a rule of thumb, don't post anything here until it compiles or
until you are simply unable to figure out why it won't compile.
In the latter case, point out "I can't get this code to compile --
what's wrong with it?" or something like that.

When you do get the code to compile, simply copy and paste the working
code into your browser or news client. It is far less error prone
than retyping and considerably easier also.

 

[user923005]

People use different language there, and I like the C code.

That does not make your question topical here. You are not asking
about C. You are asking about algorithms. There is no algorithms
group, per se, so the closest thing is to ask in
If you ask for C there, you will most likely
get it.

[snip of icky[tm] sorts, insertion of nearly equally icky[tm] sorts:]

#include <stdlib.h>
#ifdef UNIT_TEST
typedef int e_type;
#else
#include "e_type.h"
#endif

void selection_sort(e_type array[], size_t size)
{
size_t i,
j,
smallest;
e_type tmp;
for (i = 0; i < size - 1; i++) {
smallest = i;
for (j = i + 1; j < size; j++) {
if (array[j] < array[smallest]) {
smallest = j;
}
}
tmp = array;
array = array[smallest];
array[smallest] = tmp;
}

}

Your code does less exchange than mine (though an asterisk missed for
the parameter a).

Of course, it's simply awful anyway. The only O(n^2) sort worth
knowing is insertion sort. There are some very, very rare cases where
selection or even bubble sort can prove worthwhile, but it takes a
real expert to know what they are and even in that case, it carries
intense danger (in case the initial conditions do not hold).

void bubble_sort(e_type * array, size_t length)
{
size_t i,
j;
e_type tmp;
for (i = 0; i < length; i++) {
for (j = 0; j < i; j++) {
if (array < array[j]) {
tmp = array;
array = array[j];
array[j] = tmp;
}
}
}

}

#ifdef UNIT_TEST
#include <stdio.h>
#include <time.h>

static e_type arr[65535];
static size_t e_size = sizeof arr / sizeof arr[0];

void sort_check(void)
{
size_t index;
int failed = 0;
for (index = 1; index < e_size; index++) {
if (arr[index - 1] > arr[index]) {
printf("Out of sort at %d where arr[%d]=%d > arr[%d]=%d
\n", index, index - 1, arr[index - 1], index, arr[index]);
failed = 1;
}
}
if (failed)
puts("Sort failed.");
else
puts("Sort succeeded.");

}

void mk_rand_arr(void)
{
size_t index;
for (index = 0; index < e_size; index++) {
arr[index] = rand();
}

}

int main()

If UNIT_TEST isn't defined, the main() function is skipped. Your .c
file can compile but can't link, am I right?

That's the idea of a unit test. If you have UNIT_TEST defined, then
the code is tested. If UNIT_TEST is not defined, then you will need a
header file to define what e_type means (possibly switching by means
of a macro). In any case, you won't want to use either selection sort
or bubble sort for anything at all besides a toy demo program because
both of them are icky(tm).

 

[lovecreatesbea...]

Eric Sosman wrote:
(e-mail address removed) wrote On 10/16/07 15:32,:
Selection sort and bubble sort have same performance always, right?
<off-topic> Wrong. </off-topic>
Are the following correctly implemented the both functions. Comments
are welcome.
Selection sort an array of intergers range between index l and r in
ascending order. For example, sort "312" into "123"
void sort_sel(int a, int l, int r)
{
int i, j, n;
for (i = l; i < r; i++)
for (j = i + 1; j <= r; j++)
if (a > a[j]){
n = a;
a = a[j];
a[j] = n;
}
}
<off-topic> This is a bubble sort, implemented
inefficiently even by B.S. standards. </off-topic>
Bubble sort an array of intergers range between index l and r in
ascending order. For example, sort "312" into "123"
void sort_bub(int a, int l, int r)
{
int i, n;
for (; l < r; r--)
for (i = l; i < r; i++)
if (a > a[i + 1]){
n = a;
a = a[i + 1];
a[i + 1] = n;
}
}
<off-topic> This is also a bubble sort, whose
implementation efficiency rivals that of the first
example. </off-topic>
Did you have a C question?
int a, should probably be int *a, instead.

Yes, they're removed carelessly when the code was posted.

As a rule of thumb, don't post anything here until it compiles or
until you are simply unable to figure out why it won't compile.
In the latter case, point out "I can't get this code to compile --
what's wrong with it?" or something like that.

We can make mistakes in a usenet newsgroup, can't we :-(

When you do get the code to compile, simply copy and paste the working
code into your browser or news client. It is far less error prone
than retyping and considerably easier also.

Yes, it's good suggestion.

I did a replacement in Vi and removed the asterisks in my code
carelessly.

 

[user923005]

We can make mistakes in a usenet newsgroup, can't we :-(

I don't have any problem with someone making mistakes. If the same
mistake happens 77 times in a row, I get annoyed.

Yes, it's good suggestion.

I did a replacement in Vi and removed the asterisks in my code
carelessly.

No wonder. The editor vi is icky(tm). But so is emacs. I do all my
Unix side editing with UltraEdit32, which will do the end line
translations for you and does all kinds of wonderful things like
syntax coloring and can handle 100 GB files.

IMO-YMMV.

 

[lovecreatesbea...]

Sort of. They are both O(n*n) but bubble sort has a larger constant
of proportionality.


is the appropriate place for your question.

People use different language there, and I like the C code.

[snip of icky[tm] sorts, insertion of nearly equally icky[tm] sorts:]

#include <stdlib.h>
#ifdef UNIT_TEST
typedef int e_type;
#else
#include "e_type.h"
#endif

void selection_sort(e_type array[], size_t size)
{
size_t i,
j,
smallest;
e_type tmp;
for (i = 0; i < size - 1; i++) {
smallest = i;
for (j = i + 1; j < size; j++) {
if (array[j] < array[smallest]) {
smallest = j;
}
}
tmp = array;
array = array[smallest];
array[smallest] = tmp;
}

}

Your code does less exchange than mine (though an asterisk missed for
the parameter a).

void bubble_sort(e_type * array, size_t length)
{
size_t i,
j;
e_type tmp;
for (i = 0; i < length; i++) {
for (j = 0; j < i; j++) {
if (array < array[j]) {
tmp = array;
array = array[j];
array[j] = tmp;
}
}
}

}

#ifdef UNIT_TEST
#include <stdio.h>
#include <time.h>

static e_type arr[65535];
static size_t e_size = sizeof arr / sizeof arr[0];

void sort_check(void)
{
size_t index;
int failed = 0;
for (index = 1; index < e_size; index++) {
if (arr[index - 1] > arr[index]) {
printf("Out of sort at %d where arr[%d]=%d > arr[%d]=%d
\n", index, index - 1, arr[index - 1], index, arr[index]);
failed = 1;
}
}
if (failed)
puts("Sort failed.");
else
puts("Sort succeeded.");

}

void mk_rand_arr(void)
{
size_t index;
for (index = 0; index < e_size; index++) {
arr[index] = rand();
}

}

int main()

If UNIT_TEST isn't defined, the main() function is skipped. Your .c
file can compile but can't link, am I right?

 

[cr88192]

Of course, it's simply awful anyway. The only O(n^2) sort worth
knowing is insertion sort. There are some very, very rare cases where
selection or even bubble sort can prove worthwhile, but it takes a
real expert to know what they are and even in that case, it carries
intense danger (in case the initial conditions do not hold).

well, there is a useful point:
bubble sort and selection sort are very simple...
this is especially useful for when one doesn't really care much about
performance (or the input set is very small), or where one is feeling too
lazy right then to write/use a quicksort variant...

some variations of bubble sort can also deliver fairly good performance in
certain cases.

tree sort is also worth looking into (as a potentially faster alternative to
insertion sort...).

 

[lovecreatesbea...]

well, there is a useful point:
bubble sort and selection sort are very simple...
this is especially useful for when one doesn't really care much about
performance (or the input set is very small), or where one is feeling too
lazy right then to write/use a quicksort variant...

some variations of bubble sort can also deliver fairly good performance in
certain cases.

tree sort is also worth looking into (as a potentially faster alternative to
insertion sort...).

Yes, I feel that they're similar also.

What did you mean by variations when you mentioned bubble sort? Can
the following two bubble functions be called two variations?

On Oct 16, 12:32 pm, "(e-mail address removed)"

...

[...]

void bubble_sort(e_type * array, size_t length)
{
size_t i,
j;
e_type tmp;
for (i = 0; i < length; i++) {
for (j = 0; j < i; j++) {
if (array < array[j]) {
tmp = array;
array = array[j];
array[j] = tmp;
}
}
}

}

void sort_bub(int *a, int l, int r)
{
int i, n;

for (; l < r; r--)
for (i = l; i < r; i++)
if (a > a[i + 1]){
n = a;
a = a[i + 1];
a[i + 1] = n;
}
}

 

[christian.bau]

Of course, it's simply awful anyway. The only O(n^2) sort worth
knowing is insertion sort. There are some very, very rare cases where
selection or even bubble sort can prove worthwhile, but it takes a
real expert to know what they are and even in that case, it carries
intense danger (in case the initial conditions do not hold).

Insertion sort has the great advantage that it can be used to keep an
array sorted when new items arrive one at a time.

However, your command about bubble sort is incorrect. While selection
sort _always_ takes c*N^2 steps, bubble sort is very data dependent,
and there is one well-known situation where it is about the most
efficient method: Given an array with values a = f (t, i) where f
changes slowly as t changes. Once that array is sorted, and t is
changed slightly, so that all the values in the array are close to
their correct position, bubblesort can be the fastest method to make
that array sorted again.

 

[cr88192]

Yes, I feel that they're similar also.

What did you mean by variations when you mentioned bubble sort? Can
the following two bubble functions be called two variations?

well, typically, variation implies a different algo.

an example of a variation:
only making passes until there are no more moves;
taking note that after each pass (for a bidirectional variant), the left and
right elements will contain the new min and max values.

an example (trying to recall from memory):
l=0; r=cnt;
while(1)
{
r--; j=0;
for(i=l; i<r; i++)
if(arr>arr[i+1])
{ swap(arr, i, i+1); j++; }
for(i=(r-1); i>l; i--)
if(arr<arr[i-1])
{ swap(arr, i, i-1); j++; }
l++;
if(!j)break;
}

I think this is fairly similar to a sorting algo I had used for a fairly
long time (until I came to understand quicksort...).

note that (for a little extra cost) it is possible to perform quicksort
in-place.

On Oct 16, 12:32 pm, "(e-mail address removed)"

...

[...]

void bubble_sort(e_type * array, size_t length)
{
size_t i,
j;
e_type tmp;
for (i = 0; i < length; i++) {
for (j = 0; j < i; j++) {
if (array < array[j]) {
tmp = array;
array = array[j];
array[j] = tmp;
}
}
}

}

void sort_bub(int *a, int l, int r)
{
int i, n;

for (; l < r; r--)
for (i = l; i < r; i++)
if (a > a[i + 1]){
n = a;
a = a[i + 1];
a[i + 1] = n;
}
}

 

[pete]

Of course, it's simply awful anyway. The only O(n^2) sort worth
knowing is insertion sort.
There are some very, very rare cases where
selection or even bubble sort can prove worthwhile, but it takes a
real expert to know what they are and even in that case, it carries
intense danger (in case the initial conditions do not hold).

Insertion sort has the great advantage that it can be used to keep an
array sorted when new items arrive one at a time.

However, your command about bubble sort is incorrect. While selection
sort _always_ takes c*N^2 steps, bubble sort is very data dependent,
and there is one well-known situation where it is about the most
efficient method: Given an array with values a = f (t, i) where f
changes slowly as t changes. Once that array is sorted, and t is
changed slightly, so that all the values in the array are close to
their correct position, bubblesort can be the fastest method to make
that array sorted again.

I think you're talking about a different version of
bubble sort from the one that was posted in this thread.
Knuth describes bubble sort as being O(N*N) for both
worst case and average case, but O(N) for best case.
The bubble sort posted by OP, sort_bub,
is just O(N*N) for everything.

void sort_bub(int a, int l, int r)
{
int i, n;

for (; l < r; r--)
for (i = l; i < r; i++)
if (a > a[i + 1]){
n = a;
a = a[i + 1];
a[i + 1] = n;
}
}

I don't understand why even a good bubble sort
would be faster than insertion sort for the
"one well-known situation" which you describe.

When insertion sort is implemented as an exchange type
of sorting algorithm, it takes the same number of exchanges
to sort an array as bubble sort does.
Insertion sort never requires more array element value
comparisons than bubble sort does; so if
bubble sort were to outperform insertion sort,
it would have to be that the book keeping part
of the implementation of the algorithm was more efficient,
or that I'm not understanding you correctly.

When insertion sort is implemented as a daisy chaining
algorithm, instead of as an exchange type,
(consider sisort vs. i_sort)
then it is even harder for me to envision a case
where a bubble sort could outperform it.

#define E_TYPE long unsigned
#define GT(A, B) (*(A) > *(B))
typedef E_TYPE e_type;
void sisort(e_type *array, size_t nmemb)
{
e_type *base, *low, *high, temp;

if (nmemb-- > 1) {
base = array;
do {
low = array++;
if (GT(low, array)) {
high = array;
temp = *high;
do {
*high-- = *low;
if (low == base) {
break;
}
--low;
} while (GT(low, &temp));
*high = temp;
}
} while (--nmemb != 0);
}
}

void i_sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
unsigned char *array, *high, *low, *p1, *p2, *end, swap;

if (nmemb-- > 1) {
array = base;
do {
low = array;
array += size;
high = array;
while (compar(low, high) > 0) {
p1 = low;
p2 = high;
end = p2 + size;
do {
swap = *p1;
*p1++ = *p2;
*p2++ = swap;
} while (p2 != end);
if (low == base) {
break;
}
high = low;
low -= size;
}
} while (--nmemb != 0);
}
}

I don't think there's any way that any bubble sort function
could outperform a bubble insertion sort hybrid like sisor2.

void sisor2(e_type *array, size_t nmemb)
{
e_type *low, *high, temp;

if (nmemb-- > 1) {
low = array + nmemb;
do {
high = low--;
if (GT(low, high)) {
temp = *high;
*high = *low;
*low = temp;
}
} while (low != array);
if (nmemb-- > 1) {
++array;
do {
low = array++;
if (GT(low, array)) {
high = array;
temp = *high;
do {
*high-- = *low--;
} while (GT(low, &temp));
*high = temp;
}
} while (--nmemb != 0);
}
}
}

The point of the hybrid, is that the initial bubblesort pass,
eliminates the need for the break statement in the insertion sort part.

Followup To: comp.programming

 

[user923005]

well, there is a useful point:
bubble sort and selection sort are very simple...
this is especially useful for when one doesn't really care much about
performance (or the input set is very small), or where one is feeling too
lazy right then to write/use a quicksort variant...

If you want simple then call the qsort() library interface. I have
seen a one million dollar project scuttled by the use of bubble sort.

some variations of bubble sort can also deliver fairly good performance in
certain cases.

tree sort is also worth looking into (as a potentially faster alternative to
insertion sort...).

For tiny sets, insertion sort is a good general choice (unless you
know that the data will come in reversed order, in which case it is a
terrible choice).
For small sets, shell sort is a good general choice (reverse ordered
is again the worst input set).
For larger sets, introspective sort is a good general choice.

I have never seen a tree sort that beats any of those for random
distributions in their perspective wheel houses.

Do you know of a particularly good implementation of tree sort? I
would like to benchmark it if you know of a specially good one.

 

[user923005]

Of course, it's simply awful anyway. The only O(n^2) sort worth
knowing is insertion sort. There are some very, very rare cases where
selection or even bubble sort can prove worthwhile, but it takes a
real expert to know what they are and even in that case, it carries
intense danger (in case the initial conditions do not hold).

Insertion sort has the great advantage that it can be used to keep an
array sorted when new items arrive one at a time.

However, your command about bubble sort is incorrect. While selection
sort _always_ takes c*N^2 steps, bubble sort is very data dependent,
and there is one well-known situation where it is about the most
efficient method: Given an array with values a = f (t, i) where f
changes slowly as t changes. Once that array is sorted, and t is
changed slightly, so that all the values in the array are close to
their correct position, bubblesort can be the fastest method to make
that array sorted again.

Even in that case it scales badly if it is not a very tiny subset that
is out of sort.

On the other hand, I know of one chess program where I tried to
improve the speed of sorting the move list by changing to insertion
sort from bubble sort and it slowed down. That is because (due to
previous searches) the move list is already ordered 90% correct or
better every time.

Even at that, if you are going to use bubble sort in any application,
you had better be darn sure that you know exactly what the
distribution of the data looks like and that it will never change over
time or scale up to a very large set.

 

[cr88192]

If you want simple then call the qsort() library interface. I have
seen a one million dollar project scuttled by the use of bubble sort.

qsort is, typically, quicksort.
now, one can maybe debate whether it is better to use qsort, or to implement
a custom sorter (properly specialized for the data being sorted), but oh
well...

For tiny sets, insertion sort is a good general choice (unless you
know that the data will come in reversed order, in which case it is a
terrible choice).
For small sets, shell sort is a good general choice (reverse ordered
is again the worst input set).
For larger sets, introspective sort is a good general choice.

I have never seen a tree sort that beats any of those for random
distributions in their perspective wheel houses.

well, I was just providing it as an alternative to insertion sort (primarily
useful in cases where one recieves the data 1 element or so at a time and
builds/updates the structure dynamically...).

insertion sort is O(n^2), wheras tree sort is O(n log2 n).
if one can do better, then maybe.

Do you know of a particularly good implementation of tree sort? I
would like to benchmark it if you know of a specially good one.

well, this is likely difficult here (at least if the input structure is not
naturally based around linked lists or similar...). a major potential source
of overhead is likely to be in maintaining and updating the tree structure.

sadly, off hand I don't really know of any tree-sort implementations worth
much consideration for benchmarking (never really been that much into
fine-grained comparative algo benchmarking...).

or such...

 

[user923005]

qsort is, typically, quicksort.
now, one can maybe debate whether it is better to use qsort, or to implement
a custom sorter (properly specialized for the data being sorted), but oh
well...

The qsort() interface is almost never implemented as quicksort (on
modern compilers).
Once in a while we will find a modified version of Richard Singleton's
ACM algorithm 347.
Much more likely is introspective sort. P. J. Plauger's qsort()
interface is a typical {well done} introspective sort version.

I suppose that there may be a few vendors that have no idea what they
are doing.

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.

[snip]