버블 정렬

버블 정렬은 인접한 두 원소를 차례대로 비교하면서 자리바꿈을 통해 정렬된 순서를 맞추는 것을 반복하면서 정렬하는 방식이다. 원소의 이동이 거품처럼 수면으로 올라오는듯한 모습으로 버블 정렬이라는 이름이 붙여졌다.

arr [] = { 30, 50, 20, 10, 40 }의 배열로 버블 정렬을 이용하여 정렬해보자.

초기의 배열 상태

① 먼저 첫 번째 원소와 두 번째 원소를 비교한 후 큰 값을 뒤에 위치로 옮겨준다. 30과 50을 비교하였을 때 50이 더 크기 때문에 위치를 변경하지 않는다. 그 이후 두 번째 원소와 세 번째 원소를 비교한다. 50과 20을 비교하였을 때 두 번째 원소가 더 크기 때문에 세 번째 원소와 서로 위치를 변경한다.

30과 50을 비교하였을 때 뒤의 원소가 큰 값이기 때문에 위치를 교환 하지 않음

다음 위치로 이동하여 50과 20을 비교하여 뒤의 원소가 작기 때문에 위치를 교환함 

② 위의 과정을 마지막 원소까지 진행하다 보면 아래와 같은 결괏값을 얻을 수 있다.

세 번째 원소와 네 번째 원소의 비교 후 교환

네 번째 원소와 마지막 원소의 비교 후 교환

1회전 결과

③ ① ~ ②번의 과정을 정렬이 완료된 원소 전까지 순회한다.

2회전 결과

3회전 결과

④ 위의 과정을 계속 진행하다 보면 최종적으로 아래와 같은 정렬된 결과를 얻을 수 있다.

버블 정렬 결과

이제 코드로 버블 정렬을 구현해보자.

 

#include <iostream>
 
using namespace std;
 
// 원소 개수
#define MAX_LENGTH 5
 
int main()
{
    // 정렬할 배열 선언
    int arr[MAX_LENGTH] = { 30, 50, 20, 10, 40 };
 
    // 원소의 개수만큼 순회
    for (int i = 0; i < MAX_LENGTH; ++i)
    {
        // 정렬이 완료된 원소 전까지 순회
        for (int j = 0; j < MAX_LENGTH - i - 1; ++j)
        {
            // 두 원소를 비교하여 뒤의 원소가 더 작을 경우
            if (arr[j] > arr[j + 1])
            {
                // 원소 교환
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
 
    // 출력 결과 확인
    for (int i = 0; i < MAX_LENGTH; ++i)
    {
        cout << arr[i] << endl;
    }
}