버블 정렬(bubble sort) 구현하기(c++)

0~n-1까지 인접한 값들을 비교하면서, 크기가 더 큰 원소를 뒤로 보내주는 연산을 (원소의 개수-1)만큼 반복해주면 된다.

 

왜? (원소의 개수-1)만큼 반복해주나?

5, 4, 3, 2, 1 처럼 모든 원소의 자리를 바꿔야 하는 경우에는 총 4번을 연산하면 1, 2, 3, 4, 5와 같은 형태로 바꿀 수 있다.

즉, 최악의 경우까지 고려하여 (원소의 개수-1)만큼 반복 연산해주면 오름차순으로 정렬할 수 있다.

 

 

*시간복잡도*

Best	Avg	Worst
O(n^2)	O(n^2)	O(n^2)

 

코드 첨부

// 버블 정렬 구현(오름차순)
#include <iostream>
using namespace std;
 
// 초기 배열 상태
int arr[5] = {2, 1, 4, 0, 3};
 
void bubble_sort(int arr[], int size)
{
    for(int i=0; i<size-1; i++){ // 반복(size-1만큼)
        for(int j=0; j<size-1; j++){
            if(arr[j]>arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}
 
int main()
{
    bubble_sort(arr, 5);
    for(int i=0; i<5; i++){
        cout<<arr[i]<<" ";
    }
    cout<<"\n";
}

 

위의 표는 아래 블로그에서 참조했습니다.

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

[알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog