홀짝 정렬 문서 원본 보기

{{위키데이터 속성 추적}}
{{Infobox Algorithm
|class=[[정렬 알고리즘]]
|image=[[파일:Odd even sort animation.gif|Example of odd–even transposition sort sorting a list of random numbers]]
|caption=무작위 수의 목록을 정렬하는 홀짝 정렬
|data=[[배열]]
|time=<math>O(n^2)</math>
|best-time=<math>O(n)</math>
|space= <math>O(1)</math>
|optimal=아니오
}}
'''홀짝 정렬'''(odd–even sort 또는 odd–even transposition sort) 또는 '''브릭 정렬'''(brick sort),<ref>{{웹 인용|last=Phillips|first=Malcolm|title=Array Sorting|url=http://homepages.ihug.co.nz/~aurora76/Malc/Sorting_Array.htm#Exchanging_Sort_Techniques|website=Homepages.ihug.co.nz|access-date=3 August 2011|url-status=dead|archive-url=https://web.archive.org/web/20111028201105/http://homepages.ihug.co.nz/~aurora76/Malc/Sorting_Array.htm#Exchanging_Sort_Techniques|archive-date=28 October 2011}}</ref> '''패리티 정렬'''(parity sort)은 상대적으로 단순한 [[정렬 알고리즘]]이다. 로컬 상호 연결에 병렬 프로세서를 사용하기 위해 처음 개발되었다. [[거품 정렬]]과 관련된 [[비교 정렬]]이므로 거품 정렬의 수많은 특징을 공유한다. 목록 안의 인접한 요소들의 색인화된 홀/짝 쌍을 모두 비교함으로써 기능하며 쌍의 순서가 잘못된 경우(첫 번째가 두 번째보다 더 큰 경우) 요소는 위치를 서로 바꾼다. 다음 단계는 인접 요소들의 짝/홀 색인 쌍에 대해 이를 반복한다. 그 다음에 목록이 정렬될 때까지 홀/짝과 짝/홀 단계 사이를 교대로 수행한다.

== 알고리즘 ==
[[거품 정렬]]처럼 이 단순 프로세서 알고리즘은 단순하지만 매우 효율적이지는 않다. 제로 기반 인덱스가 있다고 가정할 때 다음과 같다:
<syntaxhighlight lang="javascript">
function oddEvenSort(list) {
  function swap(list, i, j) {
    var temp = list[i];
    list[i] = list[j];
    list[j] = temp;
  }

  var sorted = false;
  while (!sorted) {
    sorted = true;
    for (var i = 1; i < list.length - 1; i += 2) {
      if (list[i] > list[i + 1]) {
        swap(list, i, i + 1);
        sorted = false;
      }
    }
    for (var i = 0; i < list.length - 1; i += 2) {
      if (list[i] > list[i + 1]) {
        swap(list, i, i + 1);
        sorted = false;
      }
    }
  }
}
</syntaxhighlight>

== 각주 ==
{{각주}}

{{정렬 알고리즘}}

[[분류:정렬 알고리즘]]
[[분류:비교 정렬]]
[[분류:안정 정렬]]