정렬?

• 정렬이란 크기 순으로 오름차순 또는 내림차순으로 주어진 데이터를 나열하는 것을 의미합니다.
• 정렬에는 다양한 방법이 있으며, 데이터의 개수, 키의 자료형, 키의 크기, 정렬할 데이터의 위치와 같은 상황에 따라 최적인 정렬 방법이 있습니다.

오늘은 다양한 정렬의 방법 중에서 상대적으로 다른 방법들에 비해 비효율적이지만 단순하고 쉬운 방법인 삽입 정렬, 버블 정렬, 선택 정렬에 대해 알아보겠습니다.

삽입 정렬

• 삽입 정렬이란 정렬되어 있는 부분에 새로운 데이터를 올바른 위치에 삽입하는 정렬 방식입니다.
• 삽입 과정에서 데이터를 칸칸이 뒤로 이동해야 하기 때문에 많은 이동이 발생하고, 레코드가 클 경우 불리합니다.
• 복잡도의 경우 이미 정렬되어 있는 경우 O(n)으로 최선이고, 역순으로 정렬되어 있는 경우는 최악의 경우로 O(n^2)입니다.
• 대부분 정렬되어 있으면 매우 효율적입니다

Javascript에서의 삽입 정렬

function insertion_sort(arr) {
  let answer = arr;
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j;
    for (j = i - 1; j >= 0 && arr[j] > key; j--) {
      arr[j + 1] = arr[j];
    }
    arr[j + 1] = key;
  }
  return answer;
}

• i-1에 해당하는 값부터 정렬하기 시작합니다.
• 정렬 대상의 값이 arr[j]보다 작으면 arr[j+1]에 arr[j]의 값을 추가해주어 한칸씩 오른쪽으로 이동시킵니다.
• 정렬 대상의 값이 arr[j]보다 작지 않은 경우가 발생하면 반복을 중단하고 기존에 저장되어있던 정렬 대상(key)을 arr[j+1]에 추가해줍니다.

버블 정렬

• 버블 정렬은 인접한 2개의 레코드를 비교하여 순서대로 되어있지 않으면 서로 교환하여 큰수를 뒤로 보내는 정렬방식입니다.
• 이 과정을 리스트의 왼쪽 끝에서 오른쪽 끝까지 반복합니다.

Javascript에서의 버블 정렬

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

• 비교 횟수는 최상 평균 최악 모든 경우 동일하게 O(n^2)입니다.
• 직접 구현하기 간단하다는 장점이 있지만 데이터의 이동이 많다는 단점이 있습니다.

선택 정렬

• 선택 정렬은 이동이 많은 버블 정렬의 단점을 개선한 정렬방식입니다.
• 정렬된 왼쪽 부분과 정렬되지 않은 오른쪽 부분을 두고
• 오른쪽 부분에서 가장 작은 값을 왼쪽 부분으로 이동시키는 방식입니다.
• 이 과정을 오른쪽 부분의 데이터가 없을 때까지 반복합니다.

Javascript에서의 선택 정렬

function selection_sort(arr) {
  let answer = arr;
  for (let i = 0; i < arr.length - 1; i++) {
    let l = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[l]) l = j;
    }
    [arr[i], arr[l]] = [arr[l], arr[i]];
  }
  return answer;
}

• 버블 정렬과 같이 최상 평균 최악 모든 경우 동일한 O(n^2)의 복잡도를 갖고 있습니다.
• 효율성이 떨어지지만 입력에 민감하지 않습니다.