2. 거품 정렬 bubble sort

2750. 수 정렬하기

https://www.acmicpc.net/problem/2750

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1<=N<=1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절대값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 

5
5
2
3
4
1

예제 출력 

1
2
3
4
5

1. 거품 정렬 소개

삽입 정렬 다음으로 간단한 정렬 알고리즘을 소개하고자 한다.

마찬가지로 인간의 정렬 방법과 유사한 알고리즘이다. 삽입 정렬에선 가지고 있는 숫자 타일을 하나 내려놓고, 정렬하고 했다면,

이번에는 가지고 있는 숫자 타일 중 가장 큰 수 부터 내려놓는 방법이다.

그러면 가장 큰 수는 어떻게 찾을까? 당연히 전체를 다 뒤져야 한다.

여러 방법이 있겠지만, 거품 정렬에선 이름 처럼 거품이 떠오르는 듯한 방법을 쓴다.

1) 맨 앞의 두 인자를 비교해서(인덱스 0과 1), 올바른 순서면 바꾸지 않고, 아니라면 서로 바꾼다. (swap)

2) 이번엔 다음 두 인자를(인덱스 1, 2) 마찬가지로 비교하고 스왑한다.

3) 배열의 마지막 두 인자 까지 2)를 수행한다.

다 수행했으면 배열의 상태는 어떠할까? 중간 인자들의 상태는 뒤죽박죽일지 몰라도 가장 마지막 숫자는 올바른 위치에 있다.

오름차순으로 정렬하기로 했다면, 배열 중 가장 큰수가 가장 맨 마지막에 있게 되는 것이다.

이제 제대로 박힌 마지막 인자를 제외하고 다시 처음부터 과정을 반복하면 된다.

그러면 뒤에서 부터 올바른 위치로 인자들이 채워지는 것이다.

애니메이션으로 확인해보자.

뒤에서 부터 한 점씩 채워지는 과정을 눈으로 확인할 수 있다.

2. 코드

#include <stdio.h>
#include <vector>
using namespace std;
 
int n, tmp;
vector<int> v;
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &tmp);
        v.push_back(tmp);
    }
 
    for (int i = n - 2; i >= 0; --i) {
        for (int j = 0, k = 1; j <= i; ++j, ++k) {
            if (v[j] > v[k]) {
                tmp = v[j];
                v[j] = v[k];
                v[k] = tmp;
            }
        }
    }
 
    for (int i = 0; i < n; ++i)
        printf("%d\n", v[i]);
 
    return 0;
}

3. 시간 복잡도

삽입 정렬과의 차별점은, 삽입 정렬이 for문 안이 while문으로 되어있다면, 거품 정렬은 for문으로 되어있다는 점이다.

따라서 삽입 정렬은 운이 좋다면 while문이 별로 돌지 않고 끝날 수 있지만,

거품 정렬은 그런거 없고 무조건 for문을 다 돌아야 한다.

또한 최악의 경우 마찬가지로 이중for문으로 인해 시간복잡도는 O(n ^ 2)이다.