JavaScript의 퀵 정렬
병합 정렬과 마찬가지로 QuickSort는 분할 정복 전략을 사용합니다. 요소를 피벗으로 선택하고 그 주위에 지정된 배열을 분할합니다.
여러 가지 QuickSort 변형이 있으며 모두 피벗을 다르게 선택합니다.
JavaScript의 퀵 정렬
파티션은 quickSort()의 주요 프로세스입니다. 배열과 배열 멤버 x가 피벗으로 주어지면 분할의 목표는 x를 정렬된 배열의 올바른 위치에 배치하고 x 앞에 모든 작은 요소를 배치하고 x 뒤에 모든 큰 요소를 배치하는 것입니다. ; 이 모든 것은 선형 시간 내에 완료되어야 합니다.
JavaScript에는 sort() 메서드가 있습니다. sort()가 원하는 결과를 제공하지만 문제는 배열 구성 요소를 정렬하는 방법입니다.
JavaScript의 기본 sort()는 Chrome V8 엔진의 삽입 정렬과 Mozilla Firefox 및 Safari의 병합 정렬을 활용합니다. 그러나 많은 항목을 정렬해야 하는 경우에는 적합하지 않습니다.
결과적으로 대규모 데이터 세트에 대한 솔루션은 퀵 정렬을 사용하는 것입니다.
다음은 퀵 정렬을 구현하는 간단한 단계입니다.
-
먼저 피벗 요소로 알려진 요소를 선택합니다. 이 요소는 일반적으로 배열의 첫 번째 또는 마지막 요소입니다.
-
배열의 각 구성원을 선택한 피벗 요소와 비교하여 피벗 요소보다 작은 요소가 왼쪽에 있고 피벗 요소보다 큰 요소가 오른쪽에 있도록 구성 요소를 재정렬합니다. 이를 파티셔닝이라고 합니다.
-
마지막으로 왼쪽 및 오른쪽 구성 요소에서 수행한 것과 동일한 절차를 피벗 요소에 수행합니다.
정렬되지 않은 항목 [9, 1, 4, 7, 0, 2, 5, 8]이 있는 배열의 예를 사용하여 이러한 프로세스를 자세히 살펴보겠습니다. 마지막 요소를 피벗으로 만듭니다.
분할을 위한 JavaScript 코드:
const partitionFunction = (arratItems, left, right) => {
let pivotElement = arratItems[Math.floor((right + left) / 2)];
let leftElement = left;
let rightElement = right;
while (leftElement <= rightElement) {
while (arratItems[leftElement] < pivotElement) {
leftElement++;
}
while (arratItems[rightElement] > pivotElement) {
rightElement--;
}
if (leftElement <= rightElement) {
swapFunction(arratItems, leftElement, rightElement);
leftElement++;
rightElement--;
}
}
return leftElement;
};
스와핑을 수행하기 위한 JavaScript 코드:
const swapFunction = (arratItems, leftIndex, rightIndex) => {
const temp = arratItems[leftIndex];
arratItems[leftIndex] = arratItems[rightIndex];
arratItems[rightIndex] = temp;
};
빠른 정렬은 왼쪽 및 오른쪽 배열의 모든 요소가 정렬될 때까지 사용됩니다. 빠른 정렬 중에는 새 어레이가 생성되지 않습니다. 단순히 현재 배열을 사용합니다.
따라서 위에서 설명한 partitionFunction() 함수를 호출하여 배열을 조각으로 나누어야 합니다. 코드는 여기에서 사용할 수 있도록 제공됩니다.
const arratItems = [9, 1, 4, 7, 0, 2, 5, 8];
const quickSortFunction = (arratItems, left, right) => {
let index;
if (arratItems.length > 1) {
index = partitionFunction(arratItems, left, right);
if (left < index - 1) {
quickSortFunction(arratItems, left, index - 1);
}
if (index < right) {
quickSortFunction(arratItems, index, right);
}
}
return arratItems;
};
// Initial call to quick sort function
const result = quickSortFunction(arratItems, 0, arratItems.length - 1);
console.log(result);
JavaScript와 호환되는 모든 브라우저에서 위 코드 행을 실행하십시오. 다음과 같은 결과가 표시됩니다.
출력:
[0, 1, 2, 4, 5, 7, 8, 9]
Shraddha is a JavaScript nerd that utilises it for everything from experimenting to assisting individuals and businesses with day-to-day operations and business growth. She is a writer, chef, and computer programmer. As a senior MEAN/MERN stack developer and project manager with more than 4 years of experience in this sector, she now handles multiple projects. She has been producing technical writing for at least a year and a half. She enjoys coming up with fresh, innovative ideas.
LinkedIn