Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Trying Something New To Experiment with

Reply
Thread Tools

Trying Something New To Experiment with

 
 
joebenjamin
Guest
Posts: n/a
 
      09-17-2007

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

 
Reply With Quote
 
 
 
 
Army1987
Guest
Posts: n/a
 
      09-17-2007
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

 
Reply With Quote
 
 
 
 
Willem
Guest
Posts: n/a
 
      09-17-2007
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
 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      09-17-2007
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

 
Reply With Quote
 
pete
Guest
Posts: n/a
 
      09-17-2007
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
 
Reply With Quote
 
Tor Rustad
Guest
Posts: n/a
 
      09-17-2007
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>
 
Reply With Quote
 
pete
Guest
Posts: n/a
 
      09-17-2007
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/...ver/e_driver.c
http://www.mindspring.com/~pfilandr/C/e_driver/

--
pete
 
Reply With Quote
 
Gordon Burditt
Guest
Posts: n/a
 
      09-17-2007
>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.



 
Reply With Quote
 
pete
Guest
Posts: n/a
 
      09-17-2007
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
 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      09-18-2007
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.6 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
http://www.velocityreviews.com/forums/(E-Mail Removed)lid
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
[ANN] New free multifactor analysis tool for experiment planning dmitrey Python 0 10-24-2011 06:24 PM
var Something= new Something() What does it mean ? pamelafluente@libero.it Javascript 9 10-05-2006 02:43 PM
The Thumb Drive RAID Experiment Silverstrand Front Page News 0 12-30-2005 04:41 AM
The Underclocking Experiment Silverstrand Front Page News 0 12-26-2005 04:41 PM
Inconclusive result of a low-value experiment. Common cache Mozilla & Firefox. Splibbilla Firefox 0 05-30-2005 06:58 AM



Advertisments