퀵소트

퀵소트

QuickSort 알고리즘의 애니메이션 시각화.수평선은 피벗 값입니다.
학급	정렬 알고리즘
최악의 경우 성능	${\displaystyle O(n^{2})}$
베스트 케이스 성능	${\displaystyle O}$( ${\displaystyle n}$ log${\displaystyle n}$n $){$ $display$O ($n$ \ $log$n ) （$$ simple partition ） $또는{\displaystyle }$O (${\displaystyle n}$ )$$\ $displaystyle$O ($n$ ) $$（ 3 way partition and equal key )
평균 성능	${\displaystyle O(n\log n)}$
최악의 경우 공간의 복잡성	${\displaystyle O}$(${\displaystyle n}$ )$${ $displaystyle$O ($n$ ) }보조$$(네이브) ${\displaystyle O}$( log${\displaystyle n}$n$$) { $displaystyle$ O ( \ $log$ n $)$ } 보조$$ (Hoare 1962 )

QuickSort는 인플레이스 정렬 알고리즘입니다.1959년 영국의^[1] 컴퓨터 과학자인 토니 호어에 의해 개발되어 ^[2]1961년에 출판된 이 알고리즘은 여전히 일반적으로 분류에 사용되는 알고리즘이다.잘 구현되면 머지 정렬보다 다소 빠를 수 있으며 ^{[3][contradictory]}힙소트보다 약 2~3배 더 빠를 수 있습니다.

QuickSort는 분할 및 정복 알고리즘입니다.배열에서 'pivot' 요소를 선택하고 피벗보다 작거나 큰지 여부에 따라 다른 요소를 두 개의 하위 배열로 분할하여 작동합니다.이러한 이유로 파티션 교환 ^[4]정렬이라고도 합니다.그런 다음 하위 배열이 재귀적으로 정렬됩니다.이 작업은 인플레이스 방식으로 수행할 수 있으므로 정렬을 수행하기 위해 소량의 추가 메모리가 필요합니다.

QuickSort는 비교 정렬로, "보다 작은" 관계(공식적으로 전체 순서)가 정의된 모든 유형의 항목을 정렬할 수 있습니다.QuickSort의 효율적인 구현은 안정적인 정렬이 아니며, 이는 동일한 정렬 항목의 상대적 순서가 유지되지 않음을 의미합니다.

