[알고리즘] 정렬 알고리즘 (JS)

📌 참고 사이트

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

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

 

버블 정렬 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

버블 정렬 - 위키백과, 우리 모두의 백과사전

 

선택 정렬 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

선택 정렬 - 위키백과, 우리 모두의 백과사전

 

[JS] 선택정렬 구현 / 시간 복잡도 — 정리하는 개발자 :) 쿼카 (tistory.com)

[JS] 선택정렬 구현 / 시간 복잡도

 

삽입 정렬 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

삽입 정렬 - 위키백과, 우리 모두의 백과사전

 

[JS 알고리즘] 삽입 정렬(Insertion sort) (velog.io)

[JS 알고리즘] 삽입 정렬(Insertion sort)

 

 

 

📋 정렬 (Sorting)

데이터들을 특정한 프로세스에 따라 재배치하는 과정을 의미한다.

기본적인 정렬 알고리즘으로는 버블 정렬, 선택 정렬, 삽입 정렬이 있다.

 

 

 

📋 버블 정렬 (Bubble Sort)

📍 버블 정렬의 특징

➡️ 기본적으로 배열의 두 수를 선택한 뒤, 두 수가 정렬되었다면 그대로 놔두고, 두 수가 정렬되지 않았다면 두 수의 자리를 바꾸는 식으로 정렬이 이루어진다.

 

➡️ 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보여주어 '버블 정렬' 이라는 이름이 붙게 되었다. 

 

➡️ 오름차순으로 정렬 시 a < b 가 되어 있을 경우, 내림차순으로 정렬 시 a > b가 되어 있을 경우를 정렬되었다고 판단하고, 이 비교를 배열의 처음부터 끝까지 진행해 배열에서 아무런 변화가 없을 때까지 위 알고리즘을 진행한다.

 

 

📍 버블 정렬 적용해보기

배열 [7, 2, 0, 1]에 버블 정렬(오름차순)을 적용해 보자.

 

→ 첫번째 원소 7과 두번째 원소 2 비교 : 7 > 2 이므로 자리를 바꾼다. => [2, 7, 0, 1]

→ 두번째 원소 7과 세번째 원소 0 비교: 7 > 0 이므로 자리를 바꾼다. => [2, 0, 7, 1]

→ 세번째 원소 7과 네번째 원소 1 비교: 7 > 1 이므로 자리를 바꾼다. => [2, 0, 1, 7]

→ 가장 큰 수인 7은 정렬이 완료되었으므로 범위를 좁혀 2에서부터 1까지 정렬하기

→ 첫번째 원소 2와 두번째 원소 0 비교: 2 > 0 이므로 자리를 바꾼다. => [0, 2, 1, 7]

→ 두번째 원소 2와 세번째 원소 1 비교: 2 > 1 이므로 자리를 바꾼다. => [0, 1, 2, 7]

→ 세번째 원소 2와 네번째 원소 7 비교: 2 > 7 이므로 자리를 바꿀 필요가 없다. => [0, 1, 2, 7] (그대로)

→ 이미 정렬이 완료되었으므로 더 범위를 좁혀서 정렬을 진행하더라도 요소의 위치가 그대로이다.

 

 

💻 버블 정렬 JS로 구현하기 (오름차순)

1️⃣ i라는 인덱스로 배열의 마지막 지점에서 시작 지점까지 순회할 수 있도록 한다.

2️⃣ j라는 인덱스로 배열의 시작 지점에서 i - 1 지점까지 순회할 수 있도록 이중 반복문을 만든다.

3️⃣ 배열의 j번째 요소가 j + 1번째 요소보다 크다면 두 요소의 위치를 바꾼다.

4️⃣ 만약 안쪽 반복문에서(j에 대한 반복문) swap이 일어나지 않으면 모두 정렬된 것이므로 반복문 종료 (swap의 여부를 알릴 수 있는 flag 변수 하나를 만들어 사용한다.)

5️⃣ 마지막에는 정렬된 배열을 반환한다.

 

function bubbleSort(arr) {
  // 원소의 위치가 바뀐 경우가 있는지 없는지를 알리기 위한 flag 변수 정의
  let noSwaps;
  
  for (let i = arr.length; i > 0; i--) {
    // noSwaps의 초기값은 true
    noSwaps = true;
    for (let j = 0; j < i - 1; j++) {
      // j번째 원소(앞에 있는 원소)가 j + 1번째 원소(뒤에 있는 원소)보다 더 클 경우
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        // 두 원소 swap
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        // 두 원소 swap이 일어나면 noSwaps를 false로 변경
        noSwaps = false;
      }
    }
    
    // 안쪽 반복문을 돌면서 한번도 원소 교환이 일어나지 않아서 noSwaps가 초기값 true를 계속 유지한다면
    // 앞으로도 계속 원소의 위치가 바뀔 일이 없으므로 바깥쪽 반복문 종료
    if (noSwaps) break;
  }
  return arr;
}


console.log(bubbleSort([7, 2, 0, 1, 5, 6, 4]));
// [0, 1, 2, 4, 5, 6, 7]

 

 

 

📋 선택 정렬 (Selection Sort)

📍 선택 정렬의 특징

➡️ 제자리 정렬 알고리즘(원소들의 개수에 비해서 충분히 무시할 만한 저장 공간만을 더 사용하는 알고리즘)의 하나이다.

 

➡️ 주어진 배열의 원소 중 최소값을 찾고, 그 값을 맨 앞에 위치한 값과 교체하고, 맨 처음 위치를 뺀 나머지 배열 요소들을 같은 방법으로 교체하는 과정을 가진다.

 

 

