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

Commita5b9363

Browse files
committed
swap function using ES6 destructuring
1 parent65c44f4 commita5b9363

File tree

5 files changed

+240
-26
lines changed

5 files changed

+240
-26
lines changed

‎Sorting/bubble-sort-basic-FUTURE-REFERENCE.js

Lines changed: 15 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -2,12 +2,21 @@ let arr = Array.from({ length: 20}, () => Math.floor(Math.random() * 20))
22
// console.log(arr);
33
vararray1=[9,2,5,6,4,3,7,10,1,8];
44

5-
// swap helper function
6-
swap=(arr,i,j)=>{
7-
lettemp=arr[i];
8-
arr[i]=arr[j];
9-
arr[j]=temp;
10-
}
5+
// swap helper function - good old version
6+
7+
// swap = (arr, i, j) => {
8+
// let temp = arr[i];
9+
// arr[i] = arr[j];
10+
// arr[j] = temp;
11+
// }
12+
13+
/* Swap helper function using array destructuring, which is a way of initializing variables at once. So, the below code
14+
var [x, y] = ['a', 'b']; is the same as doing the following
15+
var x = 'a';
16+
var y = 'b';
17+
Book- Learning JavaScript Data Structures and Algorithms.pdf // page-40 */
18+
19+
swap=(arr,i,j)=>[arr[i],arr[j]]=[arr[j],arr[i]]
1120

1221
// 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.
1322

‎Sorting/insertion-sort-part-1.js

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
/* https://www.hackerrank.com/challenges/insertionsort1/problem
2+
3+
Insert element into sorted list
4+
Given a sorted list with an unsorted number in the rightmost cell, can you write some simple code to insert into the array so that it remains sorted?
5+
6+
Assume you are given the array [ 1, 2, 4, 5, 3 ] indexed 0...4 Store the value of arr[4] . Now test lower index values successively from 3 to 0 until you reach a value that is lower than arr[4] , arr[1] in this case. Each time your test fails, copy the value at the lower index to the current index and print your array. When the next lower indexed value is smaller than arr[4], insert the stored value at the current index and print the entire array.
7+
8+
The results of operations on the example array is:
9+
10+
Starting array:
11+
Store the value of Do the tests and print interim results:
12+
13+
1 2 4 5 5
14+
1 2 4 4 5
15+
1 2 3 4 5
16+
17+
There will be two lines of input:
18+
19+
The first line contains the integer , the size of the array
20+
The next line contains space-separated integers
21+
22+
Print the array as a row of space-separated integers each time there is a shift or insertion.
23+
24+
Sample Input
25+
26+
5
27+
2 4 6 8 3
28+
29+
Sample Output
30+
31+
2 4 6 8 8
32+
2 4 6 6 8
33+
2 4 4 6 8
34+
2 3 4 6 8
35+
36+
Explanation
37+
38+
is removed from the end of the array.
39+
In the st line , so is shifted one cell to the right.
40+
In the nd line , so is shifted one cell to the right.
41+
In the rd line , so is shifted one cell to the right.
42+
In the th line , so is placed at position . */
43+
44+
insertionSort1=(n,arr)=>{
45+
46+
letrightEndNum=arr[n-1];
47+
letplaced=false;
48+
49+
for(leti=n-2;i>=0;i--){
50+
51+
if(arr[i]>rightEndNum){
52+
arr[i+1]=arr[i];
53+
console.log(arr.join(' '));
54+
}else{
55+
arr[i+1]=rightEndNum;
56+
console.log(arr.join(' '));
57+
placed=true;
58+
break;
59+
}
60+
}
61+
// While with the above code, I will get the expected result from the sample input, but in HR was failing one test. Because I have not taken care of the case when the rightEndNum is smaller than all the previous numbers, and hence will not be placed anywhere while running the above if loop. Hence the significane of the 'placed' variable, which will be turned to true as soon as I can place. And after the for loop, it still remains false, that means the rightEndNum is the lowest of all, and hence need to be placed at index[0]
62+
63+
if(!placed){
64+
arr[0]=rightEndNum
65+
console.log(arr.join(' '));
66+
}
67+
68+
}
69+
70+
insertionSort1(5,[2,4,6,8,3]);
Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
// https://www.hackerrank.com/challenges/insertionsort2/problem - Read my notes in insertion-sort-part-2.js for the steps HR want us to follow to come to insertion sort - Accepted by HR
2+
3+
insertionSort2=(n,arr)=>{
4+
5+
for(leti=1;i<n;i++){
6+
for(letj=0;j<i;j++){
7+
8+
if(arr[i]<arr[j]){
9+
// just swap arr[i] and arr[j] by the standard technique of bitwise XOR
10+
arr[i]^=arr[j];
11+
arr[j]^=arr[i]
12+
arr[i]^=arr[j]
13+
}
14+
}
15+
console.log(arr.join(" "));
16+
}
17+
}
18+
19+
insertionSort2(6,[1,4,3,5,6,2]);
20+
21+
/* Explanation to swap 2 numbers with bitwise XOR operator -
22+
23+
function swapNumberXOR(a, b) {
24+
console.log('before swap: ', 'a: ', a, 'b: ', b);
25+
a ^= b;
26+
b ^= a;
27+
a ^= b;
28+
console.log('after swap: ', 'a: ', a, 'b: ', b);
29+
}
30+
31+
// console.log((2).toString(2)); // => 10
32+
33+
// console.log((4).toString(2)); // => 100
34+
35+
// swapNumberXOR(2, 4);
36+
37+
/* Output -
38+
before swap: a: 2 b: 4
39+
after swap: a: 4 b: 2
40+
*/
41+
42+
43+
44+
/*Explanation of swapNumberXOR()
45+
46+
A> https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators#Bitwise_XOR - Performs the XOR operation on each pair of bits. a XOR b yields 1 if a and b are different. Returns a one in each bit position for which the corresponding bits of either but not both operands are ones.
47+
48+
B> XOR converts their operands to 32-bit integers (i.e. zeroes and ones), then perform their operations on such binary representations
49+
50+
C> So in the above example - 2 and 4 in binary representation are 10 (which is same as 010) and 100 respectively. So a ^ b means 010 ^ 100 ie.
51+
52+
( 0 ^ 1 ) for first position then - outputting 1
53+
54+
( 1 ^ 0 ) for second position and - - outputting 1
55+
56+
( 0 ^ 0 ) for the third position. - - outputting 0
57+
58+
Which gives the resultant output as "1 1 0" .
59+
60+
So the line a ^= b means a = a
61+
62+
So with the line of code a ^= b , I am assigning a's value to be "110" which is the decimal 6.
63+
64+
Then With the next line ( b^= a ) means 4 ^ 6 i.e. ( 100 ^ 110 ) giving me 010 which is 2
65+
66+
And then finally with (a ^= b ) means 6 ^ 2 ie. ( 110 ^ 010) giving me 100 which 4.
67+
68+
*/

