버블 정렬 (Bubble sort)

김신·2023년 1월 20일

버블 정렬 알고리즘 정렬

알고리즘

목록 보기

3/7

버블 정렬의 목적

배열의 값을 오름차순 순으로 정렬한다.

버블 정렬 알고리즘

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 오름차순으로 정렬하는 경우, 왼쪽 원소가 오른쪽 원소보다 크다면 두 원소의 위치를 바꾼다. 선택 정렬과 기본 개념이 비슷하다.

버블 정렬 알고리즘은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, ... 이런 방법으로 (N - 1) 번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.

1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어간다.

버블 정렬 알고리즘의 예제

배열에 7, 4, 5, 1, 3이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.

예제가 알려주는 것은 간단하다. 큰 값이 제일 뒤로 간다.

버블 정렬 알고리즘 C++ 예제 코드

#include <iostream>

using namespace std;

void bubble_sort(int *arr, int n)
{
    int temp;

    for (int i = n - 1; i > 0; i--)
    {
        for (int j = 0; j < i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main()
{
    int n;
    cin >> n;

    int *arr = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    bubble_sort(arr, n);

    for (int i = 0; i < n; i++)
        cout << arr[i] << '\n';

    return 0;
}