빠른 정렬
6311 단어 javascriptalgorithmsprogramming
// 27, 18, 6, 21, 26, 24
// |
// i
// |
// pivotIndex
// |
// pivotValue
function getPivotPoint(arr, start, end) {
// by convention we always pick the last element as pivot
let pivotValue = arr[end];
// pivot index should at the end hold the larger value compared to pivot
let pivotIndex = start;
for (let i = start; i < end; i++) {
// as loing as values on the left of the pivot is smaller in value,
// we swap the index with the latest updated pivot index
if (arr[i] < pivotValue) {
if (i !== pivotIndex) {
[arr[i], arr[pivotIndex]] = [arr[pivotIndex], arr[i]];
}
pivotIndex++;
}
}
// swap the latest updated pivot index with the pivot value itself
// everything on the right is now larger value than the pivot value
[arr[end], arr[pivotIndex]] = [arr[pivotIndex], arr[end]];
// return new pivot point
return pivotIndex;
}
function QuickSort(arr, start = 0, end = arr.length - 1) {
// base case
if (end > start) {
const pivot = getPivotPoint(arr, start, end);
QuickSort(arr, start, pivot - 1); // do the pivot swap on the left
QuickSort(arr, pivot + 1, end); // do the pivot swap on the right
}
return arr;
}
Reference
이 문제에 관하여(빠른 정렬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/henryong92/quick-sort-14d9텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)