You signed in with another tab or window.Reload to refresh your session.You signed out in another tab or window.Reload to refresh your session.You switched accounts on another tab or window.Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: Sorting/bubble-sort-basic-FUTURE-REFERENCE.js
+39-2Lines changed: 39 additions & 2 deletions
Original file line number
Diff line number
Diff line change
@@ -1,5 +1,20 @@
1
1
/* When people first start learning sorting algorithms, they usually learn the bubble sort algorithm first, because it is the simplest of all the sorting algorithms. However, it is one of the worst-case sorting algorithms with respect to runtime. The bubble sort algorithm compares every two adjacent items and swaps them if the first one is bigger than the second one. It has this name because the items tend to move up into the correct order, like bubbles rising to the surface.
2
-
*/
2
+
bubble-sort should not be used for larger arrays, can be used for smaller ones for its simplicity.
3
+
4
+
5
+
MOST IMPORTANT POINT OF BUBBLE SORT (And base of my solution SOLUTION-3 ) :-
6
+
7
+
A> After the whole first pass is done, (i.e. after the first for loop for i = 0 is run , which also means, for each of i = 0 all the values of the nested for loop for j = 0 to j = arr.length - 1 is run) - The
8
+
9
+
See this for pictorial representation - http://codingmiles.com/sorting-algorithms-bubble-sort-using-javascript/
10
+
11
+
B> In other words, after the first pass, the biggest elements is placed at its correct position.
12
+
13
+
C) And this IS THE PRINCIPLE BASED ON WHICH I CAN IMPROVE THE ALGO BY REDUCING THE NO OF PASSES FOR THE INNER NESTED FOR LOOP EACH TIME - Meaning, for the second loop of i = 1 pass, I actually no more have to compare the right-most element. As I know the right-most element is the biggest and has been placed at its correct right-most position.
14
+
15
+
D) Then for for the next loop i=2, I can reduce the no of comarison for the nested for loop by 2, because I know, that the biggest 2 element has already been placed to the farthest right side.
// Now the same solution but starting the nested loop from 0-th index instead of 1 (as above) and going upto (arr.length - 1) instead of arr.length. And so the previous solution, I was comparing < if (arr[j] < arr[j - 1]) > and here I shall compare arr[j + 1] < arr[j] . And thats why I am running the loop upto (arr.length - 1) because inside I will take care of the element arr[j+1]
56
+
// Learning JavaScript Data Structures and Algorithms-Loiane.pdf - Page - 225
/* SOLUTION - 2 - A more optimal solution, by reducing some of the loop execution.
71
87
So, here, I only do the loops and swaps for the cases when I find a mis-placed element, i.e. larger-element placed before smaller in an ascending sort
72
88
So, here, I traverse the array only once. And only the first time, I find a mis-placed element, that is I do an actual swap, do I make that variable 'swap' to be true.
89
+
90
+
And each time there's something to swap the do-while loop will continue, and the moment the whole array is sorted, and there's nothing more to sort the do-while loop will no more execute.
/* SOLUTION-3 - Although complexity is still O(n^2). If we subtract the number of passes from the inner loop, we will avoid all the unnecessary comparisons made by the inner loop. So the idea is, for second nested loop when j = 1, I running it one less pass.
111
+
112
+
Even though we made this small change to improve the bubble sort algorithm a little bit, it is not a recommended algorithm. It has a complexity of O(n2).
113
+
114
+
Learning JavaScript Data Structures and Algorithms-Loiane.pdf - Page - 228