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[i] > a[j]){
n = a[i];
a[i] = 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[i] > a[i + 1]){
n = a[i];
a[i] = a[i + 1];
a[i + 1] = n;
}
}

lovecreatesbea...@gmail.com 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[i] > a[j]){
> n = a[i];
> a[i] = 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[i] > a[i + 1]){
> n = a[i];
> a[i] = 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?

--
Eric.Sosman@sun.com

On Oct 16, 12:32 pm, "lovecreatesbea...@gmail.com"
<lovecreatesbea...@gmail.com> wrote:
> 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.
news:comp.programming 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[i];
array[i] = 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[i] < array[j]) {
tmp = array[i];
array[i] = 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

Eric Sosman wrote:
>
> lovecreatesbea...@gmail.com 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[i] > a[j]){
> > n = a[i];
> > a[i] = 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[i] > a[i + 1]){
> > n = a[i];
> > a[i] = 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.

--
pete

On Oct 17, 9:57 am, pete <pfil...@mindspring.com> wrote:
> Eric Sosman wrote:
>
> > lovecreatesbea...@gmail.com 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[i] > a[j]){
> > > n = a[i];
> > > a[i] = 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[i] > a[i + 1]){
> > > n = a[i];
> > > a[i] = 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.

On Oct 17, 7:22 am, user923005 <dcor...@connx.com> wrote:
> On Oct 16, 12:32 pm, "lovecreatesbea...@gmail.com"
>
> <lovecreatesbea...@gmail.com> wrote:
> > 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.
>
> news:comp.programming 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[i];
> array[i] = 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[i] < array[j]) {
> tmp = array[i];
> array[i] = 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?

> {
> 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

On Oct 16, 7:15 pm, "lovecreatesbea...@gmail.com"
<lovecreatesbea...@gmail.com> wrote:
> On Oct 17, 9:57 am, pete <pfil...@mindspring.com> wrote:
>
>
>
>
>
> > Eric Sosman wrote:
>
> > > lovecreatesbea...@gmail.com 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[i] > a[j]){
> > > > n = a[i];
> > > > a[i] = 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[i] > a[i + 1]){
> > > > n = a[i];
> > > > a[i] = 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.

On Oct 16, 7:50 pm, "lovecreatesbea...@gmail.com"
<lovecreatesbea...@gmail.com> wrote:
> On Oct 17, 7:22 am, user923005 <dcor...@connx.com> wrote:
>
> > On Oct 16, 12:32 pm, "lovecreatesbea...@gmail.com"
>
> > <lovecreatesbea...@gmail.com> wrote:
> > > 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.
>
> > news:comp.programming is the appropriate place for your question.
>
> 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
news:comp.programming. 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[i];
> > array[i] = 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[i] < array[j]) {
> > tmp = array[i];
> > array[i] = 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).

> > {
> > 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- Hide quoted text -

On Oct 17, 11:07 am, user923005 <dcor...@connx.com> wrote:
> On Oct 16, 7:15 pm, "lovecreatesbea...@gmail.com"
>
>
>
>
>
> <lovecreatesbea...@gmail.com> wrote:
> > On Oct 17, 9:57 am, pete <pfil...@mindspring.com> wrote:
>
> > > Eric Sosman wrote:
>
> > > > lovecreatesbea...@gmail.com 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[i] > a[j]){
> > > > > n = a[i];
> > > > > a[i] = 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[i] > a[i + 1]){
> > > > > n = a[i];
> > > > > a[i] = 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.

On Oct 16, 9:50 pm, "lovecreatesbea...@gmail.com"
<lovecreatesbea...@gmail.com> wrote:
> On Oct 17, 11:07 am, user923005 <dcor...@connx.com> wrote:
[snip]
> > 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 :-(

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

> > 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.

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.

On Oct 17, 7:22 am, user923005 <dcor...@connx.com> wrote:
> On Oct 16, 12:32 pm, "lovecreatesbea...@gmail.com"
>
> <lovecreatesbea...@gmail.com> wrote:
> > 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.
>
> news:comp.programming 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[i];
> array[i] = 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[i] < array[j]) {
> tmp = array[i];
> array[i] = 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?

> {
> 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

"user923005" <dcorbit@connx.com> wrote in message
news:1192592464.351119.14100@v29g2000prd.googlegro ups.com...
> On Oct 16, 7:50 pm, "lovecreatesbea...@gmail.com"
> <lovecreatesbea...@gmail.com> wrote:
>> On Oct 17, 7:22 am, user923005 <dcor...@connx.com> wrote:
>>

<snip>

>
> 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...).

On Oct 17, 4:34 pm, "cr88192" <cr88...@hotmail.com> wrote:
> "user923005" <dcor...@connx.com> wrote in message
>
> news:1192592464.351119.14100@v29g2000prd.googlegro ups.com...
>
> > On Oct 16, 7:50 pm, "lovecreatesbea...@gmail.com"
> > <lovecreatesbea...@gmail.com> wrote:
> >> On Oct 17, 7:22 am, user923005 <dcor...@connx.com> wrote:
>
> <snip>
>
> > 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...).

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 17, 7:22 am, user923005 <dcor...@connx.com> wrote:
> On Oct 16, 12:32 pm, "lovecreatesbea...@gmail.com"
>> ...

[...]

> 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[i] < array[j]) {
> tmp = array[i];
> array[i] = 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[i] > a[i + 1]){
n = a[i];
a[i] = a[i + 1];
a[i + 1] = n;
}
}