‎Sorting/insertion-sort-part-2.js

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
/* https://www.hackerrank.com/challenges/insertionsort2/problem
2+
3+
In this challenge, print the array after each iteration of the insertion sort, i.e., whenever the next element has been inserted at its correct position. Since the array composed of just the first element is already sorted, begin printing after placing the second element.
4+
5+
Sample Input
6+
7+
6
8+
1 4 3 5 6 2
9+
Sample Output
10+
11+
1 4 3 5 6 2
12+
1 3 4 5 6 2
13+
1 3 4 5 6 2
14+
1 3 4 5 6 2
15+
1 2 3 4 5 6
16+
17+
18+
Skip testing at position 0 (i.e. number 1) against itself . It is already sorted.
19+
20+
Test position 1 (ie. no 4) against position 0 : 4 > 1 , no more to check, no change.
21+
Print arr
22+
23+
Test position 2 (ie. 3) against positions 1 and 0:
24+
25+
- 3 < 4, new position may be 1. Keep checking.
26+
- 3 > 1, so insert 3 at position 1 and move others to the right.
27+
Print arr
28+
29+
Test position 3 (ie 5 ) against positions 2, 1, 0 (as necessary): no change.
30+
Print arr
31+
32+
Test position 4 (ie. 6) against positions 3, 2, 1, 0 : no change.
33+
Print arr
34+
35+
Test position 5 (i.e. 2) against positions 4, 3, 2, 1, 0, insert 2 at position 1 and move others to the right.
36+
Print arr
37+
38+
*/
39+
40+
/* My Note - A> I am effectively re-writing ( ** by inserting each elements in its right place ** ) the whole array, by doing an insertion at each iteraion loop of j
41+
B> With each loop, if the (i+1)-th element is > (i)-th element, then just do a replacement code with < arr[j] = currentRightEnding; >
42+
43+
*/
44+
45+
insertionSort2=(n,arr)=>{
46+
47+
// start looping through the array. But while I am staring the loop at i=0, but will start all the comparisons from i= i + 1. And also, i < n - 1 because, (n-1)-th element will be the last right ending element and that I am taking care of by doing[i + 1] at each iteration loop
48+
for(leti=0;i<n-1;i++){
49+
50+
// Set the current right-end element from which to start the comparisons towards left all the way upto i=0
51+
letcurrentRightEnding=parseInt(arr[i+1]);
52+
53+
// This next comparison loop will start from i+1 and go leftwards. With this loop, for each value of outer for loop (i.e. each i ) - I am comparing 2 values and placing them in right place - the (i + 1)-th value and i-th value.
54+
// Note, I am using var (not let) because, with let, I will not be able to access 'j' after the for loop when 'j' goes to -1
55+
for(varj=i+1;j>=0;j--){
56+
// console.log("the value of j is " + j);
57+
58+
// Because, I have to compare with all the left elements starting from j-1 all the way upto 0. So, to start the comparison between each 2 sets of elements, first make the current j-index position to temporarily take the value of j-1-th index-position value. Only then do comparison.
59+
arr[j]=parseInt(arr[j-1])
60+
61+
if(currentRightEnding>=arr[j]){
62+
// Replace j-th position, ie. this position with that higher value of currentRightEnding. This code effectively replacing the whole array, by inserting the higher element at the j-th (i.e. (i + 1)-th ) position.
63+
arr[j]=currentRightEnding;
64+
break;
65+
}
66+
}
67+
console.log("the value of j is "+j);
68+
69+
// But the above for loop will not take care of the case, when smallest no is at the right most position of the original unsorted array. Because, the loop will only run upto (n - 1) and the max i value will be (n - 1 - 1) + 1. That is the upto index-5 when n=6 . But say for example the smallest no '1' is at the 5-th position - so this will be the value of 'currentRightEnding'. And when I do if (currentRightEnding >= arr[j]) it will fail. And so assignment of 1 to index (j-1) ie. index-0 will never happen. Hence, I have to take care of this with a separate loop. But at this point here, j has reached the value of -1 after the post-decrement from the last for loop iteration. So, its just an eazy single case, to assign arr[0] if and only I have a j=-1
70+
71+
// And j would hit -1, because, inside the for loop the value of j is being iterated through (i + 1) all the way down to 0 . So the last iteration loop makes j's value to 0
72+
73+
if(j===-1){
74+
// console.log("the value of j is " + j);
75+
arr[0]=currentRightEnding;
76+
}
77+
console.log(arr.join(" "));
78+
}
79+
}
80+
81+
insertionSort2(6,[1,4,3,5,6,2]);

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

