I am trying to figure out how sorts work because the program I am trying to write requires me to sort data based on a total score. Anyways here is the code. I thought about submiting it to the snippets but wanted to see what everyone thought about it.



the funning thing is when I first wrote this I could not figure out why it worked until I worte it out on paper.

That's good but now try to use inbuilt sort() function.

what you've written is called a bubble sort. it is called this because it will "bubble" values towards the end of the list.

here's the generally accepted take on bubble sort

advantages:
easy to write
very little memory overhead

disadvantages:
not the most intuitive algorithm
terrible big-o of n^2, and an omega of n^2 as well

the big-o of n^2 cannot be solved, however, the omega can be if you make a few optimizations to the sort.

the first optimization that can be made is checking to see if swaps were made after each pass on the list. if no swaps were made, then the list is sorted, and no further passes are required.

the second optimization which can be made to the algorithm affects the internal for loop. if you have a list of size n, and the number of passes you have already made on the list, i, then, for every pass you make on the list, the n-i'th element will be placed properly in the list, and there is no need for the algorithm to look at that last item again. in your case, you will need to set the condition of the inner for loop to run from indexes 0 to 2-i.

after these optimizations have been made, the algorithm should have an omega of simply, n.

sorts that are similar to bubble sort, which you might be interested in looking into are insertion sort and selection sort

those sorts are more intuitive meaning they function more like a human would actually sort a list of numbers.

Thanks guys. That does help me understand sorts alot better. Xing I never knew that there was a built in sort. Course I have not got that far in my book. On pointers now which is probably another topic.

One last question guys. where can I find the functions for each class or .h file. I looked through a couple like istream but could not find the function cin or cout. I am using Dev-c++ 4.9.

This post has been edited by jstephens: 14 Dec, 2006 - 01:15 PM

Here is what I want to accomplish. I will build a structure that contains a horses PostID and a total score. I then need to sort them with highest totalscore first and lowest last. How would you guys do that. I am thinking about taking the above code and making it just change location in the array but I can't seem to figure it out. Especially now that I am trying to sort an array of structures.

Here is what the struct would look like.



Edit: Instead of a new post I thought I would make a quick edit. I figured out how to do it. I would just make the temp be a struct variable and because the sort is not a function I don't have to change the address. It will change it for me since I am not passing and values to a function. Just remembered the bit.

This post has been edited by jstephens: 14 Dec, 2006 - 02:26 PM