[Algorithm] Sort #1 - 버블 정렬 Bubble Sort

버블 정렬이란?

 첫 번째 원소부터 인접한 두 원소를 검사하여 정렬하는 알고리즘

 

시간 복잡도

최상 : \( O(n^2) \)

최악 : \( O(n^2) \)

 

관련 글

[Algorithm] Sort #2 - 선택 정렬 Selection Sort

[Algorithm] Sort #3 - 삽입 정렬 Insertion Sort

[Algorithm] Sort #4 - 병합 정렬 Merge Sort

[Algorithm] Sort #5 - 힙 정렬 Heap Sort

[Algorithm] Sort #6 - 퀵 정렬 Quick Sort

 

---

 

 알고리즘의 기본이라고 할 수 있는 정렬에서 첫 번째는 버블 정렬입니다. 

 

알고리즘

 버블 정렬의 알고리즘은 다음과 같습니다.

1. 현재 원소를 기준으로 다음 원소와 비교한 뒤 정렬한다.
2. 1의 과정을 (1, 2)부터 차례대로 끝까지 진행한다.
3. 1,2의 과정을 n-1번 진행한다.

 

버블 정렬 예시

{ 9, 1, 7, 5, 2} 순서대로 원소가 존재한다고 가정했을 때 버블 정렬의 예시는 다음과 같습니다.

 

 

 1회 정렬 시 앞에 있던 9가 가장 뒤로 정렬된 것처럼 원소 중 가장 큰 숫자가 뒤로 간 것을 확인할 수 있습니다.

 

 그리고 정렬함에 따라 숫자가 큰 순서대로 뒤에부터 정렬이 되기 때문에 불필요한 정렬 과정을 생략할 수 있습니다. 그 예시로 4회 정렬을 수행할 때 5,7,9의 숫자는 이미 정렬되었기 때문에 1과 2만 비교하고 끝나도 문제없습니다.

 

시간 복잡도 계산

 버블 정렬의 시간복잡도는 최악, 최상의 경우 모두 동일합니다.

 

 각 정렬 회차에 따라 n-1, n-2, n-3 ..... 2, 1번 비교하기 때문에 n(n-1)/2번이므로 시간 복잡도는 \( O(n^2) \)입니다. 

 

C++ Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    vector<int> arr = {9,1,7,5,2};
    
    for(int i=0; i<arr.size(); i++)
        for(int j=0; j<arr.size()-i-1; j++)
            if(arr[j] > arr[j+1])
            	swap(arr[j], arr[j+1]);
    
    for(int i=0; i<arr.size(); i++)
        cout << arr[i];
}