Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Sorting
Index -> General Programming
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
MihaiG




PostPosted: Sun Nov 27, 2005 10:47 am   Post subject: 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

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 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!
Sponsor
Sponsor
Sponsor
sponsor
bugzpodder




PostPosted: Mon Nov 28, 2005 10:45 am   Post subject: (No subject)

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




PostPosted: Tue Nov 29, 2005 10:38 am   Post subject: (No subject)

I have a tutorial on sorting in progress.
Otherwise, the algorithms mentioned are widely available on the net.
Display posts from previous:   
   Index -> General Programming
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 3 Posts ]
Jump to:   


Style:  
Search: