|
This guy has already been banned once for spamming - trying to promote his online courses.
|
|
|
|
|
I didn't know that. Thanks.
The article if he creates one won't get through then
No harm done I guess.
|
|
|
|
|
You can't, unless you are prepared to pay for proper advertising.
|
|
|
|
|
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.
|
|
|
|