Quick Sort
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950
'use strict';
const swap = (items, firstIndex, secondIndex) => {
var temp = items[firstIndex];
items[firstIndex] = items[secondIndex];
items[secondIndex] = temp;
};
const partition = (items, left, right) => {
let index = (right + left) / 2 | 0;
const pivot = items[index];
let i = left;
let j = right;
while (i < j) { // i <= j to i < j
while (items[i] < pivot) {
i++;
}
while (items[j] > pivot) {
j--;
}
if (i < j) { // i <=j to i < j
swap(items, i, j);
if (i === index) { // update pivot pointer
index = j;
} else if (j === index) {
index = i;
}
i++;
j--;
}
}
return index; // return i to return index
}
const quickSort = (items, left, right) => {
let index;
if (items.length > 1) {
index = partition(items, left, right);
if (left < index - 1) {
quickSort(items, left, index - 1);
}
if (index + 1 < right) { // index < right to index + 1 < right
quickSort(items, index + 1, right); // index to index + 1
}
}
return items;
};
console.log(quickSort([3, 1, 5, 2, 4], 0, 4));
JavaScript
INFO