[Algorithm] Bubble Sort

알고리즘 정리 노트?의 시작은 정렬 알고리즘들로 시작하려고 한다. 처음 알고리즘 문제를 풀기 시작하면 제일 먼저 배웠던 것 같고... 군에서 머리가 너무 녹아서 복습도 할겸..

💡 동작원리

이 글에서는 Bubble Sort(버블정렬)에 대해 다뤄보려고 한다. Bubble Sort(버블정렬)의 원리는 가장 인접한 두 원소를 비교하여, 차순에 맞게 스왑하는 것이다.

위 그림은 오름차순으로 정렬하는 Bubble Sort(버블정렬)의 동작원리를 그림으로 표현한 것이다. i번째 원소와 i+1번째 원소를 비교하여 i번째 원소가 크면 스왑한다. 이를 끝까지 한 번 시행하면, 배열에서 가장 큰 원소가 N번째에 위치하게 된다. 이렇게 정렬되는 원소를 제외하고 계속 시행하면 배열이 오름차순으로 정렬된다. 이것이 Bubble Sort(버블정렬)이다.

💻 코드

void Bubble_Sort(){
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N - i; j++){
            if(Arr[j] > Arr[j + 1]){
                swap(Arr[j], Arr[j + 1]);
            }
        }
    }
}

⏱ 시간복잡도

(N-1) + (N-2) + ... + 1 = N(N-1)/2 이므로 시간복잡도는 $O(N^2)$가 된다.

$O(N^2)$