[알고리즘] 버블 정렬 (Bubble Sort)

버블정렬의 개념

버블정렬은 선택정렬과 유사한 개념으로 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다.
인접한 2개의 원소의 크기를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.

버블정렬의 장단점

장점

• 구현이 매우 간단하고, 소스코드가 직관적이다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않다. => 제자리 정렬(in-place sorting)
• 안정 정렬(Stable Sort) 이다.

단점

• 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적이다.
• 정렬 돼있지 않은 원소가 정렬 됐을때의 자리로 가기 위해서, swap이 많이 일어나게 된다.

시간복잡도

시간복잡도를 계산하면, $(n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2$이므로, $O(n^2)$ 이다.
또한, 버블 정렬은 정렬이 돼있던 안돼있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가 $O(n^2)$ 으로 동일하다.

구현

C++

#include <iostream>
#include <array>

using namespace std;

int main(){
    array<int, 5> arr = {7, 4, 5, 1, 3};
    int temp;
    for(int i = 0; i < arr.size()-1; i++){
        for(int j = 0; j < arr.size()-1; j++){
            if(arr[j] > arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    for(int i = 0; i < arr.size(); i++){
        cout << arr[i] << endl;
    }
}

Kotlin

fun main(){
    val list = mutableListOf<Int>(7, 4, 5, 1, 3)
    var temp: Int
    for(i in 0..list.size-2){
        for(i in 0..list.size-2){
            if(list[i] > list[i+1]){
                temp = list[i]
                list[i] = list[i+1]
                list[i+1] = temp
            }
        }
    }
    println(list)
}