QuickSort의 수학적 분석에 따르면 알고리즘은 평균적으로 O${\displaystyle }$(${\displaystyle n}$ log${\displaystyle n}$n $)\displaystyle$O ($n\log {n})$ 비교를$$ $통해{\displaystyle }$ n개의 항목을 정렬합니다.최악의 경우 O${\displaystyle ({n\mathrm{}}^{}}$2$)(\displaystyle$ O$(n^{2})$ 비교가$$ $이루어집니다{\displaystyle }$.

역사

퀵소트 알고리즘은 1959년 토니 호어 씨가 모스크바 주립대 방문 학생이었을 때 개발되었습니다.당시 Hoare는 국립물리연구소에서 기계번역 프로젝트를 하고 있었습니다.번역 과정의 일환으로, 그는 러시아어-영어 사전을 찾기 전에 러시아어 문장의 단어들을 분류할 필요가 있었는데, 러시아어-영어 사전은 ^[5]자기 테이프의 알파벳 순서로 되어 있었다.그의 첫 번째 아이디어인 삽입 정렬이 느릴 것이라는 것을 깨달은 후, 그는 새로운 아이디어를 생각해냈다.그는 Mercury Autocode에서 파티션 부분을 작성했지만 정렬되지 않은 세그먼트 목록을 처리하는 데 어려움을 겪었습니다.영국으로 돌아오면서 그는 셸소트의 코드를 써달라는 요청을 받았다.Hoare는 더 빠른 알고리즘을 알고 있다고 상사에게 말했지만 상사는 몰랐다고 6펜스를 걸었다.그의 상사는 결국 그가 내기에서 졌다는 것을 받아들였다.나중에 Hoare는 ALGOL과 그 재귀 능력에 대해 알게 되었고,^[2][6] 그 덕분에 당시 최고의 컴퓨터 과학 저널인 Communications of the Association for Computing Machine에 그 코드를 게재할 수 있었습니다.

Quicksort는 Unix에서 기본 라이브러리 정렬 서브루틴으로 나타나는 등 널리 채택되었습니다.따라서 C 표준 라이브러리 서브루틴에 이름을 빌려주었습니다.qsort^[7] 및 Java의 참조 구현에 사용됩니다.

1975년 Robert Sedgewick의 박사 논문은 Quicksort 연구의 이정표로 간주되며, Quicksort는 샘플 소트, Van^[8] Emden의 적응 분할, 예상 비교 횟수 및 스왑 ^[7]도출을 포함한 다양한 피벗 선택 체계 분석과 관련된 많은 미해결 문제를 해결했다.Jon Bentley와 Doug McIlroy는 프로그래밍 라이브러리에서 사용할 수 있는 다양한 개선 사항을 통합했습니다. 여기에는 동일한 요소를 처리하는 기술과 9개의 피벗 스킴으로 알려진 9개의 요소를 샘플로 3개의 그룹으로 나누고 3개의 그룹에서 3개의 중위수를 ^[7]선택하는 것이 포함됩니다.Bentley는 그의 저서 Programming Pearls에서 Nico Lomuto의 탓으로 돌린 또 다른 단순하고 콤팩트한 분할 방식을 묘사했다.나중에 벤틀리는 호어 버전을 수년간 사용했지만 실제로 이해하지 못했다고 썼지만 로무토의 버전은 정확하다는 것을 ^[9]증명하기에 충분할 정도로 단순했다.벤틀리는 같은 에세이에서 퀵소트를 "내가 쓴 것 중 가장 아름다운 코드"라고 묘사했다.Lomuto의 파티션 스킴은 Hoare의 스킴보다 열등하지만 모든 요소가 동일할 ^{[10][self-published source?]}경우 평균 3배 더 많은 스왑을 수행하고 O(n²) 런타임으로 저하되기 때문에 알고리즘 입문서에 의해 대중화되었습니다.

2009년 블라디미르 야로슬라브스키(Vladimir Yaroslavski)는 하나의 ^[11]피벗이 아닌 두 개의 피벗을 사용하는 새로운 Quicksort 구현을 제안했다.자바 코어 라이브러리 메일링 리스트에서 그는 자신의 새로운 알고리즘이 런타임 라이브러리의 정렬 방법보다 우수하다고 주장하는 논의를 시작했습니다.이것은 당시 Bentley와 McIlroy의 ^[12]클래식 Quicksort의 널리 사용되고 세심하게 조정된 변형에 기초하고 있었습니다.야로슬라브스키의 Quicksort는 광범위한 경험적 성능 ^[14]테스트를 거쳐 Oracle의 Java 7 런타임^[13] 라이브러리의 새로운 기본 정렬 알고리즘으로 선택되었습니다.

알고리즘.

QuickSort는 파티션 루틴에 따라 어레이를 정렬하는 분할 및 정복 알고리즘의 일종입니다.이 파티션의 세부 사항은 다소 다를 수 있기 때문에 QuickSort는 실제로 밀접하게 관련된 알고리즘의 집합입니다.분할은 적어도 2개의 요소의 범위에 적용되며, 제1 서브레인지의 요소가 제2 서브레인지의 요소보다 크지 않도록 2개의 연속적인 비어 있지 않은 서브레인지로 분할된다.이 파티션을 적용한 후 QuickSort는 서브 범위를 재귀적으로 정렬합니다.이는 분할 포인트에서 이미 최종 위치에 있는 요소를 제외시킨 후일 수 있습니다.재귀적인 성질 때문에 퀵소트(파티션 루틴과 같은)는 완전한 배열을 정렬하는 것이 최종 목표인 경우에도 더 큰 배열 내의 범위를 호출할 수 있도록 공식화해야 합니다.임플레이스 퀵소트의 순서는 다음과 같습니다.

1. 범위에 요소가 2개 미만일 경우 할 일이 없으므로 즉시 반환하십시오.다른 매우 짧은 길이의 경우 특수 목적 정렬 방법을 적용하고 나머지 단계를 건너뜁니다.
2. 그렇지 않으면 범위 내에서 발생하는 피벗이라고 하는 값을 선택합니다(정확한 선택 방법은 파티션 루틴에 따라 다르며 랜덤성을 수반할 수 있습니다).
3. 범위 분할: 분할점을 결정하는 동안 요소의 순서를 변경하여 값이 피벗보다 작은 모든 요소가 분할 앞에 오고 값이 피벗보다 큰 모든 요소가 그 뒤에 오도록 합니다. 피벗과 동일한 요소는 어느 방향으로도 이동할 수 있습니다.적어도 하나의 피벗 인스턴스가 존재하기 때문에 대부분의 파티션 루틴은 분할 포인트에서 끝나는 값이 피벗과 동일하고 현재 최종 위치에 있음을 확인합니다(단, 원래보다 완전히 작은 하위 범위가 생성되는 한 빠른 정렬의 종료는 여기에 의존하지 않습니다).
4. 분할 지점까지 하위 범위와 분할 지점 이후의 하위 범위에 빠른 정렬을 재귀적으로 적용합니다. 두 범위 모두에서 분할 지점의 피벗과 동일한 요소를 제외할 수 있습니다.(모든 요소가 피벗과 동일한 것으로 알려진 경계 부근에서 파티션에 의해 더 큰 서브범위가 생성되는 경우 이러한 서브범위를 제외할 수도 있습니다).

파티션 루틴 선택(피벗 선택 포함) 및 위에서 완전히 지정되지 않은 기타 세부 사항은 알고리즘의 성능에 영향을 줄 수 있으며, 특정 입력 배열에 큰 영향을 미칠 수 있습니다.따라서 QuickSort의 효율성에 대해 설명할 때는 먼저 이러한 선택 사항을 지정해야 합니다.여기서는 두 가지 구체적인 파티션 방법을 설명하겠습니다.

Lomuto 파티션 구성표

이 계획은 Nico Lomuto에 기인하며, Bentley에 의해 그의 저서 Programming^[15] Pearls와 Cormen 등에 의해 그들의 책 "Introduction to Algorithms"^[16]에서 대중화되었습니다.대부분의 공식에서 이 스킴은 배열의 마지막 요소를 피벗으로 선택합니다.이 알고리즘은 다른 인덱스 j를 사용하여 어레이를 스캔할 때 인덱스 i를 유지하며, lo에서 i-1(포함)까지의 요소는 피벗보다 작고, i에서 j(포함)까지의 요소는 피벗과 같거나 크다.이 계획은 보다 콤팩트하고 이해하기 쉽기 때문에, Hoare의 원래 계획보다 효율이 떨어지지만, 예를 들어 모든 요소가 ^[17]동일할 때 도입 자료에서 자주 사용됩니다.어레이가 이미 ^[10]정상일 경우 이 방식은 O(n²)로 저하됩니다.성능 향상을 위해 다양한 변형이 제안되어 왔습니다. 여기에는 피벗 선택, 등가 요소 처리, 소형 어레이 삽입 정렬 등의 기타 정렬 알고리즘이 포함됩니다.의사 코드에서 배열 A의 lo에서 hi(포함)까지 요소를 정렬하는 퀵소트는 다음과 ^[16]같이 나타낼 수 있습니다.

끓여정렬합니다는(의 부분)배열, 파티션으로, 그 알고리즘을 정렬하 quicksort(A, lo, 안녕하세요)분열은 //는지 확인한다 지수에 정확한 경우 그럼>)안녕 그럼<0다음 돌아오//분할 배열하고 피봇 지수 p:)partition(A, lo, 안녕하세요)//을 가르다 두 파티션 quicksort(A, lo, p-1)을 끓여좌파 측면이다.pi의로 피봇을 끓여임시 피벗 지수 i:)lo-1j:=lo-1만약 현재 요소보다 작거나 중심에 동일하거나 A[j]<> 적다^//니야 안녕 회전한 다음 //이 갖도록 대한 Vot quicksort(A, p+1, 안녕하세요!)피봇을 끓여오른쪽 측면 나눗셈을 합니다 두 파티션으로 array 알고리즘 partition(A, lo, 안녕하세요):)pivot은 A[안녕하세요]을 끓여는 마지막 요소를 선택합니다//.porary 피벗 인덱스 forward i : = i + 1 // 현재 요소를 임시 피벗 인덱스 스왑 A[i]에 있는 요소와 스왑합니다. A[j] // 피벗 요소를 올바른 피벗 위치(작은 요소와 큰 요소 사이)로 이동합니다. i : = i + 1 스왑 A[i]를 A[hi]와 함께 되돌립니다. ///

어레이 전체의 정렬은 quicksort(A, 0, 길이(A) - 1)로 이루어집니다.

Hoare 파티션 구성표

Tony Hoare가 설명한 원래 파티션 스킴은 분할되는 어레이의 양 끝에서 시작하여 반전을 검출할 때까지 서로 향해 이동하는 두 개의 포인터(영역 내 지표)를 사용합니다.첫 번째 포인터에서 한 쌍의 요소(피벗 값에 대한 Hoare의 용어)와 두 개의 포인터보다 작은 요소의 쌍입니다.두 번째 포인터입니다.이 시점에서 첫 번째 포인터가 두 번째 포인터보다 앞일 경우 이들 요소는 서로 잘못된 순서로 정렬되어 ^[18]교환됩니다.그 후 포인터는 안쪽으로 이동되고 반전 검색이 반복됩니다.결국 포인터가 교차할 때(첫 번째 포인트 이후), 교환은 실행되지 않습니다.교차된 포인터의 분할점이 있는 유효한 파티션이 발견됩니다(교차된 포인터 사이에 엄밀하게 존재할 수 있는 엔트리는 t와 동일합니다).그는 피벗하며 형성된 두 하위 항목에서 모두 제외될 수 있다.)이 공식에서는 1개의 서브 범위가 원래 범위 전체로 판명될 수 있으며, 이로 인해 알고리즘의 진보를 방해할 수 있습니다.따라서 Hoare는 (필요에 따라) 이격에 가장 가까운 서브레인지 엘리먼트와 교환한 후 피벗 엘리먼트를 제외함으로써 최종적으로 피벗 엘리먼트를 포함한 서브레인지의 크기를 줄일 수 있음을 규정함으로써 퀵소트의 종료를 보증한다.

이 원래 설명과 관련하여 구현은 종종 작지만 중요한 변화를 일으킨다.특히, 아래에 제시된 스킴에는 반전 후보 간의 피벗과 동일한 요소가 포함되어 있습니다(따라서 "초과" 및 "초과" 대신 "초과" 및 "초과"가 사용됩니다). 공식은 다음을 사용합니다.반복하는 것보다...이는 엄격한 비교 연산자의 사용에 의해 실제로 반영된다.)바운드와 동일한 요소를 교환할 이유는 없지만 이 변경으로 포인터 자체에 대한 테스트를 생략할 수 있습니다.이러한 테스트는 범위를 벗어나지 않도록 하기 위해 필요합니다.실제로 피벗 값의 적어도1개의 인스턴스가 범위 내에 존재하기 때문에 어떤 포인터의 첫 번째 어드밴스먼트가 이 인스턴스를 통과할 수 없습니다.일단 교환이 실행되면 이들 교환된 요소는 포인터를 발견한 포인터보다 완전히 앞서기 때문에 포인터가 실행되지 않습니다.(lat)ter는 사용된 검정과는 별개로 참이므로 첫 번째 반전을 찾을 때만 포함 검정을 사용할 수 있습니다.그러나 전체 테스트를 사용하면 범위 내의 모든 요소가 동일한 경우 중간 부근의 분할을 찾을 수 있으므로 동일한 요소를 여러 개 가진 배열 정렬에서 중요한 효율성을 얻을 수 있습니다.)비진행 분리의 위험은 Hoare가 기술한 것과 다른 방법으로 회피한다.이러한 분리는 반전이 발견되지 않을 때만 발생할 수 있으며, 첫 번째 반복 시 두 포인터가 피벗 요소로 진행됩니다(그 후 두 포인터는 교차한 것으로 간주되며 교환은 이루어지지 않습니다).반환되는 나눗셈은 두 번째 포인터의 마지막 위치 이후이므로 피벗이 범위의 마지막 요소이고 다른 모든 요소가 그보다 작은 경우 피벗을 피해야 합니다.따라서 피벗 선택은 최종 요소(Hoare 설명에서는 범위 내의 모든 요소일 수 있음)를 피해야 합니다.이 작업은 ^[19]함수를 사용하여 중간 위치를 반올림함으로써 수행됩니다.이는 Hoare 파티션 스킴 구현의 정확성에 대한 주장이 미묘할 수 있으며, 이를 오해하기 쉽다는 것을 보여준다.