Lines changed: 6 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -14,14 +14,15 @@ insertionSort = arr => {
1414
letarray=arr.slice(0);
1515

1616

17-
/* A> Here each time I find aff[i] < arr[j] I effectively have to swap the position of i and j.
17+
/*
18+
A> Here each time I find arr[i] < arr[j] I effectively have to swap the position of i and j.
1819
B> But instead of using a swap function, I returned a spliced array where the j-th position is replaced with i-th position.
1920
2021
C> Note, < arr.splice(j, 0, 'item') > means that at j-th position I am placing the element 'item' while removing zero element from the array.
2122
2223
AND remember array.splice() MUTATES THE ORIGINAL ARRAY AND RETURN THAT MUTATED ARRAY
2324
24-
D> And < arr.splice(i, 1)[0] > will delete 1 element at i-th position and return an array containing deleted element. HenceI am getting that deleted element by using 0-index position with [0]
25+
D> And < arr.splice(i, 1)[0] > will delete 1 element at i-th position and return an array containing deleted element. Hencethe [0] part will just give me that deleted element.
2526
2627
This is how the splice is working here -
2728
@@ -39,13 +40,11 @@ myArr.splice(0, 0, myArr.splice(1, 1)[0]);
3940
4041
console.log(myArr); // => [ 1, 2, 3, 4 ]
4142
42-
43-
44-
4543
*/
4644

4745
for(leti=0;i<array.length;i++){
48-
for(letj=1;j<i;j++){
46+
47+
for(letj=0;j<arr.length;j++){
4948

5049
if(array[i]<array[j]){
5150
array.splice(j,0,array.splice(i,1)[0])
@@ -57,18 +56,5 @@ console.log(myArr); // => [ 1, 2, 3, 4 ]
5756
}
5857

5958
constlist=[54,26,93,17,77,31,44,55,20]
60-
console.log(insertionSort(list));
61-
62-
// [ 17, 20, 26, 31, 44, 54, 55, 77, 93 ]
6359

64-
/* for (let i = 1; i < array.length; i++ ) {
65-
for ( let j = 0; j < i; j++ ) {
66-
67-
if ( array[i] < array[j] ) {
68-
array.splice( j, 0, array.splice(i, 1)[0] )
69-
break;
70-
}
71-
}
72-
}
73-
return array;
74-
} */
60+
console.log(insertionSort(list));// => [ 17, 20, 26, 31, 44, 54, 55, 77, 93 ]

0 commit comments

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