버블정렬 (Bubble Sort)

거품정렬(Bubble Sort)은 인접한 원소들의 대소관계를 비교하여 일정한 대소관계를 만족하지 않을 시, 인접한 원소를 교환하는 방법으로 진행되는 정렬입니다.

다음은 버블 정렬을 쉽게 시각화 한 내용입니다.

먼저 4와 2를 비교해 4가 2보다 크므로

2와 4의 위치를 바꿔 줍니다.

이후 4와 3을 비교하여 4가 3보다 크므로

4와 3의 위치를 바꿔 줍니다.

전과 동일하게 4와 1을 비교하여

위치를 바꾸어 줍니다.

처음 정한 원소인 4 다음 원소가 없으면 다시 첫 번째 원소인 2를 선택해 다음 원소인 3과 비교합니다. 2와 3은 위치를 바꿀 필요가 없으므로 그대로 놔둡니다.

다음 원소인 3에 대해 오른쪽 원소인 1과 비교합니다. 3이 더 크므로

1과 3의 위치를 바꾸어 줍니다.

4는 이미 정렬되어 있으므로 3과 4를 비교하지 않고 다음 정렬 순서로 넘어갑니다.

다시 첫 번째 원소인 2를 오른쪽 원소인 1과 비교하여 2가 1보다 크므로

1과 2의 위치를 바꿔 줍니다.

이후 3이 정렬 되어 있으므로 2를 정렬하고

1을 정렬하려 버블 정렬을 마무리합니다.

버블 정렬을 쉽게 도식화 한 그림과 설명을 보면 **한번 위치 교환을 통해 가장 큰 원소가 마지막으로 가는 것을 확인할 수 있습니다. 이를 통해 마지막 원소가 정렬되었다고 볼 수 있고, 이를 N-1번 반복한다면 버블 정렬이 끝납니다. N개의 원소가 있다면, N-1번의 교환을 통해 정렬할 수 있습니다. **이를 시간 복잡도로 나타내면 (정렬해야 할 원소의 개수 - 1) *(최대 교환 수) 이므로 O(N²)이 됩니다. 힙 정렬, 퀵 정렬과 같은 정렬보다 비효율적이므로 자주 쓰지 않습니다.

다음은 C++로 나타낸 코드입니다.

#include <iostream>
#include <algorithm>
#define MAX 5005
using namespace std;
 
int d[MAX];
 
int main()
{
	int n;
	cin >> n;
 
	for (int i = 0; i < n; i++) {
		cin >> d[i];
	}
 
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < n - i - 1; j++) {
			if (d[j] > d[j + 1]) {
				swap(d[j], d[j + 1]);
			}
		}
	}
 
	for (int i = 0; i < n; i++) {
		cout << d[i] << " ";
	}
 
	return 0;
}

다음은 Java로 나타낸 코드입니다.

import java.util.*;
 
public class Main {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
 
        int[] d = new int[5005];
 
        for (int i = 0; i < n; i++)
            d[i] = scanner.nextInt();
 
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n - i - 1; j++)
                if (d[j] > d[j + 1]) {
                    int temp = d[j];
                    d[j] = d[j + 1];
                    d[j + 1] = temp;
                }
 
        for (int i = 0; i < n; i++)
            System.out.print(d[i] + " ");
    }
}

다음 시간엔 에라토스테네스의 체에 대해 알아보겠습니다.