Bubble Sort, O(N^2) aka Quadratic time
-
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 -
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?
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.
-
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);
// priThe 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
forloops. 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.
-
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:
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 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.
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.
-
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.
merge sort maybe?
-
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
forloops. 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.
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.
-
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.
-
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);
// priLet 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.
-
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
