Velocity Reviews > Selection sort and bubble sort

# Selection sort and bubble sort

lovecreatesbea...@gmail.com
Guest
Posts: n/a

 10-16-2007
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;
}
}

Eric Sosman
Guest
Posts: n/a

 10-16-2007
(E-Mail 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[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?

--
http://www.velocityreviews.com/forums/(E-Mail Removed)

user923005
Guest
Posts: n/a

 10-16-2007
On Oct 16, 12:32 pm, "(E-Mail Removed)"
<(E-Mail Removed)> 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.

> 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

pete
Guest
Posts: n/a

 10-17-2007
Eric Sosman wrote:
>
> (E-Mail 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[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

lovecreatesbea...@gmail.com
Guest
Posts: n/a

 10-17-2007
On Oct 17, 9:57 am, pete <(E-Mail Removed)> wrote:
> Eric Sosman wrote:
>
> > (E-Mail 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[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.

lovecreatesbea...@gmail.com
Guest
Posts: n/a

 10-17-2007
On Oct 17, 7:22 am, user923005 <(E-Mail Removed)> wrote:
> On Oct 16, 12:32 pm, "(E-Mail Removed)"
>
> <(E-Mail Removed)> 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.
>
> > 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
Guest
Posts: n/a

 10-17-2007
On Oct 16, 7:15 pm, "(E-Mail Removed)"
<(E-Mail Removed)> wrote:
> On Oct 17, 9:57 am, pete <(E-Mail Removed)> wrote:
>
>
>
>
>
> > Eric Sosman wrote:

>
> > > (E-Mail 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[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.

user923005
Guest
Posts: n/a

 10-17-2007
On Oct 16, 7:50 pm, "(E-Mail Removed)"
<(E-Mail Removed)> wrote:
> On Oct 17, 7:22 am, user923005 <(E-Mail Removed)> wrote:
>
> > On Oct 16, 12:32 pm, "(E-Mail Removed)"

>
> > <(E-Mail Removed)> 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.

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

lovecreatesbea...@gmail.com
Guest
Posts: n/a

 10-17-2007
On Oct 17, 11:07 am, user923005 <(E-Mail Removed)> wrote:
> On Oct 16, 7:15 pm, "(E-Mail Removed)"
>
>
>
>
>
> <(E-Mail Removed)> wrote:
> > On Oct 17, 9:57 am, pete <(E-Mail Removed)> wrote:

>
> > > Eric Sosman wrote:

>
> > > > (E-Mail 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[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.

user923005
Guest
Posts: n/a

 10-17-2007
On Oct 16, 9:50 pm, "(E-Mail Removed)"
<(E-Mail Removed)> wrote:
> On Oct 17, 11:07 am, user923005 <(E-Mail Removed)> 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.