Bubble Sort, O(N^2) aka Quadratic time

raddevus

I'm reading the book, A Common-Sense Guide to Data Structures and Algorithms: Level Up Your Core Programming Skills[^] The book has some code samples in Ruby!! X| Argh! I converted the first one to C# for you. Although I'm sure most of you have written a bubble sort before and could do it blindfolded and typing only with your mouse. Of course, Bubble sort is slow and not a great algorithm. But now I understand why far better because of the book's explanation that it's O(N^2) -- runs in quadratic time. Large sets sorted this way will become extremely slow. And this nice graph from the book shows that too : https://i.stack.imgur.com/LPdjF.png[^] I'm quite excited to pull this stuff together into some understanding after many years of not quite being able to explain it. I know that is lame. :-O FYI if you get the Free LINQPad (LINQPad - The .NET Programmer's Playground[^]) you can copy the code below and run it easily.

void bubble_sort(int [] allValues, bool showIntermediateValues = false){
bool sorted = false;
int stepCounter = 0;
while (!sorted){
sorted = true;
for (int i = 0; i < allValues.Length-1;i++){
if (allValues[i] > allValues[i+1]){
sorted = false;
int currentVal = allValues[i];
allValues[i] = allValues[i+1];
allValues[i+1] = currentVal;
}
if (showIntermediateValues){
Console.Write($"{allValues[i]} ");
}
}
if (showIntermediateValues){
Console.WriteLine($" ## Step {++stepCounter} ##");
}
}
}

void Main()
{
// ##### Driving (main) program so you can see the algorithm in action #####
int [] allValues = {33,12,10,4,16,44};
bubble_sort(allValues,true);
// pri

Nelek

Just in case you want a graphical explanation: Bubble-sort with Hungarian ("Csángó") folk dance - YouTube[^] and others: Quick-sort with Hungarian (Küküllőmenti legényes) folk dance - YouTube[^] Merge-sort with Transylvanian-saxon (German) folk dance - YouTube[^] Insert-sort with Romanian folk dance - YouTube[^] Select-sort with Gypsy folk dance - YouTube[^] BINARY search with FLAMENCO dance - YouTube[^] and more generic and faster: 15 Sorting Algorithms in 6 Minutes - YouTube[^] I like this comparison too: Visualization and Comparison of Sorting Algorithms - YouTube[^]

M.D.V. ;) If something has a solution... Why do we have to worry about?. If it has no solution... For what reason do we have to worry about? Help me to understand what I'm saying, and I'll explain it better to you Rating helpful answers is nice, but saying thanks can be even nicer.

raddevus

Ok, so far, I watched the first one. It takes a long while for the sort to even start. Everything has been done on the Internet. :laugh:

Nelek

look the last two they are faster

M.D.V. ;) If something has a solution... Why do we have to worry about?. If it has no solution... For what reason do we have to worry about? Help me to understand what I'm saying, and I'll explain it better to you Rating helpful answers is nice, but saying thanks can be even nicer.

raddevus

Yeah, they start right up. That's how I like my algos. :laugh: You know, those little videos are actually quite interesting and it's good to think of my data as dancing :)

raddevus

Going thru chapter 5 of the book and I just rewrote the provided Selection Sort (from book's JavaScript example) as a C# example and examined it. After that I watched the selection sort dance :

Nelek wrote:

Select-sort with Gypsy folk dance - YouTube[^]

The dance really is interesting to see as you see the low value come out and dance with each one, but when the low value gets replaced, the new low value doesn't need to iterate over the other previous ones because it is lower than the previous low and thus lower than the ones that came before anyways. These dances really are quite instructive. :thumbsup:

Nelek

raddevus wrote:

These dances really are quite instructive.

Glad you like them :)

M.D.V. ;) If something has a solution... Why do we have to worry about?. If it has no solution... For what reason do we have to worry about? Help me to understand what I'm saying, and I'll explain it better to you Rating helpful answers is nice, but saying thanks can be even nicer.

Jon McKee

I think algorithm analysis is a pretty useful skill to pick up even if you just write "normal" code all day. Big O is the most commonly used but there's also Big Theta and Big Omega[^]. Also there's a cheat sheet [^] for all common data structures and sorting algorithms :thumbsup:

Amarnath S

Visualisation right here[^] and here[^] on CP.

raddevus

Jon McKee wrote:

I think algorithm analysis is a pretty useful skill to pick up even if you just write "normal" code all day

