Velocity Reviews > Trying Something New To Experiment with

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

--

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

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

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

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

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>

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

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

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.

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

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