정렬 알고리즘 - (2)

선택 정렬 - O(n2)

const selectionSort = (array) => {
  const result = [];

  let copiedArray = array.slice();
  let minValue = Infinity;
  let minIndex = -1;

  while (copiedArray.length > 0) {
    copiedArray.forEach((val, index) => {
      if (minValue > val) {
        minValue = val;
        minIndex = index;
      }
    });

    result.push(minValue);

    copiedArray = copiedArray.filter((val, index) => index !== minIndex);

    minValue = Infinity;
    minIndex = -1;
  }

  return result;
};

퀵 정렬 - 평균 : O(nlogn), 최악 : O(n2)

const quickSort = (array) => {
  if (array.length < 2) {
    return array;
  } else {
    const mid = Math.floor(array.length / 2);
    const pivot = array[mid];

    let leftArray = [];
    let rightArray = [];

    array.forEach((val, index) => {
      if (index !== mid) {
        if (val < pivot) {
          leftArray.push(val);
        } else {
          rightArray.push(val);
        }
      }
    });

    leftArray = quickSort(leftArray);
    rightArray = quickSort(rightArray);

    const result = leftArray.concat([pivot]).concat(rightArray);

    return result;
  }
};

기수 정렬 - O(dn), d : 기수의 크기

const radixSort = (array) => {
  const createRange = (start, end) => {
    return Array(end - start)
      .fill("")
      .map((val, index) => start + index);
  };

  const reverseNumber = (num) => {
    const stringArray = Array.from(num);
    stringArray.reverse();
    return stringArray.join("");
  };

  let copiedArray = array.map((val) => {
    return val.toString();
  });

  const numberRange = createRange(0, 10).map((num) => num.toString());

  const numberQueues = {
    0: [],
    1: [],
    2: [],
    3: [],
    4: [],
    5: [],
    6: [],
    7: [],
    8: [],
    9: [],
  };

  const result = [];

  let radix = 0;
  let length = radix + 1;

  while (copiedArray.length > 0) {
    copiedArray.forEach((num) => {
      const key = reverseNumber(num)[radix];
      numberQueues[key].push(num);
    });

    const remainArray = [];

    for (const key of numberRange) {
      while (numberQueues[key].length > 0) {
        const num = numberQueues[key].shift();
        if (num.length === length) {
          result.push(parseInt(num, 10));
        } else {
          remainArray.push(num);
        }
      }
    }

    copiedArray = remainArray;
    radix += 1;
    length = radix + 1;
  }

  return result;
};

입력 배열 : [66, 23, 54, 523, 132, 35, 2, 8, 6]
기수 위치 : 1
Queue의 상황

0 : []
1 : []
2 : [132, 2]
3 : [23, 523]
4 : [54]
5 : [35]
6 : [66, 6]
7 : []
8 : [8]
9 : []

정렬 결과 : [2, 6, 8]
남은 값 : [132, 23, 523, 54, 35, 66]
기수 위치 : 2
Queue의 상황

0 : []
1 : []
2 : [23, 523]
3 : [132, 35]
4 : []
5 : [54]
6 : [66]
7 : []
8 : []
9 : []

정렬 결과 : [2, 6, 8, 23, 35, 54, 66]
남은 값 : [132, 523]
기수 위치 : 3
Queue의 상황

0 : []
1 : [132]
2 : []
3 : []
4 : []
5 : [523]
6 : []
7 : []
8 : []
9 : []

정렬 결과 : [2, 6, 8, 23, 35, 54, 66, 132, 523]
남은 값 : []