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: Sort/BubbleSort/README.md
+2Lines changed: 2 additions & 0 deletions
Original file line number
Diff line number
Diff line change
@@ -18,6 +18,8 @@ A> After the whole first pass is done, (i.e. after the first for loop for i = 0
18
18
19
19
See this for pictorial representation -http://codingmiles.com/sorting-algorithms-bubble-sort-using-javascript/
20
20
21
+
So basically, the bubble sort algorithm can be easily optimized by observing that the n-th pass finds the n-th largest element and puts it into its final place. So, the inner loop can avoid looking at the last n − 1 items when running for the n-th time:
22
+
21
23
B> In other words, after the first pass, the biggest elements is placed at its correct position.
22
24
23
25
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.
// SOLUTION-1 - Necessary warning :) :) - this is a super basic implementation to understand the principle behind bubble sort (going through all comparisons) but there's huge room for performance improvement on this.
// 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]
37
+
//SOLUTION-2Now 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]
38
38
// Learning JavaScript Data Structures and Algorithms-Loiane.pdf - Page - 225
/* SOLUTION - 2 - A more optimal solution, by reducing some of the loop execution.
68
+
/* SOLUTION - 3 - A more optimal solution, by reducing some of the loop execution.
69
+
69
70
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
71
+
72
+
Remember the do-while syntax - the first do will execute anyway, but then the next while loop will ONLY execute if the condition of thw while is satisfied. In this case below, only after I find a mis-placed pair of elements, I flip 'swapped' to true. And only then while(swapped) gets satisfied > and only then the next while loop gets executed.
73
+
70
74
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.
71
75
72
76
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.
73
77
*/
74
-
bubbleSortAscending_Improved=arr=>{
75
78
76
-
// A flag that holds whether the swapping happened or not
77
-
letswapped=false;
79
+
bubbleSortAscending_Improved_3=arr=>{
80
+
81
+
// A flag that holds whether the swapping happened or not
82
+
varswapped=false;
83
+
84
+
do{
85
+
86
+
swapped=false;
87
+
88
+
for(leti=0;i<arr.length-1;i++){
89
+
90
+
if((arr[i]&&arr[i+1])&&(arr[i]>arr[i+1])){
91
+
92
+
swap(arr,i,i+1);
93
+
94
+
// register the swap
95
+
swapped=true;
96
+
}
97
+
}
98
+
}while(swapped)
99
+
100
+
returnarr;
101
+
}
102
+
103
+
// If there were no swaps then array is already sorted and there is no need to proceed.
104
+
// The way I check the above condition is if - reversed of swapped is true, that is !swapped === true. And because after each actual swap, I am turning swapped=true, so (!swapped)===true above can only happen if there was no swapping.
/* SOLUTION-4 - Same Implementation of the above with while loop - I need to loop continuously until a condition is met (no swaps happens i.e. 'swapped' is true).
110
+
Note, in the below I am setting 'swapped' back to false after each swapping, because ONLY THEN THE NEXT ITERATION OF THE WHILE LOOP CAN GET EXECUTED. BECAUSE ONLY THEN (!swapped) will be true, and the while loop condition will be satisfied.
/* 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.
135
+
/* SOLUTION-4 - 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.
94
136
95
137
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).
96
138
97
139
Learning JavaScript Data Structures and Algorithms-Loiane.pdf - Page - 228