기본 정렬

정렬 알고리즘 시간 복잡도 비교

Name	Best	Avg	Worst	Run-time(정수 60,000개) 단위: sec
삽입 정렬	n	n(2)	n(2)	7.43
선택 정렬	n(2)	n(2)	n(2)	10.84
버블 정렬	n(2)	n(2)	n(2)	22.89
셀 정렬	n	n(1.5)	n(2)	0.056
퀵 정렬	nlog2n	nlog2n	n(2)	0.014
힙 정렬	nlog2n	nlog2n	nlog2n	0.034
병합 정렬	nlog2n	nlog2n	nlog2n	0.026

---

1. 삽입 정렬 (Insertion Sort)

출처: https://im-developer.tistory.com/133 [Code Playground]

• 왼쪽에서 오른쪽으로 가면서 각 요소들을 왼쪽 요소들과 비교하여 알맞는 자리에 삽입하는 정렬 방법

Big O

• Worst Case: O(n^2): 정렬이 하나도 안되어있는 경우
• Best Case: O(n): 이미 정렬이 되어있는 경우

장점

• 메모리 절약
• 구현하기가 매우 쉽고 정렬된 데이터를 순회하는 경우 O(n)번만 순회하면 되므로 테스트로 사용

단점

• 자료의 개수가 많아질수록 성능이 매우 떨어짐

구현

const insertionSort = (array) => {
  var i = 1, j, temp;
  for (i; i < array.length; i++) {
    temp = array[i]; // 새로운 숫자를 선택
    for (j = i - 1; j >= 0 && temp < array[j]; j--) { 
      // 선택한 숫자를 이미 정렬된 숫자들과 비교 -> 넣을 위치 체크, 
      // 선택한 숫자가 정렬된 숫자보다 작으면
      array[j + 1] = array[j]; // 한 칸씩 뒤로 밀어냄
    }
    array[j + 1] = temp; // 마지막 빈 칸에 선택한 숫자넣음
  }
  return array;
};
insertionSort([5, 6, 1, 2, 4, 3]); // [1, 2, 3, 4, 5, 6]

[저작자] Wikipedia 이미지 출처

---

2. 선택 정렬 (Selection Sort)

• 데이터 중 맨 앞 요소와 나머지 요소를 비교하여 맨 앞 요소가 더 크면 자리 변경
  • 마지막 요소를 제외한 모든 요소가 반복

[저작자] Xybernetics 이미지 출처

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

const array = [1, 13, 5, 24, 94, 26, 223, 36, 45, 29];
console.log(selectSort(array)); // [1, 5, 13, 24, 26, 29, 36, 45, 94, 223]

---

3. 버블 정렬(bubble Sort)

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
  • 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환
• 일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블정렬은 단순성에도 불구하고 거의 안씀

[저작자] Algorithm 앱의 Bubble Sort GIF 이미지 출처

const bubbleSort = (data) => {
  for (let i = 0; i < data.length - 1; i++) {
    let swap = false; // 변화 여부 체크
    for (let j = 0; j < data.length - i - 1; j++) {
      if (data[j] > data[j + 1]) {
        [data[j], data[j + 1]] = [data[j + 1], data[j]]; // swap
        swap = true;
      }
    }
    if (!swap) break;
  }
  return data;
};

const data = [10, 73, 45, 34, 2, 32, 62, 1, 25, 6, 91];

console.log(bubbleSort(data)); // [1, 2, 6, 10, 25, 32, 34, 45, 62, 73, 91]