Bubble Sort, O(N^2) aka Quadratic time
-
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.
That is... Brilliant! :laugh:
Best, Sander sanderrossel.com Migrating Applications to the Cloud with Azure arrgh.js - Bringing LINQ to JavaScript Object-Oriented Programming in C# Succinctly
-
That is... Brilliant! :laugh:
Best, Sander sanderrossel.com Migrating Applications to the Cloud with Azure arrgh.js - Bringing LINQ to JavaScript Object-Oriented Programming in C# Succinctly
:laugh: :laugh:
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.
-
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);
// priI like the analyses and have studied how to compute the Big-O and Theta. I have also implemented every sorting algorithm I have ever seen (years ago). My only issue has been, how much brains does it require to understand that a loop inside a loop (the bubble) is not efficient. The rest is just proving that you are right. Of course, for school, you have to provide the reason you are right and that is actually part of the fun of learning. But in the real world, they tend to take it for granted that you can see the obvious without actually calculating the Big-O.
INTP "Program testing can be used to show the presence of bugs, but never to show their absence." - Edsger Dijkstra "I have never been lost, but I will admit to being confused for several weeks. " - Daniel Boone