I agree now that this book has illuminated how it really applies so well. Thanks for the extra resources. I will check them out.

raddevus

Amarnath S wrote:

Visualisation right here[^] and here[^] on CP

Oh yeah, those are great ones. :thumbsup: Thanks for pointing those out.

maze3

Forgotten so many of the algorithms, but I am curious as to which might be bad in single thread but faster in concurrent processing? I don't recall it being something mentioned when I was taught these things at uni 2007?

raddevus

maze3 wrote:

but I am curious as to which might be bad in single thread but faster in concurrent processing? I don't recall it being something mentioned when I was taught these things at uni 2007?

Yes, I've been thinking the same thing. Now with concurrency at the forefront of everything some of these sorting algorithms would def be faster by splitting the set up into say three sets and allow 3 threads of concurrency to sort. However, as I'm writing that I see that you'd have to compile the sets and do the sort algo once more anyways. But I am with you on wondering which ones might be faster.

englebart

The statistics you should capture in your output is the number of comparisons and number of swaps performed for each case. In the domain of complex objects, the comparison is likely more expensive then swapping a reference/pointer. Classic bubble sort "back in the day" consisted of two for loops. I think this approach is O(N log N). Each inner iteration "bubbles" the min or max to the end of the list, so there is no reason to double check the constantly, moving last "bucket" on each iteration. The inner loop needs to run fewer iterations for each outer iteration.

for (int max = 0; max < length-1; ++max)
for (int i = 0; i < max; ++i) {
//
}

Combine this with your logic to stop if the list is in order and the number of comparisons should go down by log N. Careful of infinite loops with this type of structure! If this was written for a generic and someone passed in a poorly implemented operator> such that it returns: a > b ==> true b > a ==> true then this code would result in an infinite loop where it keeps swapping values.

agolddog

raddevus wrote:

Everything has been done on the Internet. :laugh:

That's right, and don't forget it. Also don't forget a lot of things are done poorly on the internet. It's great that you're interested enough to implement these things yourself in sample code, to ensure you understand the concepts, but don't reinvent the wheel in real code.

raddevus

agolddog wrote:

It's great that you're interested enough to implement these things yourself in sample code, to ensure you understand the concepts, but don't reinvent the wheel in real code.

Definitely agree. I'm on chapter 10 now where the book teaches quicksort and the value of recursion in this scope. The author also states :

Quote:

In previous chapters, we’ve encountered a number of sorting algorithms, including Bubble Sort, Selection Sort, and Insertion Sort. In real life, however, none of these methods are actually used to sort arrays. Most computer languages have built-in sorting functions for arrays that save us the time and effort from implementing our own. And in many of these languages, the sorting algorithm that is employed under the hood is Quicksort.

THis is why this is a really great book, because the author explicitly makes statements like that.

RugbyLeague

merge sort maybe?

Jon McKee

It's still O(n^2). What you're describing is a reduction in the coefficient of one of the terms; something Big-O doesn't measure but Big-Theta does. A logarithmic term requires recursive splitting of the input data such as divide and conquer approaches. Bubble sorts time is sum_{n to 1}(n) = (n(n - 1)/2) = 0.5n^2 - 0.5n = O(n^2). EDIT: Fixed a math error.

englebart

I see your point with the x(x+1)/2. Technically it might be (x-1)(x)/2 since it is one less, but the magnitude is still the same.

Kirk 10389821

Let me suggest that this was a VERY VERY important lesson to understand. It is the basis for comparing algorithms for appropriate speed (to the problem and data at hand). I chastised someone implementing a quicksort for < 100 items... (it was about 30 items, and would not be much larger, ever). It helped me to discover Hash Indexing. I Created one that was 70% waste (only 30% of the values ever matched, and had ZERO duplicates). But it was 2 bytes. Another programmer challenged it with a binary tree, because he did NOT understand the nature of the lookup speed. Finally, other algorithms that show you the importance of this: Calculate the Determinant of a square matrix. Write the code. It will look like a bubble sort. A 6x6 took 1 minute on my old computer, how long did the 7x7 take? 7 Minutes, I believe, the 8x8 was like 56 minutes (30yrs ago). Converting to an upper/lower triangular reduces the time so amazingly you laugh. I wrote this to test my homework answers in my theory of matrices class. Quickly reviewing the algorithm told the entire story. I stuck with that FOREVER. One lesson learned well... BTW, I LOVED the videos of the various sorts... It is a beautiful explanation of what is going on.