[자료구조/TS] Bubble Sort

Bubble Sort(버블 정렬)

• 버블 정렬은 선택 정렬과 유사한 아이디어에 기반한다. 선택 정렬처럼 제일 큰 원소를 끝자리로 옮기는 작업을 반복하되 제일 큰 원소를 오른쪽으로 옮기는 방법이 다르다.

• 인접한 2개의 레코드를 비교하여 순서대로 되어 있지 않으면 교환하는 정렬방법이다

• 레코드의 이동과정이 물속에서 거품이 보글보글 떠오르는 것과 유사하여 버블정렬이라 부른다(exchange sort라고도 부른다)

• 시간복잡도가 최선의 경우 $O(n)$ 이고 최악의 경우 $O(n^2)$이다.

• 버블 정렬은 상대적으로 느리기 때문에, 실제 환경에서는 더 효율적인 정렬 알고리즘을 사용하는 것이 일반적이다.

사용처

• 거의 정렬된 배열의 경우
  거의 정렬된 배열에서 버블 정렬은 성능이 상대적으로 좋다. 배열이 거의 정렬되어 있거나 작은 변화만 필요할 때, 버블 정렬은 비교적 빠르게 동작할 수 있다. 이 경우, 버블 정렬의 최적화된 버전 (이미 정렬된 경우에는 더 이상 비교하지 않는 방식)을 사용할 수 있다.
• 메모리 제약이 있는 환경
  In-place 정렬: 버블 정렬은 추가 메모리를 거의 사용하지 않고, 입력 배열 내에서 직접 원소들을 교환하기 때문에 추가 메모리를 사용할 수 없는 상황에서 유용할 수 있다. 다만, 실무에서는 효율성 면에서 더 좋은 in-place 정렬 방법이 있기 때문에, 버블 정렬을 사용하지 않는 경우가 더 많다.
• 작은 데이터셋에서의 사용
  작은 배열에서는 버블 정렬도 충분히 빠르게 동작할 수 있다. 10개 이하의 원소를 가진 배열을 정렬할 때는 복잡한 알고리즘을 사용할 필요 없이, 간단한 버블 정렬이 빠르게 해결할 수 있다.
• 정렬 조건이 단순할 때
  복잡한 정렬이 필요 없고, 간단히 인접한 원소들 간의 비교로 충분한 경우 버블 정렬이 사용될 수 있다. 다만, 이런 경우에도 일반적으로 더 효율적인 알고리즘이 존재하므로, 실제 사용은 드물다.
• 교육적 시각화 도구
  버블 정렬은 정렬 과정이 직관적이고, 하나씩 자리를 찾아가는 과정이 명확하므로 알고리즘의 시각화에 자주 사용된다. 이는 사람들이 정렬 알고리즘의 동작 방식을 쉽게 이해하도록 도와준다.

class BubbleSort

const bubbleSort = (list: number[]) => {
    let temp = 0;

    for (let last = list.length - 1; last >= 2; last--) {
        let swapped = false; 

        for (let i = 0; i < last; i++) {
            
            if (list[i] > list[i + 1]) {

                console.log(`element 위치 변경 : ${list[i]} / ${list[i+1]} `);
                
                // temp = list[i];
                // list[i] = list[i + 1];
                // list[i + 1] = temp;

                [list[i], list[i+1]] = [list[i+1] , list[i]]

                swapped = true; 
            }
        }

        if (!swapped) {
            break;
        }
    }

    console.log(list.join("-")); 

}

bubbleSort([21, 5, 22, 4, 15, 33]);

element 위치 변경 : 21 / 5 
element 위치 변경 : 22 / 4 
element 위치 변경 : 22 / 15
element 위치 변경 : 21 / 4
element 위치 변경 : 21 / 15
element 위치 변경 : 5 / 4
4-5-15-21-22-33

swapped변수

swapped 변수를 사용하여 버블 정렬 알고리즘의 성능을 최적화하는 데 도움을 준다.

1. 불필요한 반복 방지
   swapped는 현재 반복에서 교환이 발생했는지를 나타내는 불리언 이며, 한 번의 전체 반복에서 교환이 발생하지 않았다면, 배열이 이미 정렬되어 있다는 것을 의미하므로 추가적인 반복을 수행할 필요가 없다.
2. 최적화
   swapped 변수를 사용하여 교환이 일어났는지 확인한 후, 반복문을 계속 진행할지 여부를 결정한다.
   교환이 일어나지 않았다면 break를 사용하여 가장 바깥의 for 문을 종료하게 되며, 이렇게 함으로써 불필요한 비교를 줄일 수 있다.
3. 이점
   배열이 이미 정렬된 경우, 최악의 경우 $𝑂(𝑛^2)$의 시간 복잡도를 가지는 버블 정렬이지만, swapped 변수를 사용하여 조기 종료할 수 있다면 시간 복잡도를 $𝑂(𝑛)$으로 줄일 수 있다. 이는 성능을 크게 향상시키는 요소가 될 수 있다.