QuickSort 알고리즘 Java스크립트

정렬이란 무엇입니까?

정렬은 우리가 원하는 순서대로 요소를 배열하는 것에 불과합니다. 학교나 대학 시절에 이런 일을 접했을 수도 있습니다. 작은 것에서 큰 것으로(오름차순) 또는 큰 것에서 작은 것으로(내림차순) 숫자를 배열하는 것과 같은 것으로, 정렬이라고 합니다.

기본 정렬 Java스크립트

앞서 언급 한 바와 같이, Java스크립트에는 종류(). [5,3,7,6,2,9]와 같은 몇 가지 요소 배열이 있는 예를 들어 이 배열 요소를 오름차순으로 정렬하려고 합니다. 그냥 전화해 종류() 항목 배열에 대해 배열 요소를 오름차순으로 정렬합니다.

암호:

var items = [5,3,7,6,2,9];
console.log(items.sort());
//prints [2, 3, 5, 6, 7, 9]

기본 정렬() 대신 빠른 정렬을 선택한 이유는 무엇입니까? JavaScript

sort()가 우리가 원하는 결과를 제공하지만 문제는 배열 요소를 정렬하는 방식에 있습니다. 기본 sort() Java스크립트 사용 삽입 정렬 by Chrome의 V8 엔진 그리고 병합 정렬 by 모질라 Firefox 그리고 Safari.

그러나 많은 수의 요소를 정렬해야 하는 경우에는 이 방법이 적합하지 않습니다. 따라서 해결책은 대규모 데이터 세트에 대해 Quick Sort를 사용하는 것입니다.

따라서 완전히 이해하려면 빠른 정렬이 어떻게 작동하는지 알아야 하며 이제 자세히 살펴보겠습니다.

퀵 정렬이란 무엇입니까?

빠른 정렬은 다음과 같습니다. 분열과 정복 알고리즘입니다. 어떤 조건에 따라 요소를 더 작은 부분으로 나누고, 나뉜 더 작은 부분에 정렬 작업을 수행합니다. 따라서 대규모 데이터 세트에 적합합니다. 그럼, 퀵 정렬이 어떻게 작동하는지 간단한 말로 단계를 알려드리겠습니다.

1. 먼저 호출할 요소를 선택합니다. 피벗 요소입니다.
2. 다음으로, 모든 배열 요소를 선택한 피벗 요소와 비교하고 피벗 요소보다 작은 요소는 왼쪽에 있고 피벗보다 큰 요소는 오른쪽에 있도록 배열합니다.
3. 마지막으로 피벗 요소의 왼쪽과 오른쪽 요소에도 동일한 작업을 수행합니다.

이것이 바로 퀵 정렬의 기본 개요입니다. 빠른 정렬을 수행하기 위해 하나씩 따라야 하는 단계는 다음과 같습니다.

QuickSort는 어떻게 작동하나요?

1. 먼저 찾아보세요 "피벗" 배열의 요소입니다.
2. 배열의 첫 번째 요소에서 왼쪽 포인터를 시작합니다.
3. 배열의 마지막 요소에서 오른쪽 포인터를 시작합니다.
4. 왼쪽 포인터와 가리키는 요소를 비교하고 피벗 요소보다 작으면 왼쪽 포인터를 오른쪽으로 이동합니다(왼쪽 인덱스에 1을 더함). 왼쪽 요소가 피벗 요소보다 크거나 같을 때까지 이를 계속합니다.
5. 오른쪽 포인터를 가리키는 요소를 비교하고 피벗 요소보다 큰 경우 오른쪽 포인터를 왼쪽으로 이동합니다(오른쪽 인덱스에서 1을 뺍니다). 오른쪽 요소가 피벗 요소보다 작거나 같을 때까지 이를 계속합니다.
6. 왼쪽 포인터가 오른쪽 포인터보다 작거나 같은지 확인한 다음 이 포인터 위치의 요소를 교체합니다.
7. 왼쪽 포인터를 증가시키고 오른쪽 포인터를 감소시킵니다.
8. 왼쪽 포인터의 인덱스가 여전히 오른쪽 포인터의 인덱스보다 작으면 프로세스를 반복합니다. 그렇지 않으면 왼쪽 포인터의 인덱스를 반환합니다.

