홀짝 정렬

홀짝 정렬

무작위 수의 목록을 정렬하는 홀짝 정렬
분류	정렬 알고리즘
자료 구조	배열
최악 시간복잡도	$O(n^{2})$
최선 시간복잡도	$O(n)$
공간복잡도	$O(1)$

홀짝 정렬(odd–even sort 또는 odd–even transposition sort) 또는 브릭 정렬(brick sort), 패리티 정렬(parity sort)은 상대적으로 단순한 정렬 알고리즘이다. 로컬 상호 연결에 병렬 프로세서를 사용하기 위해 처음 개발되었다. 거품 정렬과 관련된 비교 정렬이므로 거품 정렬의 수많은 특징을 공유한다. 목록 안의 인접한 요소들의 색인화된 홀/짝 쌍을 모두 비교함으로써 기능하며 쌍의 순서가 잘못된 경우(첫 번째가 두 번째보다 더 큰 경우) 요소는 위치를 서로 바꾼다. 다음 단계는 인접 요소들의 짝/홀 색인 쌍에 대해 이를 반복한다. 그 다음에 목록이 정렬될 때까지 홀/짝과 짝/홀 단계 사이를 교대로 수행한다.

알고리즘

거품 정렬처럼 이 단순 프로세서 알고리즘은 단순하지만 매우 효율적이지는 않다. 제로 기반 인덱스가 있다고 가정할 때 다음과 같다:

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