Trying Something New To Experiment with

[joebenjamin]

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]

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.

 

[Willem]

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]

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.

 

[pete]

Is there anybody still taking bubblesort seriously?

He said "for fun".

Isn't it just a teaching toy?

That's also what he said.

 

[Tor Rustad]

He said "for fun".


That's also what he said.

It smelled like homework to me.

 

[pete]

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/

 

[Gordon Burditt]

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]

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


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

 

[Eric Sosman]

[...]
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.

 

[Charlie Gordon]

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


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