My God, Bubble Sorts Suck!

[BDawg]

We're coving basic sorting in my visual basic course. Since I've covered this stuff before, I finished my project pretty quickly and decided to run a little test. I thought it would be kinda fun to compare a shell sort (not covered in this course) to a bubble sort (reccomended in our course) on a file of 30,000 records.

The shell sort finished in about 6 seconds. The bubble sort (which I know works, I tested it on a file of 5 records) is still chugging along after 20 minutes (I started at 4:47). How long should I wait before I just give up on the bubble sort?

 

[geno]

<--- just covered this in C 😛

 

[AmigaMan]

bubble sort is O(n^2) whereas shell sort is O(n/2). This is from www.nist.gov
More links: Shell Sort and BubbleSort

 

[Argo]

Somethign must be wrong. There is no way buble sort can be going on after 20 minutes on any decently fast machine. Were all the records read into memory first?

 

[BDawg]

Yeah, I covered the two when I took C in college too. But, I never did any real world experiments to see how much faster the extra pair comparisons take.

BTW, the bubble sort just finished a few minutes ago. It took a little over 21 minutes. 😀 I can only imagine what the results would be on a 486DX.

 

[BigJohnKC]

I don't recall learning shell sort, but bubble sort is notoriously slow.

 

[BDawg]

<< Somethign must be wrong. There is no way buble sort can be going on after 20 minutes on any decently fast machine. We all the records read into memory first? >>



Ida know...that's how long it took on my P3 1Ghz laptop. It has 256 MB Ram, so I would think they all (~314k) would be read into memory. I didn't really check for disk access though.