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

Commit30ae323

Browse files
committed
Do some code formatting on QuickSort algorithm.
1 parentbf5d7b3 commit30ae323

File tree

3 files changed

+42
-21
lines changed

3 files changed

+42
-21
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -78,7 +78,7 @@ a set of rules that precisely defines a sequence of operations.
7878
*[Insertion Sort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/insertion-sort)
7979
*[Heap Sort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/heap-sort)
8080
*[Merge Sort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/merge-sort)
81-
*[Quicksort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/quick-sort)
81+
*[Quicksort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/quick-sort) - in-place and non-in-place implementations
8282
*[Shellsort](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/shell-sort)
8383
***Tree**
8484
*[Depth-First Search](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/tree/depth-first-search) (DFS)

‎src/algorithms/sorting/quick-sort/QuickSort.js

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,10 @@
11
importSortfrom'../Sort';
22

33
exportdefaultclassQuickSortextendsSort{
4+
/**
5+
*@param {*[]} originalArray
6+
*@return {*[]}
7+
*/
48
sort(originalArray){
59
// Clone original array to prevent it from modification.
610
constarray=[...originalArray];
Lines changed: 37 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -1,35 +1,51 @@
11
importSortfrom'../Sort';
22

33
exportdefaultclassQuickSortInPlaceextendsSort{
4-
/* Sorting in place avoids unnecessary use of additional memory, but modifies input array.
4+
/** Sorting in place avoids unnecessary use of additional memory, but modifies input array.
55
*
66
* This process is difficult to describe, but much clearer with a visualization:
7-
* http://www.algomation.com/algorithm/quick-sort-visualization
7+
*@see: http://www.algomation.com/algorithm/quick-sort-visualization
8+
*
9+
*@param {*[]} originalArray
10+
*@param {number} inputLowIndex
11+
*@param {number} inputHighIndex
12+
*@return {*[]}
813
*/
9-
sort(originalArray,inputLow,inputHigh){
14+
sort(originalArray,inputLowIndex,inputHighIndex){
1015
// Destructures array on initial passthrough, and then sorts in place.
11-
constarray=inputLow===undefined ?[...originalArray] :originalArray;
12-
// Partition array segment and return index of last swap
13-
constpartition=(l,h)=>{
14-
constswap=(left,right)=>{
15-
consttempVariable=array[left];
16-
array[left]=array[right];
17-
array[right]=tempVariable;
16+
constarray=inputLowIndex===undefined ?[...originalArray] :originalArray;
17+
18+
/**
19+
* Partition array segment and return index of last swap
20+
*
21+
*@param {number} lowIndex
22+
*@param {number} highIndex
23+
*@return {number}
24+
*/
25+
constpartition=(lowIndex,highIndex)=>{
26+
/**
27+
*@param {number} leftIndex
28+
*@param {number} rightIndex
29+
*/
30+
constswap=(leftIndex,rightIndex)=>{
31+
consttempVariable=array[leftIndex];
32+
array[leftIndex]=array[rightIndex];
33+
array[rightIndex]=tempVariable;
1834
};
1935

20-
constpivot=array[h];
36+
constpivot=array[highIndex];
2137
this.callbacks.visitingCallback(array[pivot]);
22-
letfirstRunner=l-1;
2338

24-
for(letsecondRunner=l;secondRunner<h;secondRunner+=1){
39+
letfirstRunner=lowIndex-1;
40+
for(letsecondRunner=lowIndex;secondRunner<highIndex;secondRunner+=1){
2541
if(this.comparator.lessThan(array[secondRunner],pivot)){
2642
firstRunner+=1;
2743
swap(firstRunner,secondRunner);
2844
}
2945
}
3046

3147
if(this.comparator.lessThan(pivot,array[firstRunner+1])){
32-
swap(firstRunner+1,h);
48+
swap(firstRunner+1,highIndex);
3349
}
3450

3551
returnfirstRunner+1;
@@ -40,20 +56,21 @@ export default class QuickSortInPlace extends Sort {
4056
* still have to set `high`'s default within the function as we
4157
* don't have access to `array.length - 1` when declaring paramaters
4258
*/
43-
constlow=inputLow===undefined ?0 :inputLow;
44-
consthigh=inputHigh===undefined ?array.length-1 :inputHigh;
59+
constlowIndex=inputLowIndex===undefined ?0 :inputLowIndex;
60+
consthighIndex=inputHighIndex===undefined ?array.length-1 :inputHighIndex;
4561

4662
// Base case is when low and high converge
47-
if(low<high){
48-
constpartitionIndex=partition(low,high);
63+
if(lowIndex<highIndex){
64+
constpartitionIndex=partition(lowIndex,highIndex);
4965
/*
5066
* `partition()` swaps elements of the array based on their comparison to the `hi` parameter,
5167
* and then returns the index where swapping is no longer necessary, which can be best thought
5268
* of as the pivot used to split an array in a non-in-place quicksort
5369
*/
54-
this.sort(array,low,partitionIndex-1);
55-
this.sort(array,partitionIndex+1,high);
70+
this.sort(array,lowIndex,partitionIndex-1);
71+
this.sort(array,partitionIndex+1,highIndex);
5672
}
73+
5774
returnarray;
5875
}
5976
}

0 commit comments

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