의사 ^[16]코드에서는

끓여정렬합니다는(의 부분)배열, 파티션으로 구분된다면, quicksort(A, lo, 안녕하세요)경우 그럼>이 알고리즘을 정렬하고,=0일 아는 것과,&안녕>=0일 아는 것과,&lo<>hi 다음 p:)partition(A, lo, 안녕하세요)quicksort(A, lo, p)//참고:피봇 이제 포함되어 있quicksort(A, p+1, 안녕하세요!)을 끓여나눗셈을 합니다 array에 두개의 파티션 알고리즘 partiti.On(A, lo, 안녕하세요)은//피벗.Value피벗:)A[바닥((hi+lo)/2)]는 배열 // 왼쪽 지수의 중간 나의 값 //:)lo-1// 맞아 지수 j:=안녕하세요+영원히 움직여 왼쪽 지수는 오른쪽으로//1루프 한번쯤은 있고 끓여에 있는 요소를 왼쪽 지수는 피벗보다 적다에서 난 기억:)는 동안 A[나는]< 나는 1+, pivot// t.에 대한 정확한 지수 이동시키시오그 왼쪽 이상 // 오른쪽 인덱스의 요소가 피벗보다 클 때, A [j] > 피벗 // 인덱스가 교차하면 반환하고 j // 왼쪽 및 오른쪽 인덱스의 요소를 A[i]와 스왑합니다.

전체 배열은 빠른 정렬(A, 0, 길이(A) - 1)별로 정렬됩니다.

Hoare의 스킴은 평균적으로 3배 적은 스왑을 하기 때문에 Lomuto의 파티션 스킴보다 효율적입니다.또, 전술한 바와 같이, 모든 값이 같은 경우에도, 실장에서는 균형 있는 파티션이 작성되고 있습니다만, 로무토의 스킴은 그렇지 않습니다.^{[10][self-published source?]}Lomuto의 파티션 스킴과 마찬가지로 Hoare의 파티션 분할도 피벗이 첫 번째 또는 마지막 요소로 선택된 경우 이미 정렬된 입력에 대해 QuickSort가 O(n²)로 저하됩니다.그러나 중간 요소를 피벗으로 하면 (거의) 동일한 크기의 파티션에서 스왑이 없는 정렬된 데이터가 생성되므로 QuickSort의 최적의 동작(O(n log(n))으로 이어집니다.다른 것들과 마찬가지로 Hoare의 파티셔닝은 안정적인 종류를 만들어내지 못합니다.이 방식에서 피벗과 피벗과 동일한 요소는 파티션 단계 후에 파티션 내의 어느 곳에나 도달할 수 있으며, 단일 요소가 있는 파티션의 기본 케이스에 재귀로 도달할 때까지 정렬되지 않을 수 있기 때문에 피벗의 최종 위치는 반환되는 인덱스에 반드시 있는 것은 아닙니다.메인 알고리즘이 재귀하는 다음 2개의 세그먼트는 (lo..p)와 (p+1)가 아닌 (element pivot피벗)과 (p+1..hi)입니다.로무토의 ^[why?]스킴에서와 같이.

후속 반복(이전 단락의 확장)

메인 알고리즘이 재귀하는 다음 두 세그먼트에 대해 조금 더 확장해 보겠습니다."do..."에서는 엄격한 대조군(> <)을 사용하고 있기 때문에while'은 범위를 벗어나는 것을 방지하기 위해 루프하지만 피벗 자체가 파티션 기능의 다른 요소와 스왑될 수 있습니다.따라서 파티션 함수로 반환되는 인덱스는 반드시 실제 피벗 위치에 있는 것은 아닙니다.예를 들어 [5, 2, 3, 1, 0]의 예에 따라 첫 번째 파티션 뒤에 어레이가 [0, 2, 1, 3, 5]가 되면 반환되는 "인덱스"는 2가 됩니다. 즉, 실제 피벗에서 파티션 시작 시 선택한 인덱스는 숫자 3이 됩니다.이 예에서는 파티션 함수의 반환된 인덱스를 후속 재귀에 어떻게 포함시킬 필요가 있는지 알 수 있습니다.그 결과, 재귀 온(lo..p)과 (p+1) 중 하나를 선택할 수 있습니다.hi) 또는 (lo..p - 1) 및 (p..두 가지 옵션 중 어느 쪽을 선택할지는 인덱스가 교차할 때 파티션 함수로 반환되는 인덱스(i 또는 j)와 파티션 함수에서 피벗을 선택하는 방법(바닥 v. 천장)에 따라 달라집니다.

먼저 (lo..p)와 (p+1)의 재귀 선택지를 검토하겠습니다.hi)를 사용하여 동일한 요소가 여러 개 존재하는 배열을 정렬합니다. [0, 0]파티션 함수에서 인덱스가 교차한 후 인덱스 i('래터' 인덱스)가 반환되면 인덱스 1은 첫 번째 파티션 후에 반환됩니다.(lo..p)의 후속 재귀는 (0, 1)이 됩니다.이것은, 같은 배열[0, 0]에 대응합니다.무한 재귀의 원인이 되는 비진행 분리가 발생합니다.따라서 (lo..p) 및 (p+1)에서 재귀하는 것은 명백합니다.hi) 재귀의 왼쪽 절반은 반환된 인덱스를 포함하므로 비재귀 시나리오에서는 "꼬리"를 제외하는 것이 파티션 함수의 작업입니다.즉, i 대신 지수 j(지수가 교차할 때 "이전" 지수)를 반환해야 한다.유사한 논리로 이미 정렬된 배열 [0, 1]의 예를 고려할 때, 포인터가 "latter"가 아닌 "poor"에서 멈추도록 하기 위해 피벗을 선택해야 합니다("ceiling"을 피벗으로 하면 인덱스 1이 반환되어 (lo..p)에 포함되므로 무한 재귀가 발생합니다).마지막 요소를 피벗으로 선택하지 않아야 하는 것과 동일한 이유입니다.

(lo..p - 1) 및 (p..)의 재귀 선택.hi)는 위와 동일한 논리를 따릅니다.재귀의 오른쪽 절반에는 반환된 인덱스가 포함되므로 비진행 시나리오에서는 "헤드"를 제외하는 것이 파티션 함수의 작업입니다.파티션 함수의 인덱스 i(인덱스가 교차한 후의 "레이터" 인덱스)를 반환해야 하며 "천장"을 피벗으로 선택해야 합니다.동일한 요소가 여러 개 존재하는 배열([0, 0])과 이미 정렬된 배열[0, 1]의 예를 살펴보면 두 가지 뉘앙스가 명확합니다.같은 이유로 재귀 버전에서는 첫 번째 요소를 피벗으로 선택하지 않도록 해야 합니다.

구현 문제

피벗 선택

초기 버전의 QuickSort에서는 파티션의 왼쪽 끝에 있는 요소가 피벗 요소로 선택되는 경우가 많았습니다.안타깝게도 이로 인해 이미 정렬된 어레이에서 최악의 동작이 발생하며 이는 일반적인 사용 ^[20]사례입니다.이 문제는 피벗에 대한 랜덤 인덱스를 선택하고 파티션의 중간 인덱스를 선택하거나 (특히 긴 파티션의 경우) 피벗에 대한 파티션의 첫 번째, 중간 및 마지막 요소의 중앙값을 선택하면 쉽게 해결되었습니다(^[21]Sedgewick 권장).이 "중간" 규칙은 정렬된(또는 역 정렬된) 입력의 경우를 카운터하여 입력 순서에 대한 정보가 없는 경우 단일 요소를 선택하는 것보다 최적의 피벗(진정한 중앙값)을 더 잘 추정할 수 있습니다.

Lomuto 파티션의 코드 스니펫의 중위수:

mid : [ mid ]< A [ lo ]< A [ lo ]를 A [ mid ]로 스왑 하는 경우, A [ hi ]< A [ lo ]를 A [ hi ]로 스왑 하는 경우, A [ mid ]< A [ hi ]를 A [ hi ]로 스왑 하는 경우, A [ hi] 피벗= A [ hi]로 스왑 합니다.

