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

Commit17a8b6c

Browse files
committed
binary search standard simple solution
1 parent4470486 commit17a8b6c

5 files changed

+74
-13
lines changed

‎Search/binary-search-basic.js

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
// SOLUTION-1
2+
3+
binarySearch=(arr,value)=>{
4+
5+
letestimatedIndex,minIndex=0,maxIndex=arr.length-1;
6+
7+
while(minIndex<=maxIndex){
8+
9+
estimatedIndex=Math.floor((minIndex+maxIndex)/2);
10+
11+
if(arr[estimatedIndex]===value){
12+
returnestimatedIndex
13+
}
14+
elseif(arr[estimatedIndex]<value){
15+
// then start the next search from middle position towards right
16+
minIndex=estimatedIndex+1;
17+
}
18+
else{
19+
// i.e. the value is in the left half, so reduce the maxIndex to 1 less than the middle position
20+
maxIndex=estimatedIndex-1
21+
}
22+
}
23+
}
24+
25+
console.log(binarySearch([2,4,1,5],5));

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

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@ swap = (arr, i, j) => {
99
arr[j]=temp;
1010
}
1111

12-
// 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.
12+
//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.
1313

1414
bubbleSortBasicAscending=(arr)=>{
1515

@@ -39,7 +39,7 @@ bubbleSortBasicDescending = (arr) => {
3939

4040
console.log(bubbleSortBasicDescending(array1));
4141

42-
/* A more optimal solution, by reducing some of the loop execution are not done in this solution.
42+
/*SOLUTION - 2 -A more optimal solution, by reducing some of the loop execution are not done in this solution.
4343
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
4444
*/
4545
bubbleSortAscending=arr=>{

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

Lines changed: 44 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -14,17 +14,41 @@ 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.
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]
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+
20+
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.
21+
22+
AND remember array.splice() MUTATES THE ORIGINAL ARRAY AND RETURN THAT MUTATED ARRAY
23+
24+
D> And < arr.splice(i, 1)[0] > will delete 1 element at i-th position and return an array containing deleted element. Hence I am getting that deleted element by using 0-index position with [0]
25+
26+
This is how the splice is working here -
27+
28+
Pick-out (or return) the deleted element from the given array
29+
30+
let myArr1 = [ 2, 1, 3, 4]
31+
32+
console.log(myArr1.splice(1, 1)[0]); // => 1
33+
34+
Then replace the 0-index element with the third-argument in the .splice() method
35+
36+
let myArr = [ 2, 1, 3, 4]
37+
38+
myArr.splice(0, 0, myArr.splice(1, 1)[0]);
39+
40+
console.log(myArr); // => [ 1, 2, 3, 4 ]
41+
42+
43+
44+
2145
*/
2246

23-
for(leti=1;i<array.length;i++){
24-
for(letj=0;j<i;j++){
47+
for(leti=0;i<array.length;i++){
48+
for(letj=1;j<i;j++){
2549

2650
if(array[i]<array[j]){
27-
array.splice(j,0,array.splice(i,1)[0])
51+
array.splice(j,0,array.splice(i,1)[0])
2852
break;
2953
}
3054
}
@@ -35,4 +59,16 @@ insertionSort = arr => {
3559
constlist=[54,26,93,17,77,31,44,55,20]
3660
console.log(insertionSort(list));
3761

38-
// [ 17, 20, 26, 31, 44, 54, 55, 77, 93 ]
62+
// [ 17, 20, 26, 31, 44, 54, 55, 77, 93 ]
63+
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+
} */

‎Sorting/mergeSort-Basic-Recursive.jsrenamed to‎Sorting/mergeSort-Basic-Recursive-FUTURE-REFERENCE.js

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,8 @@
1-
// ROHAN'S NOTEIS TO REFERHEREIN FUTURE - Implementation of merge-sort algorithm, to sort an array of numbers in O(N×log(N)) time.
1+
// ROHAN'S NOTE HEREFOR FUTURE REFERENCE - Implementation of merge-sort algorithm, to sort an array of numbers in O(N×log(N)) time.
22

33
/* https://www.geeksforgeeks.org/merge-sort/
44
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. Themerge() 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.
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. Thehelper function merge2SortedArrays() 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.
66
77
MergeSort(arr[], l, r)
88
If r > l
@@ -24,7 +24,7 @@ A> The array is recursively divided in two halves till the size becomes 1.
2424
2525
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 .
2626
27-
C> So themerge() 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.
27+
C> So themerge2SortedArrays() 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.
2828
2929
merge( [1, 3, 5, 7 ] , [ 2, 4, 6, 8] ) >> will produce the below
3030

0 commit comments

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