이번 글에서는 버블 정렬에 대해서 알아보려고 한다.

버블 정렬이란?

• 두 개의 인접한 원소를 검사하여 정렬하는 알고리즘이다.
• 예를 들어, 첫 번째와 두 번째를 비교하고 교환하고 두 번째와 세 번째를 비교하여 교환하는 식으로 진행하여 n 번째와 n+1번째 자료를 비교하고 교환하여 정렬을 진행한다.
• 버블 정렬의 특징으로는 맨 끝의 자료는 정렬이 완료되었기에 제외된다는 점에 있다. 그렇기에 마지막 요소는 반복문에서 제외한다.
• 예를들어 살펴보자 ( 5 3 4 1 2 ).
  • 1회전
    • 5 3 4 1 2 → 3 5 4 1 2 → 3 4 5 1 2 → 3 4 1 5 2 → 3 4 1 2 5
  • 2회전
    • 3 4 1 2 5 → 3 4 1 2 5 → 3 1 4 2 5 → 3 1 2 4 5
  • 3회전
    • 3 1 2 4 5 → 1 3 2 4 5 → 1 2 3 4 5
  • 4회전
    • 1 2 3 4 5 → 1 2 3 4 5
  • 5회전
    • 1 2 3 4 5
• 위처럼 각 회전에서 n번째와 (n+1)번째 원소를 비교하여 작다면 앞으로 옮기는 식으로 이루어진다.
• 각 회전에 대한 설명은 다음과 같다.
  • 1회전이 끝나고 마지막 5번째 원소인 5는 정렬에서 제외된다.
  • 2회전이 끝나고 4번째 원소인 4는 정렬에서 제외된다.
  • 3회전이 끝나고 3번째 원소인 3이 정렬에서 제외된다.
  • 4회전에서는 2번째 원소인 2가 정렬에서 제외된다.
  • 5회전에서는 1번째 원소까지 정렬이 완료되면서, 정렬이 종료되게된다.

코드 (Java)

for(int i = 0; i < number-1; i++){
    for(int j = 0; j < number-i-1; j ++){
        if(numArr[j] > numArr[j+1]){
            int tmp = numArr[j];
            numArr[j] = numArr[j+1];
            numArr[j+1] = tmp;
        }
    }
}

• 코드에서는 인접한 두 숫자의 크기를 비교하여 교환하는 방식으로 이루어진다.

시간복잡도

• 버블 정렬의 시간복잡도는 for문을 통해 전체를 탐색하면서 2중 for문을 통해 인접한 원소를 계속 비교해나가기 때문에 **O(N^2)**이다.
• 비교횟수는 최선, 평균, 최악의 상황 모두 O(N^2) 일정하다.
• 하지만 교환이 한 번도 일어나지 않았을 때 break로 반복문을 탈출하도록 코드를 작성한다면, 최선의 상황에는 **O(N)**의 시간복잡도를 가지게 된다.

참고 -