버블 정렬

July 28, 2023

버블 정렬이란

버블 정렬은 순서가 잘못된 경우 인접한 요소를 반복적으로 교체하는 방식으로 진행되는 알고리즘입니다.

버블 정렬하는 과정을 간단히 정리하면 다음과 같습니다.

첫 번째 자료와 두 번째 자료 비교
두 번째 자료와 세 번째 자료 비교
세 번째 자료와 네 번째 자료 비교
배열의 마지막 요소까지 위 과정을 반복합니다.

가장 처음 1회전 정렬을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동합니다. 따라서 맨 큰에 있는 자료는 정렬에서 제외되어서 정렬을 수행할때마다 정렬에서 제외되는 데이터가 하나씩 늘어납니다.

버블 정렬 동작 과정

배열 [6, 3, 0, 5]을 예를 들어 살펴 보겠습니다.

6은 3보다 크므로 두 개의 위치를 바꾸고, 6은 0보다 크므로 두 개위 위치를 바꾸고, 6운 5보다 크므로 두 개의 위치를 바꿉니다. 가장 큰 요소는 배열의 끝에 배치됩니다.
```
[3, 0, 5, 6]
```
3은 0보다 크므로 두 개의 위치를 바꾸고, 3은 5보다 작으므로 두 개의 위치를 바꾸지 않습니다. 배열의 가장 끝 요소는 이미 정렬 되어있므로 비교하지 않습니다.
```
[3, 0, 5, 6]
```
3은 0보다 크므로 두 개의 위치를 바꿉니다. 배열의 가장 끝 - 1 인 요소는 이미 정렬된 되어있므로 비교하지 않습니다.
```
[0, 3, 5, 6]
```

버블 정렬 구현 코드

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

시간 복잡도 & 공간 복잡도

시간 복잡도

버블 정렬의 최악의 경우 시간 복잡도는 O(N^2)입니다.
버르 정렬의 평균적인 경우의 시간 복잡도는 O(N^2)입니다.
최선의 경우의 시간 복잡도는 O(N^2)입니다.

공간 복잡도

삽입 정렬의 공간 복잡도는 O(1)입니다.

버블 정렬의 특징

추가 메모리 공간이 필요하지 않습니다.
구현이 매우 간단합니다.
안정적인 배열입니다.
제자리 정렬입니다.

참조

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

https://www.geeksforgeeks.org/bubble-sort/

https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html