[알고리즘] 버블 정렬, 선택 정렬, 삽입 정렬 정리 및 비교

 

프로그래밍에서 정렬 알고리즘은 가장 기초적이면서도 중요한 개념이다. 정렬 알고리즘은 컬렉션(collection)의 항목을 재배열하는 과정이다. 최신순, 인기순, 제목순으로 글을 재배열하는 모든 서비스들에서 우리는 정렬을 만나왔다. 

버블 정렬, 선택 정렬, 삽입 정렬 세 가지를 한 번에 비교하고, 각 알고리즘의 특징과 장단점을 살펴보자.

---

버블 정렬(Bubble Sort)

버블 정렬은 인접한 두 원소를 비교하고 필요 시 교환(swap)하며 큰 값이 뒤로 이동하는 방식으로 배열을 정렬한다.
말 그대로 큰 값이 거품처럼 위로 떠오른다는 느낌에서 이름이 유래했다.

동작 방식

1. 배열의 첫 원소부터 인접한 두 값을 비교.
2. 앞의 값이 뒤보다 크면 교환.
3. 배열 끝까지 반복하면 가장 큰 값이 맨 뒤로 이동.
4. 다음 패스에서는 마지막 원소는 이미 정렬되어 있으므로 범위를 줄임.
5. 배열이 정렬될 때까지 반복.

최적화 포인트

• 교환 여부 체크 (swapped 플래그): 교환이 없으면 이미 정렬 완료 → 반복 종료.
• 내부 반복 범위 축소 (n - 1 - i): 이미 정렬된 마지막 원소는 비교 생략.
• 마지막 교환 위치 기록 (고급): 마지막으로 교환이 일어난 위치까지만 비교.

function bubbleSort(arr) {
  let n = arr.length;
  let swapped;

  for (let i = 0; i < n - 1; i++) {
    swapped = false;

    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }

    if (!swapped) break;
  }

  return arr;
}

console.log(bubbleSort([5, 3, 8, 4, 2])); // [2, 3, 4, 5, 8]

 

장단점

✅ 장점

• 구현 간단, 직관적.
• 거의 정렬된 데이터에서 빠름.

❌ 단점

• 평균/최악: O(n²), 대규모 데이터에는 비효율적.
• 삽입/병합/퀵 정렬 대비 실무 활용도 낮음.

---

3. 선택 정렬(Selection Sort)

 

선택 정렬은 배열에서 최솟값을 찾아 맨 앞에 위치한 값과 교환해 나가는 방식의 정렬이다.

• 버블과 차이점: 버블은 큰 값을 뒤로 밀고, 선택은 전체에서 최솟값을 찾아 맨 앞으로 이동.
• 정렬된 데이터는 앞쪽부터 누적

동작 방식

예시 배열: [19, 44, 38, 5, 47, 15]

1. 배열 처음부터 최솟값(5)을 찾아 첫 위치와 교환 → [5, 44, 38, 19, 47, 15]
2. 다음 위치에서 나머지 배열 중 최솟값(15)을 찾아 교환 → [5, 15, 38, 19, 47, 44]
3. 끝까지 반복 → [5, 15, 19, 38, 44, 47]

JavaScript 예시

function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let lowest = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[lowest]) lowest = j;
    }
    if (lowest !== i) [arr[i], arr[lowest]] = [arr[lowest], arr[i]];
  }
  return arr;
}

console.log(selectionSort([19, 44, 38, 5, 47, 15])); // [5, 15, 19, 38, 44, 47]

장단점

✅ 장점

• 구현 간단, 이해 쉬움.
• 스왑 횟수 최소(한 루프당 1회).

❌ 단점

• O(n²) 비교, 큰 데이터에 비효율.
• 거의 정렬된 데이터에서도 속도 향상 없음.

---

삽입 정렬(Insertion Sort)

삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고,
정렬되지 않은 원소를 꺼내 정렬된 부분의 적절한 위치에 삽입하면서 정렬하는 알고리즘입니다.

• 특징: 작은 데이터셋이나 거의 정렬된 데이터에서 빠름.
• 실시간 데이터 추가에도 적합.

동작 방식

정렬 배열: [5, 3, 4, 1, 2]

1. 첫 번째 원소(5)는 이미 정렬된 부분으로 간주.
2. 두 번째 원소(3) → 5보다 작음 → 앞으로 이동 → [3, 5]
3. 세 번째 원소(4) → [3, 4, 5]
4. 네 번째 원소(1) → [1, 3, 4, 5]
5. 마지막 원소(2) → [1, 2, 3, 4, 5]

JavaScript 예시

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

console.log(insertionSort([2, 1, 9, 76, 4])); // [1, 2, 4, 9, 76]

장단점

✅ 장점

• 거의 정렬된 데이터에서 매우 빠름.
• 실시간 데이터 삽입 시 효율적.
• 구현 간단, 직관적.

❌ 단점

• 평균/최악: O(n²), 무작위 데이터에서는 비교 많음.

---

5. 알고리즘 비교

알고리즘	특징	장점	단점
버블 정렬	인접 값 비교 후 스왑, 큰 값 뒤로 이동	거의 정렬된 데이터 빠름	랜덤 데이터에서 느림
삽입 정렬	정렬된 부분에 새 값 삽입	거의 정렬된 데이터, 실시간 삽입 적합	무작위 데이터에서 비교 많음
선택 정렬	전체에서 최솟값 찾아 맨 앞로 이동	구현 간단, 스왑 최소	항상 O(n²), 느림

거의 정렬된 데이터 성능

• 버블/삽입: 빠르게 정렬 가능.
• 선택: 전체 훑어야 하므로 느림.

---

6. 결론

• 작은 데이터: 세 알고리즘 모두 사용 가능.
• 거의 정렬된 데이터: 삽입/버블 정렬 추천.
• 대규모 데이터: 합병 정렬, 퀵 정렬 등 더 효율적인 알고리즘 필요.
• 삽입 정렬: 실시간 데이터 추가 시 장점.
• 선택 정렬: 학습용이나 스왑 최소화가 필요할 때만 유용.