[Exchange Sort] 난쟁이 정렬 (Gnome Sort)

정렬 알고리즘 위키

복잡도

• 최악 시간복잡도

  • $O(n^2)$

• 최선 시간복잡도

  • $O(n)$

• 평균 시간복잡도

  • $O(n^2)$

• 공간복잡도

  • $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 gnomeSort {
  public static main(arr: number[]): void {
    let pos: number = 0,
      count: number = 0;

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

    for (pos = 0; pos < arr.length - 1; ) {
      if (pos < 0 || arr[pos] <= arr[pos + 1]) {
        pos++;
        continue;
      }

      swap(arr, pos, pos + 1);
      pos--;

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

gnomeSort.main(arr);