Selection sort and bubble sort

Discussion in 'C Programming' started by lovecreatesbea...@gmail.com, Oct 16, 2007.

  1. Guest

    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;
    }
    }
    , Oct 16, 2007
    #1
    1. Advertising

  2. Eric Sosman Guest

    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?

    --
    Eric Sosman, Oct 16, 2007
    #2
    1. Advertising

  3. user923005 Guest

    On Oct 16, 12:32 pm, ""
    <> 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;
    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
    user923005, Oct 17, 2007
    #3
  4. pete Guest

    Eric Sosman wrote:
    >
    > 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.

    --
    pete
    pete, Oct 17, 2007
    #4
  5. Guest

    On Oct 17, 9:57 am, pete <> wrote:
    > Eric Sosman wrote:
    >
    > > 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.
    , Oct 17, 2007
    #5
  6. Guest

    On Oct 17, 7:22 am, user923005 <> wrote:
    > On Oct 16, 12:32 pm, ""
    >
    > <> 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;
    > 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?

    > {
    > 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
    , Oct 17, 2007
    #6
  7. user923005 Guest

    On Oct 16, 7:15 pm, ""
    <> wrote:
    > On Oct 17, 9:57 am, pete <> wrote:
    >
    >
    >
    >
    >
    > > Eric Sosman wrote:

    >
    > > > 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, Oct 17, 2007
    #7
  8. user923005 Guest

    On Oct 16, 7:50 pm, ""
    <> wrote:
    > On Oct 17, 7:22 am, user923005 <> wrote:
    >
    > > On Oct 16, 12:32 pm, ""

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

    > > {
    > > 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 -
    user923005, Oct 17, 2007
    #8
  9. Guest

    On Oct 17, 11:07 am, user923005 <> wrote:
    > On Oct 16, 7:15 pm, ""
    >
    >
    >
    >
    >
    > <> wrote:
    > > On Oct 17, 9:57 am, pete <> wrote:

    >
    > > > Eric Sosman wrote:

    >
    > > > > 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.
    , Oct 17, 2007
    #9
  10. user923005 Guest

    On Oct 16, 9:50 pm, ""
    <> wrote:
    > On Oct 17, 11:07 am, user923005 <> 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.
    user923005, Oct 17, 2007
    #10
  11. Guest

    On Oct 17, 7:22 am, user923005 <> wrote:
    > On Oct 16, 12:32 pm, ""
    >
    > <> 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;
    > 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?

    > {
    > 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
    , Oct 17, 2007
    #11
  12. cr88192 Guest

    "user923005" <> wrote in message
    news:...
    > On Oct 16, 7:50 pm, ""
    > <> wrote:
    >> On Oct 17, 7:22 am, user923005 <> 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...).
    cr88192, Oct 17, 2007
    #12
  13. Guest

    On Oct 17, 4:34 pm, "cr88192" <> wrote:
    > "user923005" <> wrote in message
    >
    > news:...
    >
    > > On Oct 16, 7:50 pm, ""
    > > <> wrote:
    > >> On Oct 17, 7:22 am, user923005 <> 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 <> wrote:
    > On Oct 16, 12:32 pm, ""
    >> ...


    [...]

    > 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;
    }
    }
    , Oct 17, 2007
    #13
  14. On Oct 17, 4:41 am, user923005 <> 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 = 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.
    christian.bau, Oct 17, 2007
    #14
  15. cr88192 Guest

    "" <> wrote in message
    news:...
    > On Oct 17, 4:34 pm, "cr88192" <> wrote:
    >> "user923005" <> wrote in message
    >>
    >> news:...
    >>
    >> > On Oct 16, 7:50 pm, ""
    >> > <> wrote:
    >> >> On Oct 17, 7:22 am, user923005 <> 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>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 17, 7:22 am, user923005 <> wrote:
    >> On Oct 16, 12:32 pm, ""
    >>> ...

    >
    > [...]
    >
    >> 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;
    > }
    > }
    >
    cr88192, Oct 17, 2007
    #15
  16. pete Guest

    christian.bau wrote:
    >
    > On Oct 17, 4:41 am, user923005 <> 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 = 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

    --
    pete
    pete, Oct 18, 2007
    #16
  17. user923005 Guest

    On Oct 17, 1:34 am, "cr88192" <> wrote:
    > "user923005" <> wrote in message
    >
    > news:...
    >
    > > On Oct 16, 7:50 pm, ""
    > > <> wrote:
    > >> On Oct 17, 7:22 am, user923005 <> 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.
    user923005, Oct 18, 2007
    #17
  18. user923005 Guest

    On Oct 17, 1:56 am, "christian.bau" <>
    wrote:
    > On Oct 17, 4:41 am, user923005 <> 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 = 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, Oct 18, 2007
    #18
  19. cr88192 Guest

    "user923005" <> wrote in message
    news:...
    > On Oct 17, 1:34 am, "cr88192" <> wrote:
    >> "user923005" <> wrote in message
    >>
    >> news:...
    >>
    >> > On Oct 16, 7:50 pm, ""
    >> > <> wrote:
    >> >> On Oct 17, 7:22 am, user923005 <> 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 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...
    cr88192, Oct 18, 2007
    #19
  20. user923005 Guest

    On Oct 18, 12:04 am, "cr88192" <> wrote:
    > "user923005" <> wrote in message
    >
    > news:...
    > > On Oct 17, 1:34 am, "cr88192" <> wrote:
    > >> "user923005" <> wrote in message

    >
    > >>news:...

    >
    > >> > On Oct 16, 7:50 pm, ""
    > >> > <> wrote:
    > >> >> On Oct 17, 7:22 am, user923005 <> 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...


    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]
    user923005, Oct 18, 2007
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Scott Lyons

    Two-Dimensional Bubble Sort

    Scott Lyons, May 3, 2004, in forum: C++
    Replies:
    1
    Views:
    379
    Scott Lyons
    May 3, 2004
  2. Protoman
    Replies:
    8
    Views:
    485
    Richard Herring
    Apr 5, 2006
  3. bubble sort

    , Aug 28, 2006, in forum: C++
    Replies:
    3
    Views:
    497
  4. mlimber
    Replies:
    0
    Views:
    787
    mlimber
    Aug 5, 2008
  5. Michael Campbell

    Bubble sort and rand()

    Michael Campbell, Sep 17, 2003, in forum: Ruby
    Replies:
    0
    Views:
    91
    Michael Campbell
    Sep 17, 2003
Loading...

Share This Page