중앙값 설정A[hi]첫 번째로, 그 다음에 그 새로운 가치A[hi]위의 기본 알고리즘에서와 같이 피벗에 사용됩니다.

구체적으로는 n개의 요소를 랜덤 피벗 선택으로 정렬하기 위해 필요한 예상 비교 횟수는 1.386n log n이다(see 랜덤화 퀵소트 분석 참조).중앙값 of 3 피벗을 사용하면 예상되는 ^[7]스왑 수가 3% 증가하지만 이 값은 C ≈ 1.188n log n으로_{n, 2} 낮아집니다.보다 강력한 피벗 규칙은 대규모 어레이의 경우 다음과 같이 정의된^[7] 재귀 중위수 3(Mo3)을 선택하는 것입니다.

ninther(a) = 중위수(Mo3(처음)1/3 a, Mo3, Mo3(a의 중간 1/3), Mo3(a의 최종 1/3)

정수 오버플로가 존재하기 때문에 피벗 요소를 선택하는 것도 복잡합니다.정렬 중인 하위 배열의 경계 지수가 충분히 클 경우 중간 지수(lo + hi)/2에 대한 순진 표현식은 오버플로를 일으키고 잘못된 피벗 지수를 제공합니다.예를 들어, lo + (hi-lo)/2를 사용하여 더 복잡한 산술의 비용으로 중간 요소를 색인화함으로써 이를 극복할 수 있습니다.피벗 요소를 선택하는 다른 방법에서도 유사한 문제가 발생합니다.

반복 요소

위에서 설명한 Lomuto 파티션스킴 등의 파티션알고리즘(좋은 피벗값을 선택하는 알고리즘도 포함)에서는 반복적인 요소가 많은 입력에 대해 QuickSort의 퍼포먼스가 저하됩니다.이 문제는 모든 입력 요소가 동일한 경우 명백합니다.각 재귀 시 왼쪽 파티션이 비어 있고(입력 값이 피벗보다 작지 않음), 오른쪽 파티션이 1개의 요소만 감소합니다(피벗이 제거됨).따라서 Lomuto 파티션 스킴은 동일한 값의 배열을 정렬하는 데 2차 시간이 걸립니다.단, Hoare 파티션스킴 등의 파티션알고리즘에서는 일반적으로 반복적인 요소에 의해 파티셔닝이 개선되고 피벗과 동일한 요소의 불필요한 스왑이 발생할 수 있지만 반복적인 요소의 수가 증가함에 따라 실행 시간이 감소합니다(메모리 캐시에 의해 스왑 오버헤드가 감소합니다).모든 요소가 동일한 경우 Hoare 파티션스킴은 불필요하게 요소를 스왑하지만 위의 Hoare 파티션섹션에서 설명한 바와 같이 파티션 자체가 최선의 경우입니다.

(때때로 네덜란드 국기라고 불리는 problem[7])은 Lomuto 파티션 계획 문제를 해결하기 위해, 대체 linear-time 파티션 루틴 그 세 그룹:값 피봇 이하로 값을 구분하고 피봇에 값 피봇보다 더 큰 평등을 중시한다.(벤틀리와 매킬 로이고 wa" 뚱뚱한 파티션"라고 부른다 사용될 수 있다.가 어떻게 되버전 7 Unix의 qsort에 이미 실장되어 있습니다.)^[7]피벗과 동일한 값은 이미 정렬되어 있으므로 보다 작거나 보다 큰 파티션만 반복적으로 정렬하면 됩니다.의사코드에서는 퀵소트 알고리즘은

알고리즘 quicksort(A, lo, hi)는 lo < hi이면 p : = 피벗(A, lo, hi) 왼쪽, 오른쪽 : = 파티션(A, p, lo, hi) // 노트: 다중 반환 값 quicksort(A, lo, 왼쪽 - 1) quicksort(A, 오른쪽 + 1, hi)

그partition알고리즘은 인덱스를 중간 파티션의 첫 번째('맨 왼쪽') 항목과 마지막('맨 오른쪽') 항목으로 반환합니다.파티션의 모든 항목은 다음과 같습니다.p따라서 정렬됩니다.따라서 파티션의 항목을 재귀 호출에 포함할 필요가 없습니다.quicksort.

현재 알고리즘의 최선의 경우는 모든 요소가 동일하거나 k µn 요소의 작은 세트에서 선택되었을 때 발생합니다.모든 요소가 동일한 경우 변경된 QuickSort는 빈 서브어레이에서 2개의 재귀 콜만 실행하므로 선형 시간 내에 종료됩니다(전제가partitionsubroutine은 선형 시간보다 오래 걸리지 않습니다.

최적화

Sedgewick이 제안하고 실제로 널리 사용되는 다른 두 가지 중요한 최적화는 다음과 같습니다.^[22][23]

• 최대 O(log n) 공간을 사용하려면 먼저 파티션의 작은 쪽으로 반복한 후 테일콜을 사용하여 다른 쪽으로 반복하거나, 현재 정렬된 작은 쪽을 포함하지 않도록 파라미터를 업데이트하고 더 큰 쪽을 정렬합니다.
• 요소의 수가 임계값(약 10개 요소)을 밑돌면 삽입 정렬 등의 비재귀 정렬 알고리즘으로 전환하여 이러한 소규모 어레이에서 스왑, 비교 또는 기타 작업을 더 적게 수행합니다.이상적인 '임계값'은 특정 구현의 세부 사항에 따라 달라집니다.
• 이전 최적화의 오래된 변형입니다. 요소의 수가 임계값 k보다 작을 경우 단순히 중지하고 배열 전체가 처리된 후 삽입 정렬을 수행합니다.재귀를 조기에 정지하면 배열이 k 정렬된 상태로 남습니다.즉, 각 요소는 최종 정렬된 위치에서 최대 k개 떨어진 위치에 있습니다.이 경우 삽입 정렬은 정렬을 완료하는 데 O(kn) 시간이 걸립니다. k가 ^{[24][15]: 117} 상수일 경우 선형입니다."많은 작은 정렬" 최적화에 비해 이 버전은 실행하는 명령 수가 적을 수 있지만 최신 컴퓨터에서 ^[25]캐시 메모리를 최적으로 사용하지 않습니다.

병렬화

QuickSort의 분할 및 정복 공식은 태스크 병렬화를 사용한 병렬화를 가능하게 합니다.분할 단계는 병렬 접두사 합계 알고리즘을 사용하여 분할된 ^[26][27]배열 섹션의 각 배열 요소에 대한 인덱스를 계산함으로써 수행됩니다.크기 n의 배열이 주어지면 분할 스텝은 O(n)시간 내에 O(n)작업을 하고 O(n)의 추가 스크래치 공간을 요구한다.배열을 분할한 후 두 개의 파티션을 병렬로 재귀적으로 정렬할 수 있습니다.피벗의 이상적인 선택이라고 가정하면 병렬 퀵소트는 O(n) 추가 공간을 사용하여² O(n log n) 시간 내에 O(n log n) 작업 시 크기 n의 배열을 정렬한다.

QuickSort는 효율적인 병렬화를 복잡하게 하는 병합 정렬과 같은 대체 정렬 알고리즘과 비교할 때 몇 가지 단점이 있습니다.QuickSort의 divide-and-conquer 트리의 깊이는 알고리즘의 scalability에 직접 영향을 미치며, 이 깊이는 알고리즘의 피벗 선택에 크게 좌우됩니다.또한 파티셔닝 단계를 효율적으로 일괄적으로 병렬화하는 것은 어렵습니다.스크래치 공간을 사용하면 파티셔닝 단계가 간소화되지만 알고리즘의 메모리 설치 공간과 지속적인 오버헤드가 증가합니다.

다른 보다 정교한 병렬 정렬 알고리즘은 더 나은 시간 ^[28]범위를 달성할 수 있습니다.예를 들어, 1991년에 David Powers는 파티셔닝을 ^[29]암묵적으로 실행함으로써 n개의 프로세서를 탑재한 CRCW(동시 읽기 및 동시 쓰기) PRAM(Parallel Random-Access Machine) 상에서 O(log n) 시간에 동작할 수 있는 병렬화된 Quicksort(및 관련 기수 정렬)에 대해 설명했습니다.

형식 분석

최악의 경우 분석

가장 불균형한 파티션은 파티셔닝 루틴에서 반환되는 하위 목록 중 하나가 크기 n - ^[30]1일 때 발생합니다.이 문제는 피벗이 목록에서 가장 작거나 큰 요소일 때 발생할 수 있습니다.또는 일부 구현(예를 들어 위에서 설명한 바와 같이 Lomuto 파티션 방식)에서는 모든 요소가 동일할 때 발생할 수 있습니다.

모든 파티션에서 이 문제가 반복적으로 발생할 경우 각 재귀 호출은 이전 목록보다 크기가1 작은 목록을 처리합니다.그 결과 사이즈1의 리스트에 도달하기 전에n - 1의 네스트콜을 발신할 수 있습니다.즉, 콜 트리가 n - 1 네스트콜의 선형 체인임을 의미합니다.ih 콜은 O(n - i)를 사용하여 파티션을 만듭니다.또,${\displaystyle \underset{i}{\overset{}{}}}$ i ${\displaystyle \underset{}{\overset{}{=}}}$ ${\displaystyle \underset{}{\overset{}{0}}}$ (${\displaystyle n}$ -${\displaystyle i}$ )$$ ( ${\displaystyle {n\mathrm{}}^{}}$ )${\displaystyle {}^{}}$\ $displaystyle$\ $textstyle _$ {$i =$ $0$}^{ n$$（ n - i ） =$O(n^{2$이므로 이 경우 QuickSort에는 O(n²) 시간이 걸립니다.

베스트 케이스 분석

가장 균형 잡힌 경우 파티션을 수행할 때마다 목록을 거의 동일한 두 부분으로 나눕니다.즉, 재귀 콜마다 절반 크기의 리스트가 처리됩니다.따라서 사이즈 1의 리스트에 도달하기 전에 n개의 네스트된 콜만₂ 로깅할 수 있습니다.이는 콜 트리의 깊이가 log₂ n임을 의미합니다.단, 콜 트리의 같은 레벨에 있는2개의 콜은 원래 리스트의 같은 부분을 처리하지 않습니다.따라서 각 콜레벨은 모두 O(n)시간만 필요로 합니다(각 콜은 일정한 오버헤드를 가지지만 각 레벨에 O(n)콜만 존재하기 때문에 O(n)팩터에 포함됩니다).그 결과 알고리즘은 O(n log n) 시간만 사용합니다.

평균 사례 분석

n개의 개별 요소 배열을 정렬하기 위해 퀵소트는 O(n log n) 시간이 걸리며, n개의 요소의 모든 n! 배열에 대해 동일한 확률로 평균을 구합니다.여기서는 QuickSort의 작업에 대한 다양한 통찰력을 제공하는 이 주장에 대한 세 가지 일반적인 증거를 제시합니다.

백분위수 사용

각 피벗의 순위가 50% 중간(즉, 25번째 백분위수와 75번째 백분위수 사이)인 경우 각 변에서 요소를 최소 25%, 최대 75%로 분할합니다.이러한 피벗을 일관되게 선택할 수 있다면 O(n log $n)$ 알고리즘이 생성되어 크기1의 $리스트$에 도달할 때까지 목록을 ${\displaystyle {\mathrm{최대}}_{}}$ ${\displaystyle {log\mathrm{}}_{}}$4/$3 n으로 분할하기$만 하면 됩니다.

입력이 랜덤 순열일 경우 피벗은 랜덤랭크를 가지기 때문에 50% 중반이 되는 것은 보증되지 않습니다.다만, 랜덤 치환으로부터 시작하면, 각 재귀 콜의 피벗에는 랜덤 랭크가 포함되어 있기 때문에, 피벗은 약 반수의 50%의 중간이 됩니다.그걸로 충분합니다.동전이 뒤집힌다고 상상해 보세요: 앞면은 피벗의 순위가 중간 50%에 있고, 뒷면은 그렇지 않다는 것을 의미합니다.이제 동전이 k개의 앞면이 될 때까지 뒤집혀진다고 상상해보세요.시간이 오래 걸릴 수 있지만, 평균적으로 2k번의 공중제비만 필요하며, 10k번의 공중제비 후에 동전이 k번의 헤드를 얻지 못할 가능성은 매우 희박하다(이것은 체르노프 경계를 사용하여 엄격하게 할 수 있다.같은 인수에 의해 Quicksort의 재귀는 평균 ${\displaystyle {2개}_{}}$의 $로그$4/${\displaystyle 3}$의$$콜 $심도$로 $종료됩니다.$단, 그 평균 콜 심도가 O($log$ n$)$이고 콜 트리 프로세스의 각 레벨이 최대 n개의 요소인 경우, 수행된 작업의 총량은 평균 O(log n)가 됩니다.알고리즘에서는 피벗이 중간 위치에 있는지 확인할 필요가 없습니다.단, 일정 시간 동안 피벗을 누르면 원하는 복잡도에 충분합니다.

반복 사용

대체 접근법은 크기 n의 목록을 정렬하는 데 필요한 시간인 T(n) 인자에 대한 반복 관계를 설정하는 것입니다.대부분의 경우 단일 QuickSort 콜에는 O(n) 작업과 사이즈0 및 n-1 리스트의 2개의 재귀 콜이 포함됩니다.따라서 반복 관계는 다음과 같습니다.

${\displaystyle T(n)=O(n)+T(0)+T(n-1)=O(n)+T(n-1).}$

이는 삽입 정렬 및 선택 정렬과 동일한 관계이며 최악의 경우 T(n) = O(n²)로 해결됩니다.

가장 균형 잡힌 경우 1개의 QuickSort 콜에는 O(n) 작업과 크기n/2의 리스트 상의 2개의 재귀 콜이 포함됩니다.따라서 반복 관계는 다음과 같습니다.

$\displaystyle T(n)=O(n)+2T\left({\frac {n}{2}}\오른쪽).}$

나눗셈과 나눗셈의 반복에 대한 기본 정리는 T(n) = O(n log n)라는 것을 알려준다.

O(n log n) 예상 시간의 복잡성에 대한 공식 증명 개요는 다음과 같다.중복은 선형 시간 전·후 처리로 처리하거나 분석된 경우보다 쉽게 처리할 수 있으므로 중복이 없다고 가정한다.입력이 랜덤 순열인 경우 피벗의 순위는 0 ~ n - 1 사이의 균일한 랜덤입니다.분할의 결과 부분은 크기 i와 n - i - 1을 가지며, i는 0에서 n - 1까지 균일 랜덤입니다.따라서 분할의 모든 가능한 평균은 n - 1이며, 입력 시퀀스의 모든 배열에 대한 평균 비교 횟수는 반복을 해결함으로써 정확하게 추정할 수 있습니다.ce 관계:

${\displaystyle C(n)=n-1+{\frac {1}{n}\sum _{i=0}^{n-1}(C(i)+C(n-i-1)=n-1+{\frac {2}{n}}\sum _{i=0}^{n-1}C(i)}$

${\displaystyle nC(n)=n(n-1)+2\sum _{i=0}^{n-1}C(i)}$

${\displaystyle nC(n)-(n-1)C(n-1)=n(n-1)-(n-2)+2C(n-1)}$

${\displaystyle nC(n)=(n+1)C(n-1)+2n-2}$

${\displaystyle{\begin{정렬}{\frac{C ᆨ}{n+1}}&={\frac{C ᆩ}{n}}+{\frac{2}{n+1}}-{\frac{2}{n ᆪ}}\leq{\frac{C ᆫ}{n}}+{\frac{2}{n+1}}\\&, ={\frac{C ᆬ}{n-1}}+{\frac{2}{n}}-{\frac{2}{ᆭ n}}+{\frac{2}{n+1}}\leq{\frac{C ᆮ}{n-1}}+{\frac{2}{n}}+{\frac{2}{n+1}}\\&, \)\vdots \\&, ={\frac{C ᆯ}{2}}+\sum _{i=2}^{n.}{\frac{2}{i+1}}\leq 2\sum _{i=1}^{n-1}{\frac {1}{i}}\약 2\int _{1}^{n}{x}\mathrm {d} x=2\ln n\end {aligned}}}$

반복을 해결하면 C(n) = 2n ln n 1 1.39n₂ log n이 됩니다.

즉, 평균적으로 QuickSort의 성능이 최상의 경우보다 약 39% 더 나쁘다는 것을 의미합니다.그런 의미에서 최악의 경우보다는 최선의 경우에 가깝다.비교 정렬에서는 평균 log(n!) 미만의₂ 비교를 사용하여 n개의 항목을 정렬할 수 없습니다(비교 정렬에서 설명됨). n이 클 경우 스털링의 근사치가 log(n!)≈ n(log₂ n - log₂ e)을 산출하므로₂ 퀵 정렬은 이상적인 비교 정렬보다 크게 나쁘지 않습니다.이 빠른 평균 실행 시간은 QuickSort가 다른 정렬 알고리즘에 대해 실질적으로 우위를 점하는 또 다른 이유입니다.

이진 검색 트리 사용

다음 BST(Binary Search Tree)는 QuickSort의 각 실행에 대응합니다.첫 번째 피벗은 루트 노드, 왼쪽 절반의 피벗은 왼쪽 서브트리의 루트, 오른쪽 절반의 피벗은 오른쪽 서브트리의 루트 등입니다.QuickSort 실행 비교 횟수는 삽입 시퀀스에 의한 BST 구축 중 비교 횟수와 동일합니다.따라서 랜덤화 퀵소트의 평균 비교 수는 삽입된${\displaystyle }$값(${\displaystyle {}_{}}$ 1,${\displaystyle {}_{}}$x${\displaystyle {}_{}{2\mathrm{}}_{}}$,${\displaystyle \dots ,}$ ${\displaystyle x_{}}$ n$)$ {$display (x_{1}, x_{2},$ \$ldots, x_{n})$이 랜덤 순열을 형성할 때의 평균 BST 구축 비용과 동일합니다.

랜덤 치환을 형성하는 값의 시퀀스$({\displaystyle {x\mathrm{}}_{}}$1, ${\displaystyle {}_{}{2\mathrm{}}_{}}$,${\displaystyle \dots ,}$ ${\displaystyle {}_{}}$ $)$ {$displaystyle (x_{1$},$x_{2},\ldots,x_{n})$ 삽입에$$ 의해 작성된 BST에 대해 설명합니다.C는 BST 작성 비용을 나타냅니다. i j< c 、 \ $displaystyle$ C = \ $sum$_ { i } \ $sum$ _ {$j$ <$i$}。${\displaystyle {여기}_{}}$서 c${\displaystyle {}_{}}$i$$,$$ { $displaystyle$ c$_ i$ , j$}$는 $x_style x_i$$}$ $삽입{\displaystyle {}_{}}$ 시 비교가 있었는지 여부를 나타내는 바이너리 랜덤 변수입니다.

기대 선형성에 따라 C의 $E{\displaystyle \mathrm{}}$ ${\displaystyle }$ [ $]$ \ $displaystyle \operatorname { E$} [ $C$] i < i ( c , j) { $displaystyle$ \$operatorname${ E } [ C ]$=$_$sum$ { i }$입니다$.

i와 j<i를 수정합니다.${\displaystyle {}_{}}$ ${\displaystyle {x\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{x\mathrm{}}_{}}$2, ${\displaystyle \dots ,}$ x$$(\$displaystyle {x_{1},$x_${2},\ldots,x_{j$는 정렬 후 j+1 간격을 정의합니다.핵심적인 구조적 관찰은 $(\$$displaystyle x_{i})$가 $(\$j$\})$에 $인접$한 2개의 간격 중 하나에 $xi{\displaystyle {}_{}}$(\$displaystyle x_{i})$가 $포함$되는 경우에만$$ $알고리즘$에서 $xi{\displaystyle {}_{}}$(\displaystyle x_{$j})$

$({\displaystyle }$ ${\displaystyle {x\mathrm{}}_{}{}_{}}$, x${\displaystyle {}_{}{2\mathrm{}}_{}}$,${\displaystyle \dots ,}$ ${\displaystyle {}_{}{n}_{}}$ $){displaystyle (x_{1},x_{2},\ldots,x_{n}}$은 랜덤 치환이며$,{\displaystyle }$ (${\displaystyle {}_{}{}_{}}$1, x${\displaystyle {2\mathrm{}}_{}}$, ${\displaystyle \dots ,}$ ${\displaystyle {}_{}}$ ${\displaystyle j_{}{}_{}{}_{}}$ $){displaystyle (x_1},x_{2},\ldots,x_{i})$도 랜덤 치환입니다.$(\$는 $정확히{\displaystyle \frac{\mathrm{}}{}}$ ${\displaystyle \frac{2j}{}}$ ${\displaystyle \frac{+}{}}$ $(\$입니다.

간단한 계산으로 끝납니다.

${\displaystyle \operatorname {E} [C]=\sum _{i}\sum _{j<i}{\frac {2}{j+1}}=O\left(\sum _{i}\log i\right)=O(n\log n).}$

공간의 복잡성

QuickSort에서 사용하는 공간은 사용되는 버전에 따라 달라집니다.

퀵소트의 임플레이스 버전은 다음 전략을 사용하여 신중하게 구현될 경우 최악의 경우에도 O(log n)의 공간 복잡성을 가집니다.

• 인플레이스 파티셔닝이 사용됩니다.이 불안정한 파티션에는 O(1) 공간이 필요합니다.
• 파티셔닝 후 요소가 가장 적은 파티션이 가장 먼저(재귀적으로) 정렬되므로 최대 O(log n) 공간이 필요합니다.그런 다음 테일 재귀 또는 반복을 사용하여 다른 파티션이 정렬됩니다.이것은 콜스택에 추가되지 않습니다.이 아이디어는 위에서 설명한 바와 같이 R에 의해 설명되었다. Sedgewick: 스택 깊이를 O(log n)^[21][24]로 제한합니다.

파티션이 불안정하고 인플레이스한 QuickSort에서는 재귀 호출을 하기 전에 일정한 추가 공간만 사용합니다.QuickSort는 중첩된 각 재귀 호출에 대해 일정한 양의 정보를 저장해야 합니다.최적의 경우는 최대 O(log n)의 네스트된 재귀 호출을 하기 때문에 O(log n) 공간을 사용합니다.단, 재귀 콜을 제한하는 Sedgewick의 트릭이 없으면 최악의 경우 QuickSort는 O(n) 네스트된 재귀 콜을 생성하여 O(n) 보조 공간을 필요로 할 수 있습니다.

비트 복잡도의 관점에서 보면 lo 및 hi와 같은 변수는 일정한 공간을 사용하지 않습니다.N개의 항목으로 인덱스하려면 O(log n)비트가 필요합니다.스택 프레임마다 이러한 변수가 존재하기 때문에 Sedgewick의 트릭을 사용하는 퀵소트에는 O(log n)²비트의 공간이 필요합니다.그러나 목록에 다른 요소가 포함되어 있다면 적어도 O(n log n) 비트의 공간이 필요하기 때문에 이 공간 요건은 그다지 심각하지 않습니다.

일반적이지 않은 다른 버전의 QuickSort는 작업 스토리지에 O(n) 공간을 사용하며 안정적인 정렬을 구현할 수 있습니다.동작중의 스토리지를 사용하면, 입력 어레이를 간단하게 안정된 방법으로 분할해, 재귀 콜을 연속하는 입력 어레이에 카피할 수 있습니다.Sedgewick의 최적화는 여전히 적절합니다.

다른 알고리즘과의 관계

QuickSort는 이진 트리 정렬의 공간 최적화 버전입니다.명시적 트리에 순차적으로 항목을 삽입하는 대신, QuickSort는 항목을 재귀 호출에 의해 암시되는 트리에 동시에 정리합니다.두 알고리즘은 완전히 동일한 비교를 하지만 순서가 다릅니다.정렬 알고리즘의 바람직한 속성은 안정성입니다. 즉, 동일한 값을 비교하는 요소의 순서는 변경되지 않으므로 다중 키 테이블(디렉토리 또는 폴더 목록 등)의 순서를 자연스럽게 제어할 수 있습니다.이 속성은 in in sit(또는 in sit) quick sort(포인터와 버퍼에 일정한 추가 공간만 사용하고 명시적 또는 암묵적 재귀 관리를 위해 O(log n) 추가 공간 사용)에 대해 유지하기가 어렵습니다.포인터(리스트 또는 트리) 또는 파일(실효적인 리스트)을 사용한 표현으로 인해 추가 메모리를 포함하는 변형 퀵소트의 경우 안정성을 유지하는 것은 간단하다.데이터 구조가 복잡하거나 디스크에 바인딩되어 있을수록 일반적으로 가상 메모리 또는 디스크 사용이 증가하여 시간 비용이 증가하는 경향이 있습니다.

퀵소트의 가장 직접적인 경쟁자는 힙소트이다.힙소트의 실행 시간은 O(n log n)이지만, 힙소트의 평균 실행 시간은 일반적으로 임플레이스 ^[31]퀵소트보다 느린 것으로 간주됩니다.이 결과는 논란의 여지가 있다; 일부 출판물은 ^[32][33]그 반대이다.Introsort는 불량 케이스가 검출되면 퀵소트의 최악의 실행시간을 피하기 위해 힙소트로 전환하는 퀵소트의 변형입니다.

QuickSort는 또 다른 O(n log n) 정렬 알고리즘인 병합 정렬과도 경쟁합니다.Mergesort는 표준적인 in-place 퀵소트나 힙소트와는 달리 안정적인 정렬로 최악의 경우 성능이 우수합니다.mergesort의 주요 단점은 어레이에서 동작할 때 효율적인 구현에는 O(n) 보조 공간이 필요한 반면 in-place 파티셔닝과 테일 재귀가 포함된 Quicksort의 변형에는 O(log n) 공간만 사용한다는 것입니다.

Mergesort는 링크된 목록에서 매우 잘 작동하므로 보조 저장소의 양이 일정하지 않습니다.퀵소트는 링크된 목록을 사용하여 안정적인 정렬로 구현될 수 있지만 랜덤 액세스 없이 피벗 선택이 잘 되지 않는 경우가 많습니다.또한 Mergesort는 디스크 스토리지나 네트워크 연결 스토리지와 같이 접근이 용이한 미디어에 저장된 매우 큰 데이터 세트를 외부로 정렬하기 위한 알고리즘입니다.

2개의 버킷을 사용한 버킷 정렬은 QuickSort와 매우 유사합니다.이 경우 피벗은 실질적으로 값 범위의 중간에 있는 값으로 균일하게 분산된 입력에 대해 평균적으로 적합합니다.

선택 기반 피벗

선택 알고리즘은 숫자 리스트 중 k번째로 작은 것을 선택합니다.이것은 일반적으로 정렬보다 쉬운 문제입니다.간단하지만 효과적인 선택 알고리즘 중 하나는 퀵소트와 거의 동일한 방식으로 작동하며, 따라서 퀵셀렉트라고 합니다.차이점은 양쪽 서브리스트에서 재귀 콜을 발신하는 것이 아니라 원하는 요소를 포함하는 서브리스트에서 단일 테일재귀 콜만 발신한다는 것입니다.이 변경에 의해 평균 복잡도가 선형 또는 O(n) 시간으로 낮아져 선택에 최적이지만 최악의 경우 선택 알고리즘은 여전히 O²(n)입니다.

중위수 알고리즘의 중위수인 quickselect의 변형은 피벗을 더 신중하게 선택하므로(30번째와 70번째 백분위수 사이) 피벗이 데이터의 중간 근처에 있으므로 선형 시간 – O(n)가 보장됩니다.이 동일한 피벗 전략을 사용하여 O(n log n) 시간으로 퀵소트(중간자 퀵소트의 중위수)의 변형을 구성할 수 있습니다.그러나 피벗을 선택하는 데 드는 오버헤드는 상당하기 때문에 일반적으로 실제에서는 사용되지 않습니다.

보다 추상적으로, O(n) 선택 알고리즘이 주어지면, 퀵소트의 모든 단계에서 이상적인 피벗(중앙값)을 찾아 O(n log n) 실행 시간을 가진 정렬 알고리즘을 생성할 수 있다.이 변종의 실제 구현은 평균적으로 상당히 느리지만 최적의 선택 알고리즘이 최적의 정렬 알고리즘을 산출할 수 있다는 것을 보여주기 때문에 이론적으로 관심이 있습니다.

변종

멀티피봇 퀵소트

단일 피벗을 사용하여 2개의 서브어레이로 분할하는 대신 멀티피벗 퀵소트(멀티키소트^[25])는 s - 1 피벗을 사용하여 입력을 s개의 서브어레이로 분할합니다.Sedgewick과 다른 사람들은 1970년대 중반에 이미 이중 패리티 케이스(s = 3)를 검토했지만, 결과 알고리즘은 실제로 "패키지" ^[34]퀵소트보다 빠르지 않았다.1999년 프로세서 캐시를 효율적으로 사용하도록 조정된 가변 수의 피벗을 사용한 멀티쿼코트를 평가한 결과 명령 카운트가 약 20% 증가했지만 시뮬레이션 결과에 따르면 매우 ^[25]큰 입력에서 더 효율적이라고 합니다.2009년에^[11] Yaroslavski가 개발한 듀얼 피봇 퀵소트의 버전은 Java 7에서의 구현을 보증할 만큼 충분히 빠른 것으로 판명되었습니다.이것은, 원시 요소의 어레이를 정렬하는 표준 알고리즘(Timsort를 ^[35]사용해 오브젝트의 어레이를 정렬하는 것이 가능)입니다.이 알고리즘의 퍼포먼스 이점은 캐시 ^[36]퍼포먼스와 관련된 것이 대부분으로, 실험 결과에 따르면 3피봇 변형이 최신 ^[37][38]머신에서 훨씬 더 뛰어난 성능을 발휘할 수 있습니다.

외부 퀵소트

디스크 파일의 경우 QuickSort와 유사한 파티션에 기반한 외부 정렬이 가능합니다.외부 병합 정렬보다 느리지만 추가 디스크 공간이 필요하지 않습니다. 버퍼는 4개, 입력에 2개, 출력에 2개가 사용됩니다.N = 파일 내의 레코드 수, B = 버퍼당 레코드 수, M = N/B = 파일 내의 버퍼 세그먼트 수라고 합니다.데이터는 파일의 양 끝에서 안쪽으로 읽혀집니다.X는 파일 시작 부분에서 시작하는 세그먼트를 나타내고 Y는 파일 끝 부분에서 시작하는 세그먼트를 나타냅니다.데이터는 X 및 Y 읽기 버퍼로 읽힙니다.피벗 레코드를 선택하고 피벗 레코드 이외의 X 및 Y 버퍼 내의 레코드를 피벗 레코드와 비교하여 X 쓰기 버퍼에 오름차순으로 복사하고 Y 쓰기 버퍼에 내림차순으로 복사한다.X 버퍼 또는 Y 버퍼 중 하나가 채워지면 파일에 쓰여지고 다음 X 버퍼 또는 Y 버퍼가 파일에서 읽힙니다.이 프로세스는 모든 세그먼트를 읽고 1개의 쓰기 버퍼가 남을 때까지 계속됩니다.버퍼가 X 쓰기 버퍼일 경우 피벗 레코드가 추가되고 X 버퍼가 기록됩니다.그 버퍼가 Y 쓰기 버퍼일 경우 Y 버퍼에 피벗레코드가 부가되고 Y 버퍼가 기입됩니다.이것은 파일의 1개의 파티션스텝을 구성하며, 파일은 2개의 서브파일로 구성됩니다.각 서브파일의 시작 위치와 끝 위치는 재귀에 의해 독립형 스택 또는 메인 스택에 푸시/팝됩니다.스택 공간을 O(log2(n)로 제한하려면 작은 서브파일이 먼저 처리됩니다.스탠드아론 스택의 경우 큰 서브파일 파라미터를 스택에 푸시하고 작은 서브파일로 반복합니다.재귀의 경우 먼저 작은 서브파일에 반복한 후 큰 서브파일을 처리합니다.서브파일이 4 B레코드 이하가 되면 해당 서브파일은 QuickSort를 통해 제자리에 정렬되어 기입됩니다.이 서브파일은 소트되어 파일 내에 배치됩니다.모든 하위 파일이 정렬되고 제자리에 배치될 때까지 프로세스가 계속됩니다.파일의 평균 패스 수는 약 1 + ln(N+1)/(4B)이지만 최악의 경우 패턴은 N 패스입니다(최악의 경우 내부 ^[39]정렬의 경우 O(n^2)와 동일합니다).

3방향 기수 퀵소트

이 알고리즘은 기수 정렬과 퀵 정렬의 조합입니다.배열에서 요소(피벗)를 선택하고 문자열(멀티 키)의 첫 번째 문자(키)를 고려합니다.나머지 요소를 세 가지 집합으로 분할합니다. 즉, 대응하는 문자가 피벗 문자보다 작거나 같거나 큰 요소입니다.동일한 문자에서 "보다 작음" 및 "보다 큼" 파티션을 반복적으로 정렬합니다.다음 문자(키)를 기준으로 "동일" 파티션을 반복적으로 정렬합니다.바이트 또는 길이 W 비트의 단어를 사용하여 정렬할 경우, 가장 좋은 경우는 O(KN)이며, 최소 O(2N^K) 또는 표준적인 퀵소트로서 적어도 O(N²)는 하나의 키 N<2에^K 대해 지정되며, K는 퀵소트를 포함한 모든 표준적인 비교 정렬 알고리즘에서 숨겨진 상수이다.이것은 3방향 퀵소트의 일종으로, 중간 파티션은 피벗과 정확히 동일한 요소의 (삼각으로) 정렬된 서브어레이를 나타냅니다.

빠른 기수 정렬

또한 파워스에 의해 O(K) 병렬 PRAM 알고리즘으로 개발되었습니다.이는 다시 기수 정렬과 퀵소트의 조합이지만 퀵소트 좌/우 파티션 결정은 키의 연속 비트에서 이루어지기 때문에 N K비트 키의 경우 O(KN)입니다.모든 비교 정렬 알고리즘은 해시 테이블 또는 정수 정렬을 사용하여 O(N) 시간으로 정렬할 수 있는 것처럼 δ(로그 N)에 K를 포함하는 트랜스디코토머스 모델을 가정합니다.K log log N이지만 요소가 O(log N) 비트 내에서 고유할 경우 나머지 비트는 quicksort 또는 quick radix 정렬에 의해 조사되지 않습니다.그렇지 않으면 모든 비교 정렬 알고리즘은 O(K)의 비교적 쓸모없는 비트를 살펴보는 것과 동일한 오버헤드를 가지지만 빠른 기수 정렬은 표준 빠른 정렬과 기수 빠른 정렬의 최악의 경우² O(N) 동작을 피할 수 있으며 이러한 uniquepix(K) 조건 하에서 비교 알고리즘의 최상의 경우에도 더 빠를 것이다. § 로그 N.숨겨진 오버헤드의 비교, 기수 및 병렬 정렬에 대한 자세한 내용은 파워를 참조하십시오^[40].

블록퀵소트

비교 기반 정렬 알고리즘에서 비교 수를 최소화하려면 각 비교에서 얻은 정보의 양을 최대화해야 합니다. 즉, 비교 결과를 예측할 수 없습니다.이로 인해 브랜치 예측이 자주 빗나가 ^[41]퍼포먼스가 제한됩니다.BlockQuickSort는^[42] 예측 불가능한 분기를 데이터 종속성으로 변환하기 위해 QuickSort의 계산을 재정렬합니다.파티션을 분할할 때 입력은 중간 크기의 블록(데이터 캐시에 쉽게 들어갈 수 있음)으로 분할되고 2개의 어레이에는 스왑할 요소의 위치가 채워집니다(조건부 분기를 피하기 위해 어레이의 끝에 위치가 무조건 저장되며 스왑이 필요할 경우 끝의 인덱스가 증가합니다).두 번째 패스는 배열에 표시된 위치에서 요소를 교환합니다.두 루프 모두 조건부 브랜치(종단 테스트)는 1개뿐입니다.이거는 보통 실행됩니다.

부분 및 증분 빠른 정렬

입력의 나머지 부분으로부터 k개의 최소 또는 최대 요소를 분리하는 몇 가지 종류의 QuickSort가 존재합니다.

일반화

Richard Cole과 David C. Kandathil은 2004년에 파티션 정렬이라고 불리는 정렬 알고리즘의 1 파라미터 패밀리를 발견했습니다.${\displaystyle 이}$ 알고리즘은 평균적으로 (모든 입력 순서가 같으며) 최대 n개의 로그 ${\displaystyle \log n}$ +${\displaystyle }$O (${\displaystyle n}$ )$$\ $display style$n \ $log$ n + { $O （$n ${\displaystyle ）}$ （ n ） ${\displaystyle \mathrm{isons<img\; alt="n\backslash log\; n+\{O\}(n)"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/1da176c1c292899e6fce0fb57ef6411c6e52d702"\; style="vertical-align:\; -0.838ex;\; width:14.353ex;\; height:2.843ex;">}}$ （ ） （${\displaystyle }$（ display styledisplay stylog n \ lower ） 비교 ( information lower ） ${\displaystyle ）}$ ） lower))))))))))))))))))))))))))) ${\displaystyle \mathrm{bound}}$$디스플레이$$스타일$$Theta$} ($n$ \ $log$n )연산은$$ 최악의${\displaystyle \mathrm{경우}}$ ${\displaystyle {\mathrm{worst}}^{}}$ ( n ${\displaystyle {log\mathrm{}}^{}}$ 2${\displaystyle {}^{}n}$n$$)\$$$displaystyle$$Theta$}($n\log$^{$2}n)}$ 비교$$(및 연산도 포함)입니다.이러한 비교는 인플레이스이며 $추가{\displaystyle }$ O${\displaystyle (\log n}$n$)\style {O}(\log n)$ 공간만 필요합니다$$.최적화된 퀵소트(Sedgewick 및 Bentley-Mcilroy)^[43]에 비해 실용적 효율성과 성능의 편차가 작다는 것이 입증되었습니다.

「 」를 참조해 주세요.

• Introsort – 하이브리드 정렬 알고리즘

메모들

레퍼런스

• Sedgewick, R. (1978). "Implementing Quicksort programs". Comm. ACM. 21 (10): 847–857. doi:10.1145/359619.359631. S2CID 10020756.
• Dean, B. C. (2006). "A simple expected running time analysis for randomized 'divide and conquer' algorithms". Discrete Applied Mathematics. 154: 1–5. doi:10.1016/j.dam.2005.07.005.
• Hoare, C. A. R. (1961). "Algorithm 63: Partition". Comm. ACM. 4 (7): 321. doi:10.1145/366622.366642. S2CID 52800011.
• Hoare, C. A. R. (1961). "Algorithm 65: Find". Comm. ACM. 4 (7): 321–322. doi:10.1145/366622.366647.
• Hoare, C. A. R. (1962). "Quicksort". Comput. J. 5 (1): 10–16. doi:10.1093/comjnl/5.1.10. (Hoare and Jones: 컴퓨터 과학 에세이, 1989년)
• Musser, David R. (1997). "Introspective Sorting and Selection Algorithms". Software: Practice and Experience. 27 (8): 983–993. doi:10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#.
• 도널드 크누트.The Art of Computer Programming, 제3권: Sorting and Searching, 제3판.애디슨 웨슬리, 1997년ISBN 0-201-89685-0.섹션 5.2.2의 113~122 페이지: 교환에 의한 정렬.
• 토마스 H. 코먼, 찰스 E. 리저슨, 로널드 L. 리베스트, 클리포드 스타인.알고리즘 소개, 제2판MIT Press and McGraw-Hill, 2001.ISBN 0-262-03293-7.7장: QuickSort, 페이지 145-164.
• 파론 몰러.QuickSort 분석.CS 332: 알고리즘 설계스완지 대학교 컴퓨터 공학과입니다.
• Martínez, C.; Roura, S. (2001). "Optimal Sampling Strategies in Quicksort and Quickselect". SIAM J. Comput. 31 (3): 683–705. CiteSeerX 10.1.1.17.4954. doi:10.1137/S0097539700382108.
• Bentley, J. L.; McIlroy, M. D. (1993). "Engineering a sort function". Software: Practice and Experience. 23 (11): 1249–1265. CiteSeerX 10.1.1.14.8162. doi:10.1002/spe.4380231105. S2CID 8822797.

외부 링크

• "Animated Sorting Algorithms: Quick Sort". Archived from the original on 2 March 2015. Retrieved 25 November 2008. – 그래픽 데모
• "Animated Sorting Algorithms: Quick Sort (3-way partition)". Archived from the original on 6 March 2015. Retrieved 25 November 2008.
• 오픈 데이터 구조 –섹션 11.1.2 – QuickSort, Pat Morin
• QuickSort의 인터랙티브 일러스트와 코드 워크스루