이제 예를 들어 이러한 단계를 살펴보겠습니다. 정렬해야 하는 요소의 배열이 [5,3,7,6,2,9]라고 가정해 보겠습니다.

피벗 요소 결정

그러나 빠른 정렬을 진행하기 전에 피벗 요소를 선택하는 것이 중요한 역할을 합니다. 첫 번째 요소를 피벗 요소로 선택하면 정렬된 배열에서 최악의 성능을 제공합니다. 따라서 항상 중간 요소(배열의 길이를 2로 나눈 값)를 피벗 요소로 선택하는 것이 좋으며 우리도 동일하게 수행합니다.

다음은 예제 [5,3,7,6,2,9]와 함께 표시되는 빠른 정렬을 수행하는 단계입니다.

1 단계 : 피벗을 중간 요소로 결정합니다. 그래서, 7 피벗 요소입니다.

2 단계 : 왼쪽 및 오른쪽 포인터를 각각 배열의 첫 번째 요소와 마지막 요소로 시작합니다. 따라서 왼쪽 포인터가 다음을 가리키고 있습니다. 5 인덱스 0에서 오른쪽 포인터가 가리키고 있습니다. 9 인덱스 5에서.

3 단계 : 왼쪽 포인터의 요소를 피벗 요소와 비교합니다. 5 < 6이므로 왼쪽 포인터를 오른쪽으로 이동하여 인덱스 1로 이동합니다.

4 단계 : 이제 여전히 3 <6이므로 왼쪽 포인터를 오른쪽의 한 인덱스 더 이동합니다. 따라서 이제 7 > 6은 왼쪽 포인터를 증가시키는 것을 멈추고 이제 왼쪽 포인터는 인덱스 2에 있습니다.

5 단계 : 이제 오른쪽 포인터의 값을 피벗 요소와 비교하세요. 9 > 6이므로 오른쪽 포인터를 왼쪽으로 이동합니다. 이제 2 < 6이므로 오른쪽 포인터 이동을 중지합니다.

6 단계 : 왼쪽 포인터와 오른쪽 포인터에 있는 두 값을 서로 바꿉니다.

7 단계 : 두 포인터를 한 단계 더 이동합니다.

8 단계 : 6 = 6이므로 포인터를 한 단계 더 이동하고 왼쪽 포인터가 오른쪽 포인터를 교차하면서 중지하고 왼쪽 포인터의 인덱스를 반환합니다.

따라서 위의 접근 방식을 기반으로 위 단계에서 언급한 대로 요소를 교체하고 배열을 분할하는 코드를 작성해야 합니다.

두 숫자를 바꾸는 코드 Java스크립트

function swap(items, leftIndex, rightIndex){
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}

위 단계에서 언급한 대로 파티션을 수행하는 코드

function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], //middle element
        i       = left, //left pointer
        j       = right; //right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); //swap two elements
            i++;
            j--;
        }
    }
    return i;
}

재귀 연산을 수행하세요

위의 단계를 수행하면 왼쪽 포인터의 인덱스가 반환되며 이를 사용하여 배열을 나누고 해당 부분에 대해 빠른 정렬을 수행해야 합니다. 그래서 분할 정복 알고리즘이라고 합니다.

따라서 왼쪽 배열과 오른쪽 배열의 모든 요소가 정렬될 때까지 Quick Sort가 수행됩니다.

참고 : 빠른 정렬은 동일한 어레이에서 수행되며 이 과정에서 새 어레이가 생성되지 않습니다.

그래서 우리는 이것을 호출해야 합니다 분할() 위에서 설명한 내용을 토대로 나누어보겠습니다. 정렬 부품에. 따라서 이를 사용하는 코드는 다음과 같습니다.

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}
// first call to quick sort
var result = quickSort(items, 0, items.length - 1);

빠른 정렬 코드 완성

var items = [5,3,7,6,2,9];
function swap(items, leftIndex, rightIndex){
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}
function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], //middle element
        i       = left, //left pointer
        j       = right; //right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); //sawpping two elements
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}
// first call to quick sort
var sortedArray = quickSort(items, 0, items.length - 1);
console.log(sortedArray); //prints [2,3,5,6,7,9]

알림: 빠른 정렬은 다음과 같은 시간 복잡도로 실행됩니다. O(n로그인).