[Exchange Sort] 꼭두각시 정렬 (Stooge Sort)

정렬 알고리즘 위키

복잡도

• 최악 시간복잡도

  • $O(n$^{$log \ 3 / log \ 1.5$}$)$

• 공간복잡도

  • $O(n)$

구현 코드

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

let count = 0;

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

const stoogeSort = (arr: number[], i?: number, j?: number): void => {
  if (!i) {
    i = 0;
  }

  if (!j) {
    j = arr.length - 1;
  }

  if (arr[j] < arr[i]) {
    swap(arr, i, j);
  }

  if (j - i > 1) {
    var t = Math.floor((j - i + 1) / 3);
    stoogeSort(arr, i, j - t);
    stoogeSort(arr, i + t, j);
    stoogeSort(arr, i, j - t);
  }

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

stoogeSort(arr);