홀짝 정렬

위키백과, 우리 모두의 백과사전.

홀짝 정렬
Example of odd–even transposition sort sorting a list of random numbers
무작위 수의 목록을 정렬하는 홀짝 정렬
분류정렬 알고리즘
자료 구조배열
최악 시간복잡도
최선 시간복잡도
공간복잡도

홀짝 정렬(odd–even sort 또는 odd–even transposition sort) 또는 브릭 정렬(brick sort),[1] 패리티 정렬(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;
      }
    }
  }
}

각주[편집]

  1. Phillips, Malcolm. “Array Sorting”. 《Homepages.ihug.co.nz》. 2011년 10월 28일에 원본 문서에서 보존된 문서. 2011년 8월 3일에 확인함.