[UNK] 정렬 - 위키백과, 우리 모두의 백과사전 [UNK] 정렬 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 [UNK] 정렬 난수열에 대해 [UNK] 정렬을 실행한 그림. 수평선은 피벗 값을 가리킨다. 분류 정렬 알고리즘자료 구조 배열최악 시간복잡도 O ( n 2 ) { [UNK] displaystyle O ( n ^ { 2 } ) } 최선 시간복잡도 O ( n log n ) { [UNK] displaystyle O ( n [UNK] log n ) } 평균 시간복잡도 O ( n log n ) { [UNK] displaystyle O ( n [UNK] log n ) } [UNK] 정렬 ( Quicksort ) 은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. [UNK] 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는
ort ) 은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. [UNK] 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O ( n2 ) 번의 비교를 수행하고, 평균적으로 O ( n log n ) 번의 비교를 수행한다. [UNK] 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고 ( 그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다. ), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 때문에 일반적인 경우 [UNK] 정렬은 다른 O ( n log n ) 알고리즘에 비해 훨씬 빠르게 동작한다. 그리고 [UNK] 정렬은 정렬을 위해 O ( log n ) 만큼의
lse if ( a > pivot ) right = right : a else equal = equal : a } quickSort ( left ) equal quickSort ( right ) } 자바스크립트 [ 편집 ] 1 / * * 2 * [UNK] 정렬 3 * 시간 복잡도 : 최악 - O ( n2 ), 최선 - O ( nlogn ), 평균 - O ( nlogn ) 4 * 공간 복잡도 : O ( 1 ) 5 * { Array } arr 6 * { int } left 7 * { int } right 8 * 9 var arr = [ 4, 5, 1, 2, 11, 8, 3, 1, 2, 5 ] ; 10 quicksort ( arr, 0, arr. length - 1 ) ; 11 * / 12 var quicksort = function (
을 설계하는 것이 가능하다. 때문에 일반적인 경우 [UNK] 정렬은 다른 O ( n log n ) 알고리즘에 비해 훨씬 빠르게 동작한다. 그리고 [UNK] 정렬은 정렬을 위해 O ( log n ) 만큼의 memory를 필요로한다. 또한 [UNK] 정렬은 불안정 정렬에 속한다. 목차 1 알고리즘 2 예제 3 정확성 증명 4 의사 코드와 세부 설명 4. 1 개선된 피벗 선택 5 복잡도 6 소스 코드 6. 1 C 6. 2 java 6. 3 비주얼 베이직 6. 4 OCaml 6. 5 하스켈 6. 6 파이썬 6. 7 파이썬 ( Cache 없이 ) 6. 8 스칼라 6. 9 자바스크립트 알고리즘 [ 편집 ] [UNK] 정렬은 분할 정복 ( divide and conquer ) 방법을 통해 리스트를 정렬한다. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고
n add x to less if x [UNK] pivot then add x to greater add pivot to pivotList return concatenate ( quicksort ( less ) ( less ), pivotList, quicksort ( greater ) ) 그러나 위 코드는 두 개의 작은 리스트를 저장하기 위해 [UNK] ( n ) 크기의 저장공간이 따로 필요하다는 단점이 있다. 실제 구현에서 임시 메모리는 캐시 성능과 속도에 심각한 저하를 가져올 수 있다. 아래와 같이 추가 메모리 없이 배열 내부에서 분할 작업을 구현하면 좀 더 복잡하지만 추가 메모리를 사용하지 않고 구현할 수 있다. 작은 크기의 예제 리스트에 대해 내부 분할을 적용한 그림 : 두꺼운 선으로 둘러싸인 원소는 피벗 원소이다. 파란색은 피벗보다 작거나 같고 빨간색은 피벗보다 크다.
할 수 있다. 작은 크기의 예제 리스트에 대해 내부 분할을 적용한 그림 : 두꺼운 선으로 둘러싸인 원소는 피벗 원소이다. 파란색은 피벗보다 작거나 같고 빨간색은 피벗보다 크다. function partition ( a, left, right, pivotIndex ) pivotValue : = a [ pivotIndex ] swap ( a [ pivotIndex ], a [ right ] ) / / 피벗을 끝으로 옮겨 놓는다. storeIndex : = left for i from left to right - 1 if a [ i ] < = pivotValue then swap ( a [ storeIndex ], a [ i ] ) storeIndex : = storeIndex 1 swap ( a [ right ], a [ store
작거나 같다면 계속 반복해서 수행한다. 위 와 같은 과정은 pivot을 기준으로 왼쪽으로 정렬된 list 에서는 최초 Left 값이 감소된 j 보다 작다면 계속 재귀하면되고, pivot을 기준으로 오른쪽으로 정렬된 list 에서는 최초 Right 값이 증가된 i 값보다 크다면 계속 재귀하면된다. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다. 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다. 예제 [ 편집 ] [UNK] 간단한 설명 [UNK] 임의의 pivot 값을 기준으로 pivot 의 좌측에는 pivot 보다 작은값을 두고 우측에는 pivot 보다 큰 값을 두고자 한다. 이 행위는 pivot을 기준으로 좌 우로 이분화 된 리스트를 재귀적으로 반복했을 때 결국 정렬이 완성 된다는 방법 론이다. 보다 쉽게 설명하면 pivot보다 큰 값을 pivot index 보다 왼쪽에서 찾고 ( 큰 값 이 나타날 때까지 i index 를 증가시키도록 한다. ) pivot 보다 작은 값을 pivot index 보다 오른쪽
음을 보장한다. 분할한 부분 배열이 정렬되므로 전체 배열이 정렬된다는 것도 수학적 귀납법으로 쉽게 보일 수 있다. 의사 코드와 세부 설명 [ 편집 ] [UNK] 소트 예제 : 두꺼운 선으로 둘러싸인 원소는 피벗 원소로서, 파티션의 마지막 원소로 한 경우이다. function quicksort ( q ) var list less, pivotList, greater if length ( q ) [UNK] 1 then return q select a pivot value pivot from q for each x in q except the pivot element if x < pivot then add x to less if x [UNK] pivot then add x to greater add pivot to pivotList return concatenate ( quicksort ( less )
ion is - less rest in quicksort left @ [ pivot ] @ quicksort right 하스켈 [ 편집 ] quicksort [ ] = [ ] quicksort ( p : tl ) = quicksort [ x | x < - tl, x < = p ] [ p ] quicksort [ x | x < - tl, x > p ] OCaml 과 비교를 쉽게하기 위한 version quicksort [ ] = [ ] quicksort ( pivot : rest ) = let left = [ x | x < - rest, x < = pivot ] right = [ x | x < - rest, x > pivot ] in quicksort left [ pivot ] quicksort right 파이썬 [ 편집 ] 1 def quicksort ( x )
퀵 정렬(Quicksort)은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다. 퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 또한 매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어든다. 때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다. 이러한 이유로 퀵소트(빠른정렬)라는 이름의 기원이 되었다. 그리고 퀵 정렬은 정렬을 위해 평균적으로 O(log n)만큼의 memory를 필요로한다. 이는 재귀적 호출로 발생하는 것이며, 최악의 경우 O(n)의 공간복잡도를 보인다. 원소들 중에 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있어 불안정 정렬에 속한다. 이러한 경우의 C코드 예: 51, 52, 3, 2, 1를 정렬하면 1, 2, 3, 52, 51 이 된다.