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 -