MESSAGE
| DATE | 2008-07-23 |
| FROM | Ruben Safir
|
| SUBJECT | Subject: [NYLXS - HANGOUT] C Programming Workshop
|
Taking a slight detour from the C programming efforts to this point
I'd like to present a rather famous allorithm, the Bubble Sort.
Sorting is one of the biggest things that programmers need to do and it
is often very CPU intenssive work. While writing the core for the
C++ workshop, i had the oppurtunity to right from memory a bubble sort
as one of the API's for the IntArray class.
I, of course, wrote it wrong and had to refresh my memory about this
important algorithm. So I cooked up this bubble Sort which I believe
works, but has some inefficiencies that can be improved and we might
take some time discussing sorting in C and means to improve it (ignoring
for the time being C's internal library function qsort.
I came up with the following agorithm
#include
#include
int a[10] = {6,5,0,1,4,7,2,9,3,8};
int *x, y , *indx, *end;
int main(){
end = (a + 9);
for( indx = a; indx <= end; indx++){
for(x = a; x < end; x++){
if( *x > *(x + 1)){
y = *x;
*x = *(x + 1);
*(x + 1) = y;
}
}
}
for( x=a; x < (end + 1); x++)
printf ("%d \t", *x);
return 1;
}
The bubble sort generally has 2 for loops which perculates up the highest
values. The first loop keeps track of how many times it is needed
to run through an array and the inner loop switches the placement of
values in an array when they are found out of order.
I used pointer arrithmatic to conduct this sort. That should speed up
the sorting times since indexing through an array is faster that
incrementing an integer and then derefencing an array by element numbers.
This array has 10 mebers and starts in the position of 'a'. Since I user
a+1 to define the second place holder, we shouldn't go past the end of the
array hence last is a + 9 (not 10). Also I use a seperate pointer to
increment through the array, otherwise I think I mess up the meaning of a[]
itself because i redine the value of a with autoincrmentation.
I'd like to see ssome ideas to speed this even further.
Ruben
--
http://www.mrbrklyn.com - Interesting Stuff
http://www.nylxs.com - Leadership Development in Free Software
So many immigrant groups have swept through our town that Brooklyn, like Atlantis, reaches mythological proportions in the mind of the world - RI Safir 1998
http://fairuse.nylxs.com DRM is THEFT - We are the STAKEHOLDERS - RI Safir 2002
"Yeah - I write Free Software...so SUE ME"
"The tremendous problem we face is that we are becoming sharecroppers to our own cultural heritage -- we need the ability to participate in our own society."
"> I'm an engineer. I choose the best tool for the job, politics be damned.<
You must be a stupid engineer then, because politcs and technology have been attached at the hip since the 1st dynasty in Ancient Egypt. I guess you missed that one."
© Copyright for the Digital Millennium
|
|
