-----------------------------------

MihaiG

Sun Nov 27, 2005 10:47 am


Sorting

-----------------------------------

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 


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 :wink: 

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

Mon Nov 28, 2005 10:45 am



-----------------------------------

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

Tue Nov 29, 2005 10:38 am



-----------------------------------

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