Hey guys, lets gonna practice with the QuickSort algorithm.
This algorithm is based on the divide and conquer approach of programming. As a rule, the Quicksort is an in-place sorting algorithm, but that is not necessary.
- This algorithm, on average, takes
O(nlog n)time to sort n items. In the worst case, it makesO(n^2)(good implementations as a rule takeO(nlog n)) -
The space complexity is
O(log n)but it depends on implementation. Another interesting thing is that we can make this algorithm stable and unstable as well. And as for the stable case, it will takeO(n)space orO(1)for in-place implementations - A little preparation in choosing a pivot
- Used in V8 before Timsort algorithm
Let's visualize the algorithm:
During selecting the pivot we can sort the first, pivot, and last element - it is a constant operation and doesn't take additional time.
Rules for the code (as usual):
- Choose the right names for variables
- Choose the right loop statements: for, while, forEach, reduce etc.
- Avoid excess conditions and comparisons for edge cases
- Escape the side effects in your algorithms function, because very often you need to do mutations to decrease space or time complexity
class QuickSort {
constructor(inputArray) {
/**
* it depends on the requirements, in our case we sort in place
*/
this.inputArray = inputArray;
}
inputArray;
swap = (arr, firstIndex, secondIndex) => {
const temp = arr[firstIndex];
arr[firstIndex] = arr[secondIndex];
arr[secondIndex] = temp;
};
getMedianFrom3WithSwap = (arr, from = 0, to = arr.length - 1) => {
const middleIndex = Math.round((from + to) / 2);
if (arr[middleIndex] < arr[from]) {
this.swap(arr, middleIndex, from);
}
if (arr[to] < arr[from]) {
this.swap(arr, from, to);
}
if (arr[to] < arr[middleIndex]) {
this.swap(arr, to, middleIndex);
}
return arr[middleIndex];
};
sortPartition = (arr, from, to) => {
const pivot = this.getMedianFrom3WithSwap(arr, from, to);
while (from <= to) {
while (arr[from] < pivot) {
from++;
}
while (arr[to] > pivot) {
to--;
}
if (from <= to) {
this.swap(arr, from, to);
from++;
to--;
}
}
return [from, to];
};
sort = () => {
const repeatSorting = (arr, from, to) => {
if (arr.length < 2 || from > to) {
return;
}
const [nextFrom, nextTo] = this.sortPartition(arr, from, to);
repeatSorting(arr, from, nextTo);
repeatSorting(arr, nextFrom, to);
};
repeatSorting(this.inputArray, 0, this.inputArray.length - 1);
return this.inputArray;
};
}
console.log(new QuickSort([7, 4, 3, 5, 6, 8, 1, 9]).sort());
console.log(new QuickSort([100, 3, 4, 5, 13, 7, 3, 0]).sort());
console.log(new QuickSort([1, 4, 3, 5]).sort());
console.log(new QuickSort([3, -1]).sort());
Check result on leetcode
Sources:
https://favtutor.com/blogs/quick-sort-cpp
https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/quick-sort
Let me know your thoughts in the comment section below! 😊
Top comments (0)