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/insertion_sort-with-swap.js
+1-1Lines changed: 1 addition & 1 deletion
Original file line number
Diff line number
Diff line change
@@ -30,7 +30,7 @@ function insertion_sort(array) {
30
30
31
31
3. Compare new element in sorted array with previous elements to determine correct destination index in sorted array. Say I get 12, 11 as the second and third element. Since 11 is smaller than 12, move 12 and insert 11 before 12
32
32
33
-
4. In the below,at the last step, I had to decrement j by one, to stopthewhile loop. Because,with thedecremented value of j, in the next iteration of the loop, one of the while loop condition will fail
33
+
4. In the below,I have donetheinsertion operationwith theswap function.
// ROHAN'S NOTE IS TO REFER HERE IN FUTURE - Implementation of merge-sort algorithm, to sort an array of numbers in O(N×log(N)) time.
2
+
3
+
/* https://www.geeksforgeeks.org/merge-sort/
4
+
5
+
Like QuickSort, Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one. See following pseudo-code.
6
+
7
+
MergeSort(arr[], l, r)
8
+
If r > l
9
+
1. Find the middle point to divide the array into two halves:
10
+
middle m = (l+r)/2
11
+
2. Call mergeSort for first half:
12
+
Call mergeSort(arr, l, m)
13
+
3. Call mergeSort for second half:
14
+
Call mergeSort(arr, m+1, r)
15
+
4. Merge the two halves sorted in step 2 and 3:
16
+
Call merge(arr, l, m, r)
17
+
18
+
ANOTHER GOOD EXPLANATION - https://www.hackerearth.com/practice/algorithms/sorting/merge-sort/tutorial/
19
+
20
+
In other words - Merge sort is a divide-and-conquer algorithm based on the idea of breaking down a list into several sub-lists until each sublist consists of a single element and merging those sublists in a manner that results into a sorted list.
21
+
22
+
Steps implemented below :-
23
+
A> The array is recursively divided in two halves till the size becomes 1.
24
+
25
+
B> Once the size becomes 1, the merge processes comes into action, meaning I invoke the merge function on the 2 single-element arrays. That is, take adjacent pairs of two singleton lists, sort the elements of the 2 list, and merge them to form a list (ie array) of 2 elements .
26
+
27
+
C> So the merge() function below is a completely independent function and will just take 2 sorted-arrays ( the individual arrays MUST BE SORTED ), and then concat the elements to forma a single SORTED array. That is, within the merge() function before pushing the elements to the final result array (which will be the output from merge ) it checks for proper-sorting between the 2 elements on the 2 arrays.
28
+
29
+
merge( [1, 3, 5, 7 ] , [ 2, 4, 6, 8] ) >> will produce the below
30
+
31
+
[ 1, 2, 3, 4, 5, 6, 7, 8 ]
32
+
33
+
D) And then starts merging arrays back till the complete array is merged.
// Note, I am using post-increment syntax leftIndex++ . So the way it will work is, it will push the current leftIndex and only then it will increment it and pass that incremented value for the next iteration.
47
+
}
48
+
49
+
// And now I have to concat the left-over elements of the longer array. Because, the while loop will stop as soon as I have traversed all the sorter array's elements.