[알고리즘/node.js] 비교 정렬 (버블/선택/삽입/병합/퀵)

뭘 찾아보면 굳이 한참을 거슬러 올라가서 조상의 조상까지 찾아보ㅏ야하는 나쁜 습관 ..

정렬이란 무엇인가 수준까지 올라가서 찾아봤다 ^^,, ㅎ

 

정렬 알고리즘 Sorting Algorithm

정렬 이라는 개념 자체는 참 직관적이고 단순한 것에 반해 동작 원리가 제법 복잡해서

컴퓨터 개발 초창기부터 제법 뜨거운 감자였다고 한다.

1950년대부터 정렬 알고리즘 관련 연구가 많았다고 ,, 🤔

 

정렬 알고리즘은 크게 두가지로 구분 된다.

1. 비교 정렬 Comparison Sorts

2. 비비교 정렬 Non-comparison Sorts

 

 

비교 정렬

말 그대로 정렬 내 두개 요소의 크기를 비교해가면서 크기에 따라 위치를 조정하는 것.

종류가 10개도 넘게 있는데 개중 제일 자주 언급되는 것 5개만 정리해보았다.

 

 

버블 정렬 Bubble Sort

동작 원리 및 과정

 1. arr[n] 이랑 arr[n+1] 비교

 2. arr[n] > arr[n+1] 일 경우 교체

 3. 정렬 길이 만큼 위 과정 반복

코드 예시

버블 정렬 코드는 직접 작성해보았는데, 다른 정렬 대비 좀 쉽게 느껴진다.

// 버블 정렬
const arr = [7, 2, 16, 5, 1, 4];
for (let i = 0; i < arr.length; i++) {
  for (let j = 0; j < arr.length-1; j++) {
    if (arr[j] > arr[j+1]) {
      const temp = arr[j];
      arr[j] = arr[j+1];
      arr[j+1] = temp;
    }
  }
}

 

 

선택 정렬 Selection Sort

동작 원리 및 과정

 1. 배열을 훑으면서 가장 작은 값을 찾는다

 2. 가장 작은 값을 배열 제일 앞으로 이동 시킨다.

 3. 정렬되지 않은 나머지 배열에서 1, 2 과정을 반복한다.

코드 예시

const arr = [7, 2, 16, 5, 1, 4];

for (let i = 0; i < arr.length; i++) {
    let lowestValue = arr[i];
    let indexOfLowestValue = i;
    for (let j = i; j < arr.length; j++) {
      if (arr[j] < lowestValue) {
        lowestValue = arr[j];
        indexOfLowestValue = j;
      }
    }
    let temp = arr[i];
    arr[i] = arr[indexOfLowestValue];
    arr[indexOfLowestValue] = temp;
  }

 

삽입 정렬 Insertion Sort

동작 원리 및 과정

 1. 배열의 정렬되지 않은 부분에서 첫번째 값을

 2. 정렬된 부분의 값들과 순차적으로 비교해서 올바른 위치에 배치한다.

 3. 배열 길이 만큼 비교 후 배치 동작을 실행한다.

코드 예시

const arr = [7, 2, 16, 5, 1, 4];

for (let i = 1; i < arr.length; i++) {
    let currentValue = arr[i]
    let j
    for (j = i - 1; j >= 0 && arr[j] > currentValue; j--) {
      arr[j + 1] = arr[j]
    }
    arr[j + 1] = currentValue
  }

 

 

 

병합 정렬 Merge Sort

동작 원리 및 과정

 1. 배열을 두개의 하위 배열로 나눈다 (기존 배열의 약 절반 사이즈가 되도록)

 2. 하위 배열의 크기가 1 이상이면 다시 두개로 나누고, 모든 하위 배열의 크기가 1이 될 때까지 반복한다.

 3. 이웃한 두개의 하위 배열의 크기를 비교해서, 크기가 작은 수가 먼저 오도록 병합 한다.

https://www.w3schools.com/dsa/dsa_algo_mergesort.php

 

 

 

퀵 정렬 Quick Sort

동작 원리 및 과정

 1. 배열에서 정렬 기준 요소를(pivot element) 정한다.

 2. 기준 요소를 제외한 나머지 값들이 기준 요소 보다 작으면 왼쪽, 크면 오른쪽에 위치하도록 분할 및 정렬한다.

 3. 기준 요소를 해당 요소보다 작은 수 우측, 큰 수들 좌측에 위치 하도록 배치한다.

 4. 분할 된 두 배열에 대해 1~3 과정을 반복한다.

 

 

 

 

결국 어떤 알고리즘을 사용하는 것이 좋을까  🤔

비교 정렬 중에 가장 빠른 것은 퀵 정렬이라고 한다.

버블정렬 같은 건 어떨 때 쓰면 좋을지 찾아봤는데 "정말 특수한 상황"에서 가장 빠르고 또 필요로 할 수 있다고 ,,

근데 그 특수 상황 예시가 저장된 정보를 불러오는데 메모리 키가 너무 커서 혹은 메모리가 너무 작아서

딱! 2개에만 접근 할 수 있는 그런 상황이라고 구체적으로 적혀있었다 ^^ ㅎ

컴퓨터 처음 나온 시절에는 충분히 연구할 가치가 있었을거라고 ,,,

즉, 지금은 딱히 쓸 필요는 없고 퀵 정렬이 제일 효율이 좋은 것이 통설로 보인다.