1.-(2) 기본 정렬 알고리즘 - Bubble Sort (버블정렬)

이번 시간에 다뤄볼 알고리즘은 저번 시간에 이어 기본 정렬 알고리즘인 Bubble Sort 입니다.

 

Bubble Sort는 Selection Sort와 함께 가장 기본적인 정렬 알고리즘에 속합니다.

 

Bubble Sort의 동작 과정

 

1. 첫번째 수 부터 N-1 번째 수 까지 가면서 해당 수와 바로 다음 수를 비교한다.

2. 해당 수 보다 바로 다음 수가 더 작다면, 둘의 자리를 바꿔 큰 수가 뒤에 오도록 한다.

3. N번째 수에 도달하게 되면 그 자리에는 가장 큰 수가 오게된다.

4. 1~3 과정을 N-2번째 수 까지, N-3번째 수까지 ... ... 첫번째 수 까지 하게되면 모든 수가 오름차순으로 정렬된다.

 

 

1, 2, 3번과정을 수행하면 다음과 같이 진행됩니다.

여기서 초록색 부분은 현재까지 정렬된 구간입니다.

첫번째 수 부터 진행하여 다섯번째 수에 도달하게 되면 그 자리에는 가장 큰 수 7 이 오게 됨을 알 수 있습니다.

 

다섯번째 수 까지는 정렬된 구간이니, 네번째 수 까지 1, 2, 3 과정을 진행해보면

이렇게 7을 제외한 가장 큰 수 5까지 정렬된 구간이 됩니다.

 

더 진행하면 4, 5, 7 까지 정렬되고

마침내 모든 수가 오름차순으로 정렬됩니다.

 

이 알고리즘의 시간복잡도는 Selection Sort 와 마찬가지로 \( O(n^{2}) \) 입니다.

\( n \)개의 수가 있다면, \( n-1 + n-2 + ... ...+ 1 \) 번 비교를 해야하기 때문입니다.

 

공간복잡도 또한 Selection Sort와 마찬가지로 \( O(n) \) 입니다.

 

www.acmicpc.net/problem/2750

2750번: 수 정렬하기

마찬가지로 위 문제를 해결할 수 있습니다.

 

 

#include <bits/stdc++.h>
using namespace std;
 
int numbers[1001];
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for(int i=0;i<n;i++)
        scanf("%d", &numbers[i]);
 
    for(int i=0;i<n;i++)
    {
        // n-i 번째 수 까지 비교한다.
        for(int j=0;j<n-i-1;j++)
        {
            // 지금 보고 있는 수가 다음 수 보다 크면 자리 바꾸기
            if(numbers[j] > numbers[j+1])
            {
                // swap
                int tmp = numbers[j];
                numbers[j] = numbers[j+1];
                numbers[j+1] = tmp;
            }
        }
    }
 
    for(int i=0;i<n;i++)
        printf("%d\n", numbers[i]);
    return 0;
}