Trying Something New To Experiment with

Discussion in 'C Programming' started by joebenjamin, Sep 17, 2007.

  1. joebenjamin

    joebenjamin Guest

    Im tring an experiment that will generate 7000 integer random numbers and
    save them in an array. Then I need to copy these 7000 values into a second
    array, so that I have two identical integer arrays.
    In a function, I want to sort the first array with an un-optimized bubble
    sort.
    In a second function, I want to sort the second array with an optimized
    bubble sort.

    So in the main, I would like to print out the time each sort routine took
    to execute and print out a message determining which sort routine was
    faster.

    Any Ideas, I made this one up for fun to also learn how to do arrays and
    counts.


    Any help would be appreciated.....

    --
    Message posted using http://www.talkaboutprogramming.com/group/comp.lang.c/
    More information at http://www.talkaboutprogramming.com/faq.html
     
    joebenjamin, Sep 17, 2007
    #1
    1. Advertising

  2. joebenjamin

    Army1987 Guest

    On Mon, 17 Sep 2007 04:18:57 -0400, joebenjamin wrote:

    > Im tring an experiment that will generate 7000 integer random numbers and
    > save them in an array. Then I need to copy these 7000 values into a second
    > array, so that I have two identical integer arrays.
    > In a function, I want to sort the first array with an un-optimized bubble
    > sort.
    > In a second function, I want to sort the second array with an optimized
    > bubble sort.

    Optimized bubble sort?

    > So in the main, I would like to print out the time each sort routine
    > took to execute and print out a message determining which sort routine
    > was faster.


    #include <time.h>
    int main(void)
    {
    clock_t start, end;
    double t0, t1;
    start = clock();
    func0(arr0, 7000);
    end = clock();
    t0 = (double)(end - start) / CLOCKS_PER_SEC;
    /* Now t0 is the *processor* time elapsed by func0. Repeat the
    * same for func1, compare them, print them, etc. */
    return 0;
    }

    > Any Ideas, I made this one up for fun to also learn how to do arrays and
    > counts.

    Is there anybody still taking bubblesort seriously? Isn't it just a
    teaching toy? No, I'm told that it predates selection sort and insertion
    sort... But I still can't imagine how anybody could come up with something
    like that having serious purposes.

    --
    Army1987 (Replace "NOSPAM" with "email")
    If you're sending e-mail from a Windows machine, turn off Microsoft's
    stupid “Smart Quotes†feature. This is so you'll avoid sprinkling garbage
    characters through your mail. -- Eric S. Raymond and Rick Moen
     
    Army1987, Sep 17, 2007
    #2
    1. Advertising

  3. joebenjamin

    Willem Guest

    joebenjamin wrote:
    ) Im tring an experiment that will generate 7000 integer random numbers and
    ) save them in an array. Then I need to copy these 7000 values into a second
    ) array, so that I have two identical integer arrays.
    ) In a function, I want to sort the first array with an un-optimized bubble
    ) sort.
    ) In a second function, I want to sort the second array with an optimized
    ) bubble sort.
    )
    ) So in the main, I would like to print out the time each sort routine took
    ) to execute and print out a message determining which sort routine was
    ) faster.
    )
    ) Any Ideas, I made this one up for fun to also learn how to do arrays and
    ) counts.

    I'm not sure what it is you want help with... In any case, this may be
    useful: (Quoted from the manual:)

    The clock() function determines the amount of processor time used since
    the invocation of the calling process, measured in CLOCKS_PER_SECs of a
    second.



    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
     
    Willem, Sep 17, 2007
    #3
  4. joebenjamin

    CBFalconer Guest

    joebenjamin wrote:
    >
    > Im tring an experiment that will generate 7000 integer random
    > numbers and save them in an array. Then I need to copy these 7000
    > values into a second array, so that I have two identical integer
    > arrays. In a function, I want to sort the first array with an
    > un-optimized bubble sort. In a second function, I want to sort
    > the second array with an optimized bubble sort.
    >
    > So in the main, I would like to print out the time each sort
    > routine took to execute and print out a message determining which
    > sort routine was faster.


    Sounds simple, so just do it. However you should realize that a
    bubble sort is fundamentally unsound in that it is inefficient.
    Also, you don't need to save the original sequence (unless you have
    other different uses for it) since you can save the initializing
    value for the rand (or random) function, and thus reset it to
    regenerate the same sequence.

    --
    Chuck F (cbfalconer at maineline dot net)
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net>


    --
    Posted via a free Usenet account from http://www.teranews.com
     
    CBFalconer, Sep 17, 2007
    #4
  5. joebenjamin

    pete Guest

    Army1987 wrote:
    >
    > On Mon, 17 Sep 2007 04:18:57 -0400, joebenjamin wrote:


    > > Any Ideas, I made this one up for fun
    > > to also learn how to do arrays and counts.


    > Is there anybody still taking bubblesort seriously?


    He said "for fun".

    > Isn't it just a teaching toy?


    That's also what he said.

    --
    pete
     
    pete, Sep 17, 2007
    #5
  6. joebenjamin

    Tor Rustad Guest

    pete wrote:
    > Army1987 wrote:
    >> On Mon, 17 Sep 2007 04:18:57 -0400, joebenjamin wrote:

    >
    >>> Any Ideas, I made this one up for fun
    >>> to also learn how to do arrays and counts.

    >
    >> Is there anybody still taking bubblesort seriously?

    >
    > He said "for fun".
    >
    >> Isn't it just a teaching toy?

    >
    > That's also what he said.


    It smelled like homework to me.

    --
    Tor <torust [at] online [dot] no>
     
    Tor Rustad, Sep 17, 2007
    #6
  7. joebenjamin

    pete Guest

    Tor Rustad wrote:
    >
    > pete wrote:
    > > Army1987 wrote:
    > >> On Mon, 17 Sep 2007 04:18:57 -0400, joebenjamin wrote:

    > >
    > >>> Any Ideas, I made this one up for fun
    > >>> to also learn how to do arrays and counts.

    > >
    > >> Is there anybody still taking bubblesort seriously?

    > >
    > > He said "for fun".
    > >
    > >> Isn't it just a teaching toy?

    > >
    > > That's also what he said.

    >
    > It smelled like homework to me.


    I wrote one for fun and to learn a little about sorting.

    http://www.mindspring.com/~pfilandr/C/e_driver/e_driver.c
    http://www.mindspring.com/~pfilandr/C/e_driver/

    --
    pete
     
    pete, Sep 17, 2007
    #7
  8. >Is there anybody still taking bubblesort seriously? Isn't it just a
    >teaching toy?


    It isn't that terrible if the number of items to sort is 3 or fewer.

    >No, I'm told that it predates selection sort and insertion
    >sort... But I still can't imagine how anybody could come up with something
    >like that having serious purposes.


    Bubblesort is a reasonable auxiliary sorting method to use with
    bogosort. Bogosort: You generate all possible orders of the data
    to be sorted, count how many entries are out of sequence for each
    order, then sort (using an auxiliary sorting method) the orders by
    number of entries that are out of sequence, and take the smallest
    one. The purpose of this is to change an algorithm that is n log
    n in CPU time and n in memory to n! log n! in CPU time and n*n! in
    memory. Bogosort is not used much outside of "cost plus" contracts.

    A first-level bogosort uses some other algorithm (e.g. bubblesort)
    as an auxiliary sorting method. An Nth-level (N > 1) bogosort uses a
    (N-1)th level bogosort as an auxiliary sorting method.
     
    Gordon Burditt, Sep 18, 2007
    #8
  9. joebenjamin

    pete Guest

    Gordon Burditt wrote:
    >
    > >Is there anybody still taking bubblesort seriously? Isn't it just a
    > >teaching toy?

    >
    > It isn't that terrible if the number of items to sort is 3 or fewer.
    >
    > >No, I'm told that it predates selection sort and insertion
    > >sort... But I still can't imagine how anybody could come up with something
    > >like that having serious purposes.

    >
    > Bubblesort is a reasonable auxiliary sorting method to use with
    > bogosort. Bogosort: You generate all possible orders of the data
    > to be sorted, count how many entries are out of sequence for each
    > order, then sort (using an auxiliary sorting method) the orders by
    > number of entries that are out of sequence, and take the smallest
    > one. The purpose of this is to change an algorithm that is n log
    > n in CPU time and n in memory to n! log n! in CPU time and n*n! in
    > memory. Bogosort is not used much outside of "cost plus" contracts.
    >
    > A first-level bogosort uses some other algorithm (e.g. bubblesort)
    > as an auxiliary sorting method. An Nth-level (N > 1) bogosort uses a
    > (N-1)th level bogosort as an auxiliary sorting method.


    A typical stable implementation of insertion sort
    has to check after every comparison to make sure that
    operations aren't attempted at a lower address than the array,
    as in the break statement in sisort.
    Using bubblesort to sort the first element of the array,
    allows the rest of the array to be sorted by an insertion sort
    that does not make an address check, resulting in very tight
    inner do loops as in sisor2, which is also stable.

    #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 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);
    }
    }
    }

    --
    pete
     
    pete, Sep 18, 2007
    #9
  10. joebenjamin

    Eric Sosman Guest

    [OT] Re: Trying Something New To Experiment with

    Army1987 wrote:
    > [...]
    > Is there anybody still taking bubblesort seriously? Isn't it just a
    > teaching toy? No, I'm told that it predates selection sort and insertion
    > sort... But I still can't imagine how anybody could come up with something
    > like that having serious purposes.


    Knuth illustrates (TAOCP Figure 5.3.4.47) circumstances
    in which bubble sort and insertion sort are identical. Not
    just "same big-O," but identical.

    Knuth also reports (TAOCP Exercise 5.3.4.68) on Demuth's
    construction of a situation in which bubble sort is optimal.

    Neither of the above has much relevance to "general
    purpose" sorting -- nor to C.

    --
    Eric Sosman
    lid
     
    Eric Sosman, Sep 18, 2007
    #10
  11. "Gordon Burditt" <> a écrit dans le message de
    news: ...
    > >Is there anybody still taking bubblesort seriously? Isn't it just a
    >>teaching toy?

    >
    > It isn't that terrible if the number of items to sort is 3 or fewer.
    >
    >>No, I'm told that it predates selection sort and insertion
    >>sort... But I still can't imagine how anybody could come up with something
    >>like that having serious purposes.

    >
    > Bubblesort is a reasonable auxiliary sorting method to use with
    > bogosort. Bogosort: You generate all possible orders of the data
    > to be sorted, count how many entries are out of sequence for each
    > order, then sort (using an auxiliary sorting method) the orders by
    > number of entries that are out of sequence, and take the smallest
    > one. The purpose of this is to change an algorithm that is n log
    > n in CPU time and n in memory to n! log n! in CPU time and n*n! in
    > memory. Bogosort is not used much outside of "cost plus" contracts.
    >
    > A first-level bogosort uses some other algorithm (e.g. bubblesort)
    > as an auxiliary sorting method. An Nth-level (N > 1) bogosort uses a
    > (N-1)th level bogosort as an auxiliary sorting method.


    What a nice suggestion for our Fortune 500 coder ;-)

    --
    Chqrlie.
     
    Charlie Gordon, Sep 18, 2007
    #11
    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. CrazyCube
    Replies:
    1
    Views:
    395
    Kevin Spencer
    Oct 22, 2004
  2. Peter

    design experiment?

    Peter, Feb 22, 2005, in forum: Java
    Replies:
    4
    Views:
    364
    Chris Uppal
    Feb 23, 2005
  3. Richard
    Replies:
    17
    Views:
    616
    The Farkinator
    Oct 15, 2003
  4. dmitrey
    Replies:
    0
    Views:
    150
    dmitrey
    Oct 24, 2011
  5. Replies:
    9
    Views:
    182
Loading...

Share This Page