버블 정렬 bubble sort

가장 쉽게 떠올릴 수 있는 방법 중 하나가 아닐까 싶다.
1학년 때 c언어 수업에서 가장 먼저 접했던 버블 소트,,,
다시 정리해보자.

버블 정렬이란?

• 버블 정렬은 바로 인접한 두 개의 원소를 비교하여 정렬하는 알고리즘이다.
• 단순하게 둘을 비교해서 그 순서가 제대로 되어있지 않으면 swap해준다.
• 선택 정렬과 기본 개념이 유사하지만 선택정렬은 하나의 인덱스를 뽑아 앞의 정렬된 부분과 비교해주는 반면, 버블 정렬은 그저 자신의 바로 옆 인덱스 하나와만 비교해준다는 차이가 있다.

버블 정렬 예제

• 배열에 8 6 5 4 2가 저장되어있다고 생각해보자.

1. 8 6 5 4 2
   • 8(arr[j-1])과 6(arr[j])을 비교해준다.
   • 8이 6보다 크므로 swap
2. 6 8 5 4 2
   • 6, 8 둘이 정렬이 되었다.
   • 다음 5와 8을 비교해주기 위해서 j++를 해준다.
   • 8(arr[j-1]), 5(arr[j])가 되고 8이 5보다 크므로 swap
3. 6 5 8 4 2
   • 6 5 8까지 정렬이 들어갔고, 8과 4를 비교해줄 차례다.
   • j++를 해주고 8과 4를 비교한다.
   • 8이 4보다 크므로 swap
4. 6 5 4 8 2
   • j++ 후 8과 2를 비교
   • swap
5. 6 5 4 2 8
   • j가 배열의 끝까지 왔으므로 for문을 나가서 i를 증가시킨다.
   • i=1이 되고 다시 j=1부터 시작하여 바로 앞의 인덱스 (j-1)과 비교한다.

해당 과정을 코드로 정리하면 다음과 같다.

void bubbleSort(int length){
    for(int i=0; i<length; i++){
        for(int j=1; j<length-1; j++){
            if(numbers[j-1] > numbers[j])
                swap(numbers[j-1], numbers[j]);
        }
    }
}

버블 정렬의 특징

• 장점
  - 구현이 간단하다
• 단점
  - 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열의 모든 다른 요소들과 교환되어야 한다.
  • 특정 요소가 최종 정렬 위치에 이미 위치한 경우더라고 자리가 변경된다.
  • 해당 단점들 때문에 구현의 단순성에도 불구하고 거의 사용되지 않는다.

시간복잡도

• best
  O(n^2)
  • 1 2 3 4 5 과 같이 이미 정렬되어있는 배열을 정렬하더라도 계속 비교를 해야하기 때문에 best의 경우에도 시간 복잡도는 O(n^2)로 일정하다.
• worst
  O(n^2)
  • 최악의 경우, 5 4 3 2 1의 경우에도 best와 똑같은 과정을 거쳐야 하므로 일정하다.