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

Commitfab2f15

Browse files
committed
quick sort
1 parentaf188ca commitfab2f15

File tree

3 files changed

+187
-0
lines changed

3 files changed

+187
-0
lines changed

‎Sorting/quick-sort-Hoare.js

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
// First write the swap function, which is just a helper function to swap values of the array.
2+
functionswap(array,i,j){
3+
vartemp=array[i];
4+
array[i]=array[j];
5+
array[j]=temp;
6+
}
7+
8+
functionquicksortHoare(array,left,right){
9+
// left-pointer would be the index of the first element which is 0 and right-pointer would be the index of the last element which would be (length -1).
10+
left=left||0;
11+
right=right||array.length-1;
12+
13+
varpivot=partitionHoare(array,left,right);
14+
15+
if(left<pivot-1){
16+
quicksortHoare(array,left,pivot-1);
17+
}
18+
19+
if(right>pivot){
20+
quicksortHoare(array,pivot,right)
21+
}
22+
23+
returnarray;
24+
25+
}
26+
27+
/* Two indices that start at the ends of the array being partitioned, then move toward each other, until they detect an inversion: a pair of elements, one greater than the pivot, one smaller, that are in the wrong order relative to each other. The inverted elements are then swapped.
28+
Here the numerical values of left and right is continually getting updated with each inner while loop. But only if the while loop condition gets satisfied. That is, when the while loop condition is unsatisfied, e.g. for the first inner while loop, when array[left] > array[pivot] which means we have found a misplaced pair.
29+
30+
That is, although the left <= right (which is being made sure by the outer while loop) the actual elements are not sorted. Meaning a left side element is larger in value than the right side element. So, the code execution then jumps out of the inner while loop and goes right in to execute the swap function.
31+
*/
32+
functionpartitionHoare(array,left,right){
33+
varpivot=Math.floor((left+right)/2);
34+
35+
while(left<right){
36+
while(array[left]<array[pivot]){
37+
left++
38+
}
39+
while(array[right]>array[pivot]){
40+
right--
41+
}
42+
43+
if(left<=right){
44+
swap(array,left,right);
45+
left++
46+
right--
47+
}
48+
}
49+
returnleft;
50+
}
51+
52+
53+
54+
/******************* Testing Hoare algorithm *********************/
55+
56+
functiongetRandomInt(min,max){
57+
returnMath.floor(Math.random()*(max-min+1))+min;
58+
// 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
59+
}
60+
61+
vararr=[];
62+
63+
for(vari=0;i<10;i++){//initialize a random integer unsorted array
64+
arr.push(getRandomInt(1,100));
65+
}
66+
67+
console.log("Unsorted array: ");
68+
console.log(arr);//printing unsorted array
69+
70+
arr=quicksortHoare(arr,0,arr.length-1);
71+
console.log("Sorted array: ");
72+
console.log(arr);

‎Sorting/quick-sort-Lomuto.js

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
// First write the swap function, which is just a helper function to swap values of the array.
2+
functionswap(array,i,j){
3+
vartemp=array[i];
4+
array[i]=array[j];
5+
array[j]=temp;
6+
}
7+
8+
functionquicksortLomuto(array,left,right){
9+
// left-pointer would be the index of the first element which is 0 and right-pointer would be the index of the last element which would be (length -1).
10+
left=left||0;
11+
right=right||array.length-1;
12+
13+
varpivot=partitionLomuto(array,left,right);
14+
15+
if(left<pivot-1){
16+
quicksortLomuto(array,left,pivot-1);
17+
}
18+
19+
if(right>pivot){
20+
quicksortLomuto(array,pivot-1,right)
21+
}
22+
23+
returnarray;
24+
}
25+
26+
functionpartitionLomuto(array,left,right){
27+
// Lomuto algorithm always uses the last element, array[right], for the pivot.
28+
varpivot=right;
29+
vari=left;
30+
31+
/*The logic under Lomuto is, we start from the leftmost element and keep track of index of smaller (or equal to) elements as j. While traversing, if we find a smaller element, we swap current element with arr[j]. Otherwise we ignore current element.*/
32+
for(varj=left;j<right;j++){
33+
if(array[j]<=array[pivot]){
34+
swap(array,i,j);
35+
i++
36+
}
37+
}
38+
swap(array,i,j);
39+
returni;
40+
}
41+
42+
/******************* Testing Lomuto algorithm *********************/
43+
44+
functiongetRandomInt(min,max){
45+
returnMath.floor(Math.random()*(max-min+1))+min;
46+
// 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
47+
}
48+
49+
vararr=[];
50+
51+
for(vari=0;i<10;i++){//initialize a random integer unsorted array
52+
arr.push(getRandomInt(1,100));
53+
}
54+
55+
console.log("Unsorted array: ");
56+
console.log(arr);//printing unsorted array
57+
58+
arr=quicksortLomuto(arr,0,arr.length-1);
59+
console.log("Sorted array: ");
60+
console.log(arr);

‎Sorting/quick-sort-basic.js

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
// sorting the below array with quick sorting
2+
3+
/*The algorithm for Quicksort is:
4+
1. Pick a pivot element that divides the list into two sublists.
5+
6+
2. Reorder the list so that all elements less than the pivot element are placed before
7+
the pivot and all elements greater than the pivot are placed after it.
8+
9+
3. Repeat steps 1 and 2 on both the list with smaller elements and the list of larger
10+
elements.*/
11+
12+
// basic implementation, where pivot is the first element, without usuing swap function and partition function.
13+
14+
functionquickSortBasic(array){
15+
if(array.length<2){
16+
returnarray;
17+
}
18+
19+
varpivot=array[0];
20+
varlesserArray=[];
21+
vargreaterArray=[];
22+
23+
for(vari=1;i<array.length;i++){
24+
if(array[i]>pivot){
25+
greaterArray.push(array[i]);
26+
}else{
27+
lesserArray.push(array[i]);
28+
}
29+
}
30+
31+
returnquickSortBasic(lesserArray).concat(pivot,quickSortBasic(greaterArray));
32+
}
33+
34+
35+
/******************* Testing Quick sort algorithm *********************/
36+
37+
// 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.
38+
39+
functiongetRandomInt(min,max){
40+
returnMath.floor(Math.random()*(max-min+1))+min;
41+
// 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
42+
}
43+
44+
vararr=[];
45+
46+
for(vari=0;i<10;i++){//initialize a random integer unsorted array
47+
arr.push(getRandomInt(1,100));
48+
}
49+
50+
console.log("Unsorted array: ");
51+
console.log(arr);//printing unsorted array
52+
53+
arr=quickSortBasic(arr,0,arr.length-1);
54+
console.log("Sorted array: ");
55+
console.log(arr);

0 commit comments

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