정렬

1. Selection Sort

  선택 정렬은 첫 번째 인덱스에는 두 번째 자료부터 마지막 자료까지 중에 가장 최솟값을 놓고
  두 번째 자료에는 세 번째 자료부터 마지막 자료까지 중에 최솟값을 놓는 과정을 반복하여 정렬하는 알고리즘

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let min = Math.min(...arr.slice(i + 1));
    let minIdx = arr.indexOf(min);
    if (minIdx === i) continue;
    else [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
  }
  return arr;
}

 

2. Bubble Sort

  버블 정렬은 자기 자신 바로 옆에 자료와 크기 비교를 통해 한 쪽으로 최댓값 또는 최솟값을 결정하고 이것을 매번 반복하여
  정렬하는 알고리즘이다.

function bubbleSort(numbers) {
  for (let i = 0; i < numbers.length - 1; i++) {
    for (let j = i; j < numbers.length - 1; j++) {
      if (numbers[j] > numbers[j + 1]) {
        [numbers[j], numbers[j + 1]] = [numbers[j + 1], numbers[j]];
      }
    }
  }
  return numbers;
}

 

3. Insert Sort

  각 자료를 선형 탐색하면서 해당 자료와 해당 자료 이전까지 자료들의 크기를 비교하여 정렬하는 알고리즘이다.
  즉 두 번째 자료는 첫 번째 자료와 크기를 비교하여 정렬하고 세 번째 자료는 두 번째 자료와 크기를 비교하고 만약 세 번째 자료의 크기가 작다면 두 번째 자료와 자리를 바꾸고 또 두 번째 자료와 첫 번째 자료의 크기를 비교한다. 이러한 방법으로 마지막 자료까지 반복하는 것이 삽입 정렬이다.

function insertSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j >= 0; j--) {
      if (arr[j] < arr[j - 1]) [arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
      else break;
    }
  }
  return arr;
}

 

4. Quick Sort

  현존하는 가장 빠른 정렬 알고리즘 중에 하나이다. 퀵 정렬에서는 요소 하나를 기준 원소인 pivot으로 설정한다.
  그리고 기준 원소의 왼쪽에는 기준 원소보다 작은 값의 배열을 놓고 오른쪽에는 기준 원소보다 큰 값을 놓는다.
  그리고 왼쪽 배열과 오른쪽 배열 각각에 대해서 또 위의 과정을 반복하여 정렬하는 것이 퀵 정렬이다.

const quickSort = function (arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[0];
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] <= pivot) left.push(arr[i]);
    else right.push(arr[i]);
  }

  const lSorted = quickSort(left);
  const rSorted = quickSort(right);
  return [...lSorted, pivot, ...rSorted];
};