[Exchange Sort] 빗질 정렬 (Comb Sort)

정렬 알고리즘 위키

복잡도

• 최악 시간복잡도

  • $O(n^2)$

• 최선 시간복잡도

  • $\Theta(n \ log(n))$

• 평균 시간복잡도

  • $\Omega(n^2 / 2^p)$ : 여기서 $p$는 증가 수

• 공간복잡도

  • $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 combSort {
  public static main(arr: number[]): void {
    let i: number,
      gap: number,
      size: number,
      count: number = 0,
      temp: number = 0,
      sorted: boolean = true;

    gap = size = arr.length;

    while (gap !== 1 || sorted) {
      gap /= 1.3;

      if (gap < 1) gap = 1;

      sorted = false;

      for (i = 0; i < size - gap; i++) {
        if (arr[i] > arr[i + gap]) {
          temp = arr[i];
          arr[i] = arr[i + gap];
          arr[i + gap] = temp;
          sorted = true;
        }
      }
      count++;
      console.log(arr.toString(), `→ [${count}회]`);
    }
  }
}

combSort.main(arr);