|
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!!  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. 
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()
{
int [] allValues = {33,12,10,4,16,44};
bubble_sort(allValues,true);
TestArray(allValues);
int [] moreValues = {100,88,38,53,14,55,40,7,2};
bubble_sort(moreValues, true);
TestArray(moreValues);
int [] presortedValues = {5,17,33,59,72,73,74,75,76,88,99,100};
bubble_sort(presortedValues, true);
TestArray(presortedValues);
}
void TestArray(int [] allValues){
Console.WriteLine("############## OUTPUT #################");
Console.Write("SORTED ===> ");
foreach (int i in allValues){
Console.Write($"{i} ");
}
Console.WriteLine();
Console.WriteLine("#######################################");
Console.WriteLine();
}Output Shown With Steps
// Each Test array is shown with its steps so you can see how inefficient the bubble sort algo is.
12 10 4 16 33 ## Step 1 ##
10 4 12 16 33 ## Step 2 ##
4 10 12 16 33 ## Step 3 ##
4 10 12 16 33 ## Step 4 ##
############## OUTPUT #################
SORTED ===> 4 10 12 16 33 44
#######################################
88 38 53 14 55 40 7 2 ## Step 1 ##
38 53 14 55 40 7 2 88 ## Step 2 ##
38 14 53 40 7 2 55 88 ## Step 3 ##
14 38 40 7 2 53 55 88 ## Step 4 ##
14 38 7 2 40 53 55 88 ## Step 5 ##
14 7 2 38 40 53 55 88 ## Step 6 ##
7 2 14 38 40 53 55 88 ## Step 7 ##
2 7 14 38 40 53 55 88 ## Step 8 ##
2 7 14 38 40 53 55 88 ## Step 9 ##
############## OUTPUT #################
SORTED ===> 2 7 14 38 40 53 55 88 100
#######################################
5 17 33 59 72 73 74 75 76 88 99 ## Step 1 ##
############## OUTPUT #################
SORTED ===> 5 17 33 59 72 73 74 75 76 88 99 100
#######################################
|
|
|
|
|
|
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. 
|
|
|
|
|
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.
|
|
|
|
|
Yeah, they start right up. That's how I like my algos.
You know, those little videos are actually quite interesting and it's good to think of my data as dancing 
|
|
|
|
|
raddevus wrote: Everything has been done on the Internet.
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.
|
|
|
|
|
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. 
|
|
|
|
|
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.
|
|
|
|
|
That is... Brilliant!
|
|
|
|
|
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 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
|
|
|
|
|
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.
|
|
|
|
|
|
Amarnath S wrote: Visualisation right here[^] and here[^] on CP
Oh yeah, those are great ones. Thanks for pointing those out.
|
|
|
|
|
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.
|
|
|
|
|
|
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.
|
|
|
|
|
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.
modified 30-Jan-20 15:22pm.
|
|
|
|
|
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.
|
|
|
|
|
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.
|
|
|
|
|
I 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
|
|
|
|
|
During the holiday downtime last week I finally took the time to install a Let's Encrypt cert on the company's self-hosted web server. Because I'm impatient and not willing to wait hours for a txt record to propagate, I used the simple challenge test for a single named server. (wildcards require the txt method for verification) The cert was created for the canonical server name meaning that requests with the www prepended failed.
No problem, just add a couple of new url rewrite rules, one to remove the www. and the other to redirect to force https. It worked like a charm...or so I thought.
A week goes by without any reported problems until a customer goes to renew their contract. (desktop app) That's when all hell broke loose.  The desktop app sends a request to a registration web app hosted on that server that takes the querystring params and sends back a response indicating if the account is in good standing. This has worked well for many, many years so I was surprised when it started misbehaving. The problem turned out to be the querystring params were doubling. 
This was happening as a result of the url rewrite even though I had included the option to not append the querystring.  This was a problem due to the way multiple querystring paramaters with the same name are handled...basically, resource.aspx?sID=2&sID=2 resolves to '2,2'. Try parsing that to an int! (also, another reason to use TryParse vs. Parse)
Now, while that webpage/app was throwing a 500, the client-side app that was calling it became aware that an error had occurred and re-requested the page. It was only supposed to retry a maximum of 10 times before quitting...however, a line of code that made the request was mistakenly left right before the quit condition....  ...so, no matter what the fail counter said, it was going to keep trying...at least until the short variable hit it's limit!
This resulted in an unresponsive app for the client that had to be killed manually as well as a royal mess in the server's WC3 log.
Since this webserver is also used by other customers, I had to resort to handling the double parameters in the registration web app until after hours when I could correct the url rewrite rule. (use {URL} instead of {REQUEST_URI} in the redirect) In all, I had around a dozen different apps to fix on the server plus fixing and redeploying the desktop app. 
I was a bit surprised to realize that IIS's auto-ban had not kicked in until I discovered that it was not enabled. I could've sworn I enabled that a while back ...maybe that was the old server. (at least 2 years ago)
"Go forth into the source" - Neal Morse
|
|
|
|
|
Fun or what.
Services, with people using them, and expecting better.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
