Sorting

[MihaiG]

many programmers have problems with sorting large amounts of data...but is there really an easy way


Bubble Sorting-

bubble sorting seems to be the easiest way to sort out a large amount of data but is also the most inefficient..

problem:

Make a bubble sorting program for the following text file with 1000 numbers (1-100)


how:

buble sorting works on he basis of

code:

a being ur first number in the set b being the second c being a helper variable so u compare a < b,a>b, a=b if a is smaller than the second ...thats ok...so we leave it if a is larger than b....we know b must go first then... but how do we switch it? here come our helper variable c so u assign b - c...then a-b then b-a and everything switched nice and easy....

but how efficient is our code? how do we find out?


well that easy

for every "swap" occuring u increase a counter and you have how many swaps occured....

usualy thats as low as u can get for bubble sorting..

here comes the tricky part...

for every compare u do ur counter increases by 1

ie.

if u have an if statement that has the following if
a < b,a>b, a=b

u cant increase te counter for each by 1.....!

for the first u increase it by 1..

for the second u increase by 2(rember u also compared it with the first and the second)

and forthe 3rd u increase it by 3!

there must be a more efficient way than this!


Contest:


to see who make the most efficient bubble sorting program with the least number of compares and swaps


no cheating...ppl will check ur code and u will be burned

heres my table for data

El Comandante-
Compares=496575
Swaps=248052


try and beat that.....rember u cant beat swaps unless ur not buble sorting!

[bugzpodder]

you said so yourself, bubble sort is very inefficient on large sets of data because it is an O(n^2) algorithm. so there is no reason for us to use it. stick with quicksort or bucket/radix/counting sort. they are not difficult and certainly within the reach of a highschool student.

[codemage]

I have a tutorial on sorting in progress.
Otherwise, the algorithms mentioned are widely available on the net.