정렬 알고리즘

오름차순으로 정렬하도록 구현한 코드

버블 정렬

버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.

1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

const bubbleSort = (array) => {
  for (let i = 0; i < array.length - 1; i++) {
    let swap;
    for (let j = i+1; j < array.length; j++) {
      if (array[i] > array[j]) {
        swap = array[i];
        array[i] = array[j];
        array[j] = swap;
      }
    }
  }  
  return array;
};

선택 정렬

선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.

1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회전에서는 두 번째 자료를 가지고 비교한다. 마찬가지로 3회전에서는 세 번째 자료를 정렬한다.

const selectionSort = (nums) => {
  const length = nums.length;
  let minIndex, temp;

  for (let i = 0; i < length - 1; i++) {
    minIndex = i;

    for (let j = i + 1; j < length; j++) {
      if (nums[j] < nums[minIndex]) {
        minIndex = j;
      }
    }

    temp = nums[minIndex];
    nums[minIndex] = nums[i];
    nums[i] = temp;
  }
  return nums;
};

퀵 정렬

하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.

const quickSort = (array) => {
  if (array.length < 2) return array;

  const pivot = array[0];
  const small = [];
  const big = [];

  for (let i = 1; i < array.length; i++) {
    if (array[i] <= pivot) {
      small.push(array[i]);
    } else {
      big.push(array[i]);
    }
  }

  return quickSort(small).concat(pivot, quickSort(big));
};

Reference
https://gmlwjd9405.github.io/tags#algorithm