[Exchange Sort] 홀짝 정렬 (Odd-Even Sort)

정렬 알고리즘 위키

복잡도

• 최악 시간복잡도

  • $O(n^2)$

• 최선 시간복잡도

  • $O(n)$

• 평균 시간복잡도

  • $O(1)$

구현 코드

export const arr = [
  14, 17, 12, 20, 1, 5, 9, 7, 3, 8, 6, 2, 4, 10, 11, 16, 15, 19, 18, 13,
];

import { arr } from "./number_array";

class oddEvenSort {
  public static main(arr: number[]): void {
    let sorted = false,
      count: number = 0;

    const swap = (arr: number[], i: number, j: number): void => {
      let temp: number = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    };

    while (!sorted) {
      sorted = true;
      for (let j = 1; j < arr.length - 1; j += 2) {
        if (arr[j] > arr[j + 1]) {
          swap(arr, j, j + 1);
          sorted = false;
        }
      }

      for (let j = 0; j < arr.length - 1; j += 2) {
        if (arr[j] > arr[j + 1]) {
          swap(arr, j, j + 1);
          sorted = false;
        }
      }

      count++;
      console.log(arr.toString(), `→ [${count}회]`);
    }
    // console.log(arr.toString());
  }
}

oddEvenSort.main(arr);