정렬 알고리즘(1. 버블정렬)

알고리즘을 공부하다보면 자료형을 정렬하는 일이 꽤 빈번한게 발생합니다.

Java에서는 Arrays.sort나 Collections.sort와 같은 편리한 메서드들이 자동으로 정렬을 해주기 때문에 평소에는 정렬 알고리즘의 내부 동작 방식에 대해 깊이 고민할 필요가 없었습니다.

하지만, 정렬 알고리즘 내에서도 다양한 방식이 존재하고 그 방식별로 시간복잡도, 공간복잡도, 안정성이 다르기 때문에 한번쯤 공부를 하고 넘어가는 것이 좋겠다라고 생각해 이렇게 공부 내용을 정리하게 되었습니다.

정렬 시리즈는 해당 정렬에 대한 간단한 설명과 동작방식 그리고 구현을 해보는 순서로 진행해보겠습니다.

---

버블정렬

1. 개념

평균	최악	메모리	안정성
$O(N^2)$	$O(N^2)$	$O(1)$	O

버블정렬은 말 그대로 Bubble(공기방울)과 유사한 정렬입니다.
물 속에서 공기방울은 차츰차츰 단계별로 올라가게되는데 이런 공기방울과 유사한 방식으로 동작한다고 보면 이해하기쉽습니다.

버블 정렬은 이웃 요소 둘을 비교해서 올바른 순서로 고치는 과정을 반복하는 알고리즘입니다.
배열을 올림차순으로 정렬한다고 가정했을때, 한번의 순회마다 가장 큰 값이 가장 위로 올라가는 것입니다.

2. 동작 과정

int[] arr = new int[]{7,4,2,5,6};

1. 처음 인덱스(0)부터 차례대로 이웃한 항과 비교
2. 비교(왼쪽 요소 기준)
   • 우측 항보다 작을 경우: 순서 유지
   • 우측 항보다 클 경우: 두 요소 위치 변경
3. 인덱스를 순차적으로 증가시키며 해당 과정 반복

→ 해당 과정을 1회 통과마다 가장 높은 값이 가장 오른쪽에 배치됩니다.

즉, 가장 높은 값이 순회마다 오른쪽에 배치되며 매 순회마다 살펴보는 요소의 수는 1개씩 줄어들게 됩니다.(= 이미 최댓값으로 고정되기 때문)

버블 정렬의 시간 복잡도

버블 정렬은 총 N-1회의 반복을 진행합니다.
순회를 하며 방문하는 요소의 수는 N-1 → N-2 → ... 1 로 줄어들게 되는데 모든 항이 평균적으로 $\frac{N}{2}$ 만큼 방문하게 됩니다.
또, 원본 배열을 가지고 정렬을 진행하기때문에 별도의 메모리 소요는 없기때문에 공간복잡도는 $O(1)$이 됩니다.

이를 정리해보면 아래와 같습니다.

• 총 반복 횟수: N-1
• 평균 반복 요소 수: $\frac{N}{2}$
• 시간 복잡도: $O(\frac{N(N-1)}{2}) ⇒ O(N^2)$
• 공간복잡도: $O(1)$
• 안정성: X

구현

void bubbleSort(int[] arr) {
        int len = arr.length;

        for(int i = 0; i < len-1; i++){
            for(int j = 0; j < len-i-1; j++){
                if(arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }

‼️주의
앞서 동작 과정을 봐서 알다시피 매 반복마다 방문하는 요소의 수는 1씩 줄어들게 되기때문에 len -1 이 아닌 len - i - 1이 되게 됩니다.

---

버블 정렬은 가장 기본적인 정렬 방식인만큼 언제든지 구현이 가능할 정도로 학습하는 것이 좋습니다 🙂 (학습하세효!)