Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit1c3494c

Browse files
committed
insertion sort with splice and without using swap method
1 parent9d5ea28 commit1c3494c

File tree

5 files changed

+44
-33
lines changed

5 files changed

+44
-33
lines changed

‎Sorting/insertion-sort-with-splice.js

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
/* Algorithm -
2+
3+
A) Loop from i = 1 (second element of the array) to n-1.
4+
B) Pick element arr[i] and insert it into sorted sequence arr[0…i-1]
5+
C) Say I get 12, 11 as the second and third element. Since 11 is smaller than 12, move 12 and insert 11 before 12
6+
*/
7+
8+
insertionSort=arr=>{
9+
10+
if(!Array.isArray(arr)||arr.length<2){
11+
returnarr;
12+
}
13+
14+
letarray=arr.slice(0);
15+
16+
17+
/* A> Here each time I find aff[i] < arr[j] I effectively have to swap the position of i and j.
18+
B> But instead of using a swap function, I returned a spliced array where the j-th position is replaced with i-th position.
19+
C> Note, < arr.splice(j, 0, 'item') > means that at j-th position I am placing the 'item' and removing zero element.
20+
D> And < arr.splice(i, 1)[0] > will delete 1 element from i-th position and return and return an array containing deleted element. Hence I am getting that delete element by accessing [0]
21+
*/
22+
23+
for(leti=1;i<array.length;i++){
24+
for(letj=0;j<i;j++){
25+
26+
if(array[i]<array[j]){
27+
array.splice(j,0,array.splice(i,1)[0])
28+
break;
29+
}
30+
}
31+
}
32+
returnarray;
33+
}
34+
35+
constlist=[54,26,93,17,77,31,44,55,20]
36+
console.log(insertionSort(list));
37+
38+
// [ 17, 20, 26, 31, 44, 54, 55, 77, 93 ]

‎Sorting/insertion_sort.jsrenamed to‎Sorting/insertion_sort-with-swap.js

Lines changed: 6 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -24,9 +24,12 @@ function insertion_sort(array) {
2424
vari,j;
2525

2626
/*
27-
1. Assume first element is sorted
28-
2. Add first unsorted element to sorted array
29-
3. Compare new element in sorted array with previous elements to determine correct destination index in sorted array
27+
1. Assume first element is sorted. So, Loop from i = 1 (second element of the array) to n-1.
28+
29+
2. Add first unsorted element to sorted array.
30+
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+
3033
4. In the below, at the last step, I had to decrement j by one, to stop the while loop. Because, with the decremented value of j, in the next iteration of the loop, one of the while loop condition will fail
3134
*/
3235

‎Sorting/quick-sort-Lomuto.js

Lines changed: 0 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -41,34 +41,10 @@ function partitionLomuto(array, left, right) {
4141

4242
/******************* Testing Lomuto algorithm *********************/
4343

44-
functiongetRandomInt(min,max){
45-
returnMath.floor(Math.random()*(max-min+1))+min;
46-
}
47-
4844
letarr=Array.from({length :20},()=>Math.floor(Math.random()*20));
4945
console.log(arr);//printing unsorted array
5046

5147
arr=quicksortLomuto(arr,0,arr.length-1);
5248
console.log(arr);
5349

5450

55-
/* Explanation of < Math.floor(Math.random() * (max - min + 1)) + min >
56-
57-
By adding 1, I am making the maximum inclusive ( the minimum is inclusive anyway). Because, the Math.random() function returns a floating-point, pseudo-random number in the range from 0 inclusive up to but not including 1. the formula can generate the correct amount of numbers but they always start at 0 because the range from Math.random starts from 0. https://teamtreehouse.com/community/need-an-explanation
58-
59-
Math.random() returns a number from 0 to 1, not including one. Flooring this number will always result in a zero.
60-
61-
If you multiply this float by the max prior to flooring, you will get numbers all the way up to the maximum, including those below the minimum, but not the maximum itself. Say you have 10 as the maximum, you cannot get a 10.
62-
63-
In order to rule out those below the minimum, you subtract the minimum from the maximum. In order to include the maximum, you add one. This is all multiplied by the random floating point number between 0 and 1.
64-
65-
At that point, we aren't quite there. You will be receiving numbers based on the range between the minimum and maximum as explained above. Adding the minimum back in, post-randomizing, ensure that you have numbers that are between the minimum and the maximum.
66-
67-
TLDR: The range of numbers (i.e. the number of numbers between min and max) is defined by those within the floor method's parentheses. The minimum added at the end ensures these numbers are between the desired minimum and maximum.
68-
69-
By subtracting the minimum number from the maximum, you define the range. Say you have minimum of 5 and a maximum of 20, you will get the range of 15. There are 15 possible numbers that you could select at random between these bounds.
70-
71-
Paul-Note - So, if I dont add Min of 5, the formulae will give me all the random numbers between 0 and 15. But I want between 5 and 20. So thats why I add back the min.
72-
73-
Another great visual explanation at - https://stackoverflow.com/questions/1527803/generating-random-whole-numbers-in-javascript-in-a-specific-range
74-
*/

‎Sorting/quick-sort-basic-recursion.js

Lines changed: 0 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -33,12 +33,6 @@ function quickSortBasic(array) {
3333

3434
/******************* Testing Quick sort algorithm *********************/
3535

36-
// Returns a random integer between min (inclusive) and max (inclusive). Using Math.round() will give a non-uniform distribution, which we dont want in this case.
37-
38-
functiongetRandomInt(min,max){
39-
returnMath.floor(Math.random()*(max-min+1))+min;
40-
}
41-
4236
letarr=Array.from({length :20},()=>Math.floor(Math.random()*20));
4337

4438
console.log(arr);//printing unsorted array

‎Sorting/quick-sort-iterative.js

Whitespace-only changes.

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp