QuickSort 알고리즘 Java스크립트 예시 포함

퀵 정렬이란 무엇입니까?

빠른 정렬 이는 다음을 따르는 비교 정렬 알고리즘입니다. 분열과 정복 이 접근 방식은 배열의 한 요소를 피벗으로 선택하고, 피벗보다 작은 값을 가진 부분과 큰 값을 가진 부분으로 배열을 분할한 다음, 전체 배열이 정렬될 때까지 각 부분에 동일한 절차를 적용합니다.

퀵 정렬은 모든 프로그래밍 언어에서 가장 널리 사용되는 정렬 알고리즘 중 하나입니다. 만약 당신이 다음과 같이 작성한다면... JavaScript아마 이미 내장 기능을 사용해 보셨을 겁니다. 종류() 이 방법은 기본적으로 제공되므로, 별도의 퀵 정렬 구현을 배우는 것이 왜 중요한지 궁금할 수 있습니다. 그 답을 알기 위해서는 먼저 정렬이란 무엇이며 기본 정렬 방식은 무엇인지 알아야 합니다. Java스크립트가 실제로 그렇습니다.

퀵 정렬은 세 가지 속성으로 정의됩니다.

• 현재 위치: 원본을 재배열합니다 정렬 그리고 동일한 크기의 두 번째 배열을 할당하지 않습니다.
• 재귀적: 각 파티션은 동일한 함수로 정렬된 두 개의 더 작은 범위를 생성합니다.
• 불안정한: 동일한 키를 가진 두 요소가 처음과는 다른 상대적인 순서로 배열될 수 있습니다.

정렬이란 무엇입니까?

정렬이란 요소들을 정해진 순서대로 배열하는 것을 의미합니다. 여러분은 학교에서 이러한 정렬을 거의 확실히 접해봤을 것입니다. 예를 들어, 숫자를 가장 작은 것부터 가장 큰 것 순으로 배열하는 것이 정렬의 한 예입니다. 오름차순 순서대로 나열하고, 가장 큰 것부터 가장 작은 것 순으로 정렬하면 하강하는 순서. 정렬은 숫자에만 국한되지 않습니다. 문자열은 알파벳순으로, 날짜는 시간순으로, 객체는 가격이나 점수와 같은 원하는 필드를 기준으로 정렬할 수 있습니다.

정렬은 데이터가 정렬되면 연산 속도가 빨라지기 때문에 중요합니다. 이진 검색은 O(log n) 시간 복잡도로 실행되지만, 이는 입력 데이터가 정렬된 경우에만 가능합니다. 중복 제거, 범위 검색, 순위 지정 및 병합 연산은 데이터가 정렬되면 훨씬 더 저렴해지므로 모든 프로그래밍 언어에는 최소한 하나의 정렬 루틴이 포함되어 있습니다.

기본 정렬 Java스크립트

앞서 언급 한 바와 같이, Java스크립트는 다음을 제공합니다. 종류()[5,3,7,6,2,9]와 같이 오름차순으로 정렬하고 싶은 작은 배열을 생각해 보세요. 호출하기 종류() 배열에서 정확히 그런 역할을 하는 것 같습니다.

위 스크린샷은 정렬된 배열이 브라우저 콘솔에 출력되는 모습을 보여줍니다. 다음은 동일한 코드입니다.

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

출력:

[ 2, 3, 5, 6, 7, 9 ]

그 결과는 맞지만, 우연의 일치일 뿐입니다. Array.prototype.sort()는 모든 요소를 ​​문자열로 변환하고 해당 문자열들을 비교합니다. 비교 함수를 제공하지 않는 한, 이 배열의 모든 값은 한 자리 숫자이므로 문자열 순서가 숫자 순서와 일치합니다. 데이터를 변경하면 이러한 착각이 깨집니다.

var prices = [10, 9, 1, 100, 25];
console.log(prices.sort());                              // string comparison
console.log(prices.sort(function (a, b) { return a - b; })); // numeric comparison

출력:

[ 1, 10, 100, 25, 9 ]
[ 1, 9, 10, 25, 100 ]

sort() 함수는 어떤 알고리즘을 사용하나요?

사양서에는 알고리즘 이름이 명시되어 있지 않으므로 각 엔진이 자체적인 알고리즘을 선택합니다. 최신 엔진들은 모두 병합 기반 알고리즘을 사용합니다.

• V8 (Chrome, Edge, Node.js)에서 사용되었습니다. 팀소트 V8 7.0 버전부터 Chrome 70에 포함되어 제공됩니다.
• 거미 원숭이 (Firefox) 사용 병합 정렬.
• Java스크립트코어 (Safari)도 사용합니다 병합 정렬.

ES2019 이후로 해당 언어는 다음을 보장합니다. sort() is 안정된이는 엔진 내부에서 일반적인 퀵 정렬을 사용하는 것을 배제합니다. 병합 기반 정렬은 O(n)의 보조 메모리가 필요하며, 사용자의 함수를 호출해야 합니다. Java모든 비교에 대한 스크립트 비교기. 직접 작성한 숫자 퀵 정렬은 숫자를 직접 비교하고 제자리에서 정렬하므로 대규모 숫자 배열에서 더 나은 성능을 보입니다. Node.js 22에서 1,000,000개의 임의 정수를 정렬하는 데 대략적인 시간이 걸렸습니다. 100 MS 아래의 퀵 정렬과 대략적인 결과를 사용하면 됩니다. 210 MS 과 sort((a, b) => a - b).

따라서 퀵 정렬은 제자리 정렬, 메모리 사용량에 대한 엄격한 제어, 또는 정렬 원리에 대한 확실한 이해가 필요할 때 유용하게 사용할 수 있습니다. 이제 그 작동 방식을 자세히 살펴보겠습니다.

퀵 정렬은 어떻게 작동하나요?

퀵 정렬은 하나의 핵심 연산을 반복합니다. 파티셔닝점점 더 작은 범위에서 진행합니다. 다음은 단계별 설명입니다.

1. 찾기 피벗 배열의 요소입니다.
2. 범위의 첫 번째 요소에 왼쪽 포인터를 놓습니다.
3. 범위의 마지막 요소에서 오른쪽 포인터를 시작합니다.
4. 왼쪽 포인터의 요소를 피벗과 비교합니다. 왼쪽 포인터가 피벗보다 작으면 왼쪽 포인터를 오른쪽으로 한 칸 이동합니다. 왼쪽 요소가 피벗보다 크거나 같아질 때까지 이 과정을 반복합니다.
5. 오른쪽 포인터의 요소를 피벗과 비교합니다. 오른쪽 포인터가 피벗보다 크면 오른쪽 포인터를 왼쪽으로 한 단계 이동합니다. 오른쪽 요소의 크기가 피벗보다 작거나 같아질 때까지 이 과정을 반복합니다.
6. 왼쪽 포인터가 여전히 오른쪽 포인터보다 작거나 같으면 두 요소를 바꿉니다.
7. 왼쪽 포인터를 증가시키고 오른쪽 포인터를 감소시킵니다.
8. 왼쪽 포인터의 인덱스가 여전히 오른쪽 포인터의 인덱스보다 작거나 같으면 4단계부터 다시 반복합니다. 그렇지 않으면 왼쪽 포인터의 인덱스를 반환합니다.

위의 그림 trac샘플 배열에서 포인터의 이동을 예로 들어 보겠습니다. 피벗보다 작은 모든 요소는 피벗의 왼쪽에, 피벗보다 큰 모든 요소는 피벗의 오른쪽에 위치하게 되는데, 이는 반환된 인덱스가 가리키는 위치와 정확히 일치합니다. 아래 섹션에서는 동일한 배열을 단계별로 살펴봅니다.

피벗 요소를 결정하는 방법

피벗 위치를 선택하는 것은 퀵 정렬의 속도를 결정짓는 단 하나의 핵심 요소입니다. 만약 항상 피벗 위치를 잘못 선택한다면... 먼저 이미 정렬된 배열의 요소를 분할하면 최악의 결과가 나타납니다. 즉, 한쪽은 비어 있고 다른 한쪽에는 나머지 모든 요소가 있습니다. 이로 인해 알고리즘의 시간 복잡도는 O(n²)이 됩니다. 중간 요소(배열 길이를 2로 나눈 값)는 정렬된 입력과 역순으로 정렬된 입력 모두에서 그러한 함정을 피할 수 있기 때문에 아래 코드에서 이를 사용합니다.

일반적인 피벗 전략:

• 첫 번째 또는 마지막 요소: 코딩하기는 가장 간단하지만, 정렬된 데이터에서는 O(n²)의 시간 복잡도를 갖습니다.
• 중간 요소: 정렬된 배열과 역순으로 정렬된 배열을 O(n log n)의 시간 복잡도로 처리하는 좋은 기본값입니다.
• 무작위 요소: 최악의 경우 입력값을 사전에 구성하는 것을 불가능하게 만듭니다.
• 세 가지의 중앙값: 첫 번째, 중간, 마지막 값의 중앙값을 취합니다. 이는 프로덕션 라이브러리에서 일반적으로 사용되는 방식입니다.

이제 배열에 대한 퀵 정렬 과정을 살펴보겠습니다. [5,3,7,6,2,9].

1 단계 : 중심축은 가운데 요소입니다. 왼쪽은 0, 오른쪽은 5입니다. Math.floor((5 + 0) / 2) 인덱스 2를 제공하므로 피벗 값은 다음과 같습니다. 7.

2 단계 : 배열의 양 끝에 포인터를 놓습니다. 왼쪽 포인터는 인덱스 0(값)에 있습니다. 5오른쪽 포인터는 인덱스 5(값)에 있습니다. 9).

3 단계 : 왼쪽 값을 기준점과 비교합니다. 5 < 7이므로 오른쪽으로 이동하여 1번 인덱스로 이동합니다. 3 < 7이므로 오른쪽으로 이동하여 2번 인덱스로 이동합니다. 2번 인덱스의 값은 7로 기준점보다 작지 않으므로 왼쪽 포인터는 2번 인덱스에서 멈춥니다.

4 단계 : 오른쪽 값을 기준점과 비교합니다. 9 > 7이므로 왼쪽으로 이동하여 4번째 인덱스로 이동합니다. 4번째 인덱스의 값은 2이며, 이는 기준점보다 크지 않으므로 오른쪽 포인터는 4번째 인덱스에서 멈춥니다.

5 단계 : 왼쪽 인덱스(2)가 오른쪽 인덱스(4)보다 작거나 같으므로 두 값을 바꿉니다. 배열은 다음과 같이 됩니다. [5,3,2,6,7,9].

6 단계 : 두 포인터를 한 칸씩 안쪽으로 이동합니다. 이제 왼쪽 포인터는 인덱스 3에 있고 오른쪽 포인터도 인덱스 3에 있습니다.

7 단계 : 스캔을 반복합니다. 인덱스 3의 값은 6이고, 6 < 7이므로 왼쪽 포인터는 인덱스 4로 이동합니다. 인덱스 3의 값은 피벗보다 크지 않으므로 오른쪽 포인터는 인덱스 3에 그대로 유지됩니다.

8 단계 : 이제 왼쪽 인덱스(4)가 오른쪽 인덱스(3)보다 크므로 루프가 종료되고 함수가 반환됩니다. 4인덱스 4 이전의 모든 값은 피벗보다 작거나 같고, 인덱스 4 이후의 모든 값은 피벗보다 크거나 같습니다.

위의 설명에 따르면, 두 가지 연산에 대한 코드가 필요합니다: 교환ping 두 요소와 범위 분할.

Code 두 개를 교환하기 Numbers in Java스크립트

위의 편집기 스크린샷에서 볼 수 있듯이, swap 헬퍼는 임시 변수를 사용하여 두 인덱스의 값을 교환합니다. 배열을 직접 변경하고 아무것도 반환하지 않습니다.

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

var demo = [5, 3, 7, 6, 2, 9];
swap(demo, 0, 5);
console.log(demo);

출력:

[ 9, 3, 7, 6, 2, 5 ]

Code 분할을 수행하려면

위 스크린샷의 코드는 1단계부터 8단계까지의 과정을 함수로 변환합니다. 두 개의 내부 함수는... 루프 포인터를 앞으로 이동시키세요. if 블록은 스왑을 수행하고, 함수는 분할된 인덱스를 반환합니다.

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;
}

var items = [5, 3, 7, 6, 2, 9];
var index = partition(items, 0, items.length - 1);
console.log(items);
console.log(index);

출력:

[ 5, 3, 2, 6, 7, 9 ]
4

출력은 매뉴얼의 설명과 정확히 일치합니다. 한 번의 파티션 패스 후 배열은 [5,3,2,6,7,9]이고 반환된 분할 인덱스는 4입니다.

재귀를 수행합니다 Opera기

분할을 통해 분할 인덱스를 얻으면, 이 인덱스를 사용하여 범위를 나누고 각 절반에 대해 퀵 정렬을 실행합니다. 이것이 바로 분할 정복 알고리즘이라고 불리는 이유입니다. 재귀 호출은 모든 하위 범위에 요소가 하나씩 남을 때까지 계속되며, 그 시점에서 전체 배열이 정렬됩니다.

참고 : 퀵 정렬은 전체 과정에서 동일한 배열을 사용합니다. 이 과정에서 새로운 배열이 생성되지 않기 때문에 제자리 정렬(in-place algorithm)이라고 불립니다.

그래서 당신은 전화를 겁니다 분할() 위에서 설명한 함수를 사용하고 해당 함수의 반환 값을 사용하여 분할합니다. 정렬 여러 부분으로 나눕니다. 다음은 그 작업을 수행하는 코드입니다.

스크린샷에서 강조 표시된 두 가지 가드 조건을 확인하세요. left < index - 1 왼쪽에는 최소 두 개의 요소가 남아 있음을 확인시켜 줍니다. index < right 오른쪽도 마찬가지임을 확인시켜 줍니다. 이러한 보호 장치가 없으면 함수는 단일 요소 범위에서 무한히 자기 자신을 호출하게 됩니다.

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 items = [5, 3, 7, 6, 2, 9];
var result = quickSort(items, 0, items.length - 1);
console.log(result);

출력:

[ 2, 3, 5, 6, 7, 9 ]

빠른 정렬 완료 Code

스왑, 파티션, 재귀 부분을 모두 합치면 완전한 구현이 됩니다.

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); // swapping 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);

출력:

[ 2, 3, 5, 6, 7, 9 ]

위 스크린샷은 에디터에서 실행되는 전체 프로그램과 콘솔에 출력된 정렬된 배열을 보여줍니다. 이 구현은 이미 정렬된 배열, 역순으로 정렬된 배열, 중복 및 동일한 값을 포함하는 배열, 음수, 단일 요소, ​​그리고 빈 배열을 대상으로 검증되었으며, 모든 경우에 올바른 결과를 반환합니다.

퀵 정렬의 시간 및 공간 복잡도

각 분할 패스는 범위 내의 각 요소를 한 번씩 건드리므로 단일 패스의 비용은 O(n)입니다. 따라서 총 비용은 범위가 단순해지기 전에 배열을 몇 번 분할할 수 있는지에 따라 달라집니다.

공간 복잡도는 O(log n)입니다. 이 인플레이스 버전의 경우 두 번째 배열이 할당되지 않으므로 추가 메모리는 재귀 스택뿐이며, 균형 분할로 인해 스택 깊이는 약 log₂(n) 프레임으로 유지됩니다. 최악의 경우 스택은 O(n) 프레임까지 커지므로 매우 큰 배열은 호출 스택 오버플로를 일으킬 수 있습니다.

두 가지 수치가 이를 구체화합니다. 위 코드를 사용하여 4,096개의 임의 값을 정렬하는 데 약 65,000번의 비교가 사용되었는데, 이는 이론적인 n·log₂(n)인 49,152보다 훨씬 높은 수치입니다. 또한 가장 깊은 재귀 호출은 24프레임에 도달했는데, log₂(4096)은 12입니다. 두 수치 모두 O(n log n) 알고리즘에서 예상되는 작은 상수 계수 범위 내에 있습니다.

퀵 정렬 vs. 다른 정렬 방식 Algorithms

퀵 정렬은 유일한 선택지가 아닌 경우가 많습니다. 아래 표는 퀵 정렬을 여러분이 접하게 될 가능성이 가장 높은 다른 알고리즘들과 비교하여, 데이터에 맞는 최적의 알고리즘을 선택할 수 있도록 도와줍니다.

퀵 정렬은 내부 루프의 시간 복잡도가 낮고 캐시 친화적인 연속적인 범위에서 작동하기 때문에 실제 사용에서 일반적으로 가장 효율적입니다. O(n log n) 시간 복잡도 또는 안정적인 정렬이 보장되어야 할 때는 병합 정렬을, 메모리 제약이 매우 심할 때는 힙 정렬을, 배열 크기가 매우 작거나 거의 정렬된 배열에는 삽입 정렬을 선택하십시오. 실제 라이브러리에서는 이러한 정렬 방식을 조합하여 사용하는 경우가 많습니다. 예를 들어, introsort는 퀵 정렬로 시작하여 재귀 호출이 너무 깊어지면 힙 정렬로 전환하고, 작은 범위에서는 삽입 정렬로 마무리합니다.

객체와 문자열을 빠르게 정렬하는 방법

지금까지 보여준 구현 방식은 값을 다음과 비교합니다. < >이는 숫자로만 제한됩니다. 실제 응용 프로그램에서는 정렬이 필요합니다. 사물 속성, 문자열의 알파벳순 또는 날짜순으로 정렬할 수 있습니다. 해결 방법은 내장 함수처럼 비교 로직을 콜백 함수로 옮기는 것입니다. sort() 않습니다.

비교기는 두 값을 입력받아 첫 번째 값이 먼저 와야 할 경우 음수를, 두 번째 값이 먼저 와야 할 경우 양수를, 두 값이 같을 경우 0을 반환합니다. 하드코딩된 두 개의 비교 연산을 비교기 호출로 대체하면 알고리즘이 모든 데이터 유형에서 작동하게 됩니다.

function swap(items, i, j) {
    var temp = items[i];
    items[i] = items[j];
    items[j] = temp;
}

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

function quickSort(items, left, right, compare) {
    if (left >= right) { return items; } // nothing left to split
    var index = partition(items, left, right, compare);
    if (left < index - 1) { quickSort(items, left, index - 1, compare); }
    if (index < right) { quickSort(items, index, right, compare); }
    return items;
}

function sort(items, compare) {
    compare = compare || function (a, b) { return a < b ? -1 : a > b ? 1 : 0; };
    return quickSort(items, 0, items.length - 1, compare);
}

var numbers = [10, 9, 1, 100, 25];
console.log(sort(numbers, function (a, b) { return a - b; }));

var names = ["Priya", "arun", "Bala", "chetan"];
console.log(sort(names, function (a, b) {
    return a.toLowerCase().localeCompare(b.toLowerCase());
}));

var employees = [
    { name: "Arun",   salary: 52000 },
    { name: "Bala",   salary: 41000 },
    { name: "Chetan", salary: 68000 }
];
console.log(sort(employees, function (a, b) { return a.salary - b.salary; }));

출력:

[ 1, 9, 10, 25, 100 ]
[ 'arun', 'Bala', 'chetan', 'Priya' ]
[
  { name: 'Bala', salary: 41000 },
  { name: 'Arun', salary: 52000 },
  { name: 'Chetan', salary: 68000 }
]

세 가지 세부 사항에 주목할 필요가 있습니다. 재귀 가드는 이제 다음과 같습니다. left >= right이는 어떤 범위에서도 정확하며 외부 배열의 길이에 의존하지 않습니다. 문자열 비교는 다음을 사용합니다. localeCompare() 이렇게 하면 악센트가 있는 문자와 대소문자를 원시 코드 포인트가 아닌 올바르게 처리할 수 있습니다. 또한 퀵 정렬은 안정적이지 않기 때문에 급여가 같은 레코드의 순위가 바뀔 수 있습니다. 원래 순서가 중요하다면 두 번째 키를 사용하여 순위를 결정하도록 정렬하세요.

계속 나아갈 준비가 되셨나요? 기본기를 탄탄히 다지세요. Java대본 소개포인터 조작법을 연습하세요 Java스크립트 루프더 많은 과정을 거쳐 실용적인 Java스크립트 코드 예시구현 방식을 비교합니다. 삽입 정렬 힙 정렬또는 이 알고리즘에 정적 타입을 추가하세요. TypeScript 참고.

자주 묻는 질문