📍 선택 정렬 적용해보기

배열 [9, 1, 6, 8]에 선택 정렬(오름차순)을 적용해 보자.

 

→ 배열에서 가장 작은 원소는 1이고, 첫번째 원소인 9와 자리를 교체한다. => [1, 9, 6, 8]

→ 첫번째 원소를 제외한 나머지 원소들 중에서 가장 작은 원소는 6이고, 두번째 원소인 9와 자리를 교체한다. => [1, 6, 9, 8]

→ 첫번째, 두번째 원소를 제외한 나머지 원소들 중에서 가장 작은 원소는 8이고, 세번째 원소인 9와 자리를 교체한다. => [1, 6, 8, 9]

→ 마지막 원소인 9에 이르렀으므로 정렬이 종료된다. 

 

 

💻 선택 정렬 JS로 구현하기 (오름차순)

Math.min을 사용하지 않고 구현해 보겠다.

1️⃣ 첫번째 원소를 min이라는 변수에 저장한다.

2️⃣ 반복문으로 배열을 순회하며 min을 다음 요소들과 비교하며 가장 작은 값을 min에 할당한다.

3️⃣ 만약 min이 최초에 저장한 값이 아니라면, 두 값의 위치를 바꾼다.

4️⃣ 배열의 모든 요소에 위 작업을 반복한 후 정렬된 배열을 반환한다.

 

function selectionSort(arr) {
  // 배열의 모든 요소 순회
  for (let i = 0; i < arr.length; i++) {
    // min(최소값 인덱스)은 일단 배열의 첫번째 요소로 초기값 잡아놓기
    // (바깥 반복문을 한번 돌 때마다 배열의 첫번째 요소는 인덱스가 1씩 증가, 배열의 범위를 좁혀나간다고 생각)
    let min = i;
    // 두번째 요소부터 배열의 끝까지 순회
    for (let j = i+1; j < arr.length; j++) {
      // arr[j]가 arr[min] 보다 더 작다면
      if (arr[j] < arr[min]) {
        // 최소값 인덱스 min을 현재 인덱스인 j로 업데이트
        min = j;
      }
    }
    // 만약 최소값 인덱스와 배열의 첫번째 요소의 인덱스가 다르다면
    // (배열의 첫번째 요소가 최소값이 아닌 경우)
    if (min !== i) {
      // 배열의 첫번째 값과 최소값의 위치를 swap한다.
      [arr[i], arr[min]] = [arr[min], arr[i]];
    }
  }
  // 반복문이 모두 종료되면 정렬 종료이므로 정렬된 arr 반환
  return arr;
}

console.log(selectionSort([9, 1, 6, 8, 4, 3, 2, 0]));
// [0, 1, 2, 3, 4, 6, 8, 9]

 

 

 

📋 삽입 정렬 (Insertion Sort)

📍 삽입 정렬의 특징

➡️ 자료 배열의 모든 요소를 앞에서부터 차례로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

 

➡️ 각 반복에서 정렬되지 않은 나머지 부분 중 첫 번째 항목은 제거되어 정확한 위치에 삽입된다.

 

 

📍 삽입 정렬 적용해보기

배열 [31, 25, 12, 22] 에 삽입 정렬(오름차순)을 적용해 보자. 

 

→ 배열의 두번째 원소인 25를 선택하여 첫번째 원소와 비교 결과, 31 > 25이므로 자리를 교체한다. => [25, 31, 12, 22]

→ 배열의 세번째 원소인 12를 선택하여 첫번째 원소와 비교 결과, 25 > 12이므로 첫번째 자리에 12를 삽입한다. => [12, 25, 31, 22]

→ 배열의 네번째 원소인 22를 선택하여 첫번째 원소와 비교 결과 12 < 22로 올바른 순서이므로 다음 원소로 넘어간다. 비교 결과 25 > 22이므로 두번재 자리에 22를 삽입한다. => [12, 22, 25, 31]

 

 

💻 삽입 정렬 JS로 구현하기 (오름차순)

1️⃣ 배열의 두번째 요소를 선택한다.

2️⃣ 두 번째 요소를 첫번째 요소와 비교하고 두 번째 요소가 첫 번째 요소보다 더 작다면 swap한다.

3️⃣ 다음 요소로 계속 반복하고, 요소의 앞부분인 정렬된 부분을 순회하면서 정확한 위치에 배치한다.

4️⃣ 모든 요소가 정렬될 때까지 반복한다.

 

function insertionSort(arr) {
  // 바깥 반복문은 정렬되지 않은 부분을 순회한다.
  for (let i = 1; i < arr.length; i++) {
    // 현재 요소는 현재 i를 인덱스로 가지는 요소로 한다.
    let currentVal = arr[i];
    let j;
    // 안쪽 반복문은 정렬된 부분을 순회한다.
    // i-1번째부터 시작하여 배열의 앞쪽으로 가고, arr[j]가 currentVal보다 클 때까지만 반복한다.
    for (j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
      arr[j + 1] = arr[j];
    }
    arr[j + 1] = currentVal;
  }
  return arr;
}

console.log(insertionSort([4, 3, 2, 1, 5, -5, 20, 17]));
// [-5, 1, 2, 3, 4, 5, 17, 20]

 

 

 

🕛 시간 복잡도

 

알고리즘명	최적의 시간 복잡도	평균 시간 복잡도	최악의 시간 복잡도	공간 복잡도
버블 정렬	O(n)	O(n^2)	O(n^2)	O(1)
선택 정렬	O(n^2)	O(n^2)	O(n^2)	O(1)
삽입 정렬	O(n)	O(n^2)	O(n^2)	O(1)