On Oct 17, 4:41 am, user923005 <dcor...@connx.com> wrote:

> 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[i] = 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.

"lovecreatesbea...@gmail.com" <lovecreatesbeauty@gmail.com> wrote in message
news:1192611262.584712.210200@z24g2000prh.googlegr oups.com...
> On Oct 17, 4:34 pm, "cr88192" <cr88...@hotmail.com> wrote:
>> "user923005" <dcor...@connx.com> wrote in message
>>
>> news:1192592464.351119.14100@v29g2000prd.googlegro ups.com...
>>
>> > On Oct 16, 7:50 pm, "lovecreatesbea...@gmail.com"
>> > <lovecreatesbea...@gmail.com> wrote:
>> >> On Oct 17, 7:22 am, user923005 <dcor...@connx.com> wrote:
>>
>> <snip>
>>
>> > 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...).
>
> 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[i]>arr[i+1])
{ swap(arr, i, i+1); j++; }
for(i=(r-1); i>l; i--)
if(arr[i]<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 17, 7:22 am, user923005 <dcor...@connx.com> wrote:
>> On Oct 16, 12:32 pm, "lovecreatesbea...@gmail.com"
>>> ...
>
> [...]
>
>> 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[i] < array[j]) {
>> tmp = array[i];
>> array[i] = 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[i] > a[i + 1]){
> n = a[i];
> a[i] = a[i + 1];
> a[i + 1] = n;
> }
> }
>

christian.bau wrote:
>
> On Oct 17, 4:41 am, user923005 <dcor...@connx.com> wrote:
>
> > 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[i] = 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[i] > a[i + 1]){
n = a[i];
a[i] = 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

--
pete

On Oct 17, 1:34 am, "cr88192" <cr88...@hotmail.com> wrote:
> "user923005" <dcor...@connx.com> wrote in message
>
> news:1192592464.351119.14100@v29g2000prd.googlegro ups.com...
>
> > On Oct 16, 7:50 pm, "lovecreatesbea...@gmail.com"
> > <lovecreatesbea...@gmail.com> wrote:
> >> On Oct 17, 7:22 am, user923005 <dcor...@connx.com> wrote:
>
> <snip>
>
>
>
> > 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...

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.

On Oct 17, 1:56 am, "christian.bau" <christian....@cbau.wanadoo.co.uk>
wrote:
> On Oct 17, 4:41 am, user923005 <dcor...@connx.com> wrote:
>
> > 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[i] = 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.

"user923005" <dcorbit@connx.com> wrote in message
news:1192647862.830022.301470@q3g2000prf.googlegro ups.com...
> On Oct 17, 1:34 am, "cr88192" <cr88...@hotmail.com> wrote:
>> "user923005" <dcor...@connx.com> wrote in message
>>
>> news:1192592464.351119.14100@v29g2000prd.googlegro ups.com...
>>
>> > On Oct 16, 7:50 pm, "lovecreatesbea...@gmail.com"
>> > <lovecreatesbea...@gmail.com> wrote:
>> >> On Oct 17, 7:22 am, user923005 <dcor...@connx.com> wrote:
>>
>> <snip>
>>
>>
>>
>> > 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...
>
> 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...


>> 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