정렬

다양한 정렬 알고리즘 중에서 버블 정렬, 선택 정렬, 삽입 정렬 순으로 살펴보려고 한다.

버블 정렬

버블 정렬은 인접한 두 개의 원소를 비교해서 자리를 바꾸는 알고리즘이다.

구현

버블 정렬을 JavaScript로 구현해보자.

function BubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

const arr = [4, 2, 3, 1];
BubbleSort(arr);
console.log(arr); // output: [1, 2, 3, 4]

정리

시간 복잡도	장점	단점
O(n²)	단순하고 구현이 쉬움	성능이 좋지 않음

선택 정렬

선택 정렬은 정렬되지 않은 영역에서 가장 작은 값을 찾아, 맨 앞에 있는 원소와 교환하는 방식으로 정렬을 진행한다.

먼저 배열의 첫 번째 원소부터 마지막 원소까지 탐색하여, 가장 작은 값을 찾아 첫 번째 위치로 이동시킨다.
그 다음에는 두 번째 원소부터 마지막까지 탐색해 가장 작은 값을 찾아 두 번째 위치로 이동시킨다.

이런 식으로 정렬되지 않은 영역을 점점 줄여가며, 같은 작업을 반복하면 정렬이 완료된다.

구현

선택 정렬을 JavaScript로 구현해보자.

function SelectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minValueIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minValueIndex]) {
        minValueIndex = j;
      }
    }
    let temp = arr[i];
    arr[i] = arr[minValueIndex];
    arr[minValueIndex] = temp;
  }
}

const arr = [4, 2, 1, 3];
SelectionSort(arr);
console.log(arr);

정리

시간 복잡도	장점	단점
O(n²)	단순하고 구현이 쉬움	성능이 좋지 않음

삽입 정렬

삽입 정렬은 정렬되지 않은 영역에서 데이터를 하나씩 꺼내,
정렬된 영역 내에서 적절한 위치에 삽입하며 정렬을 완성해가는 알고리즘이다.

처음에는 배열의 첫 번째 원소만 정렬된 영역으로 보고, 두 번째 원소부터는 정렬되지 않은 영역이라고 생각한다.

정렬되지 않은 영역에서 값을 하나씩 꺼내어, 정렬된 영역에서 자신보다 큰 값들을 뒤로 밀고, 비어 있는 위치에 삽입하는 과정을 반복한다.

이 과정을 통해 배열은 앞쪽부터 차례대로 정렬되며, 결국 전체 배열이 정렬된다.

구현

삽입 정렬을 JavaScript로 구현해보자.

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

let arr = [4, 1, 5, 3, 6, 2];
InsertionSort(arr);
console.log(arr);

정리

시간 복잡도	장점	단점
O(n²)	단순하고 구현이 쉬움	성능이 좋지 않음