[JS Algorithm] 자바스크립트 Sorting - 기본편 (Bubble, Selection, Insertion)

Young-mason·2021년 2월 17일

algorithm

Algorithm

목록 보기

2/4

💡 자바스크립트 언어로 자료구조 & 알고리즘에 대해 배운 내용을 기록합니다

📖 Intro

정렬(Sorting) 은 데이터들을 특정한 순서에 따라 재배치하는 프로세스를 의미합니다

ex)

숫자를 오름차순으로 정렬
이름을 알파벳순으로 정렬
영화들을 개봉년도에 따라 정렬
영화들을 매출에 따라 정렬

정렬은 매우 흔한 작업이기 때문에 구현과정을 파악하는 것은 좋은 공부가 될 것 같습니다.

정렬에는 다양한 방식들이 있고, 각각 장점과 단점이 있습니다. 정렬 알고리즘들 중에서 가장 기본적인 버블, 선택, 삽입 정렬이 어떤 방식으로 실행되는지, 자바스크립트 코드로는 어떻게 구현되는지 알아보겠습니다

📖 Basic Sorting Algorithms

1. 버블 정렬 (Bubble Sort)

가장 큰 값이 버블처럼 위로 올라가는 모양을 하게 되는 알고리즘입니다

Pseudocode

i라는 변수를 통해 배열의 마지막 지점에서 시작지점까지 순회하는 반복문을 만듭니다
j라는 변수를 통해 시작점부터 i - 1 까지 순회하는 이중 반복문을 만듭니다
배열의 j번째 요소가 j + 1번째 요소보다 크면, 두 개의 위치를 바꿉니다 (Swap)
만약 Inner Loop 에서 Swap이 발생하지 않는다면, 모두 정렬된 것이므로 반복문을 종료합니다
정렬된 요소를 return 합니다

function bubbleSort(arr) {
  let noSwaps;
  for (let i = arr.length; i > 0; i--) {
      noSwaps = true;
      for (let j = 0; j < i - 1; j++) {
        if (arr[j] > arr[j+1]) {
            let temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
            noSwaps = false;
                         
         }
      }
    if (noSwaps) break;
   }
  return arr;
}

2. 선택 정렬 (Selection Sort)

가장 작은 값을 탐색한다음 Swap을 통해 앞부분에 배치시키는 정렬방식입니다.

Pseudocode

첫번째 요소를 min이라는 변수에 저장합니다
반복문을 통해 min을 다음요소들과 비교하면서 가장 작은 값을 min에 할당합니다
만약 min이 최초에 저장한 값이 아니라면, 두 값을 swap 합니다
arr의 모든 요소에 위 작업을 반복한 후 정렬된 배열을 리턴합니다

function selectionSort(arr) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  }
  
  for (let i = 0; i < arr.length; i++) {
      if (arr[min] > arr[j]) {
        min = j;
      }
   }
  
  if (arr[min] !== arr[i]) {
     swap(arr, i, min);
  }
  
  return arr;
}

3. 삽입 정렬 (Insertion Sort)

배열 두번째 요소부터 모든 요소를 앞부분에 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 방식의 정렬 알고리즘입니다

Pseudocode

배열의 두번째 요소를 Pick
두 번째 요소를 첫번째요소와 비교하고, 필요하다면 Swap
다음 요소로 계속 반복, 만약 순서가 틀리다면, 정렬된 부분을 순회하면서 정확한 위치에 배치한다
정렬될때까지 반복한다

function insertionSort(arr) {

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

📖 시간복잡도

지금까지 알아본 3가지 정렬 알고리즘의 시간복잡도는 아래와 같습니다

전반적으로 O(n^2) 의 비효율적인 시간복잡도를 갖습니다.
이미 어느정도 정렬이 되어있는 배열에서 버블 정렬과 삽입 정렬을 실행할 경우, O(n)의 시간복잡도를 갖게됩니다. 선택 정렬의 경우 이미 정렬이 어느정도 되어있다 하더라도 모든 요소들을 순회하면서 최소값을 탐색하게 되므로, 여전히 시간복잡도는 O(n^2)이 됩니다