[정렬 알고리즘]Bubble Sorting - 버블정렬

버블정렬은 인접한 자료 2개를 비교하여 정렬해가는 정렬 알고리즘입니다. 버블정렬은 정렬될때 데이터들이 움직이는 모습이 거품이 올라오는거 같다고 하여 버블 정렬이라 하며 시간복잡도는 BigO(n^2)인 알고리즘입니다.

버블 정렬은 다음과 같은 과정을 거치게 됩니다.

1. 제일 왼쪽부터 값을 비교하여 왼쪽이 큰 경우 오른쪽의 값과 교체합니다
   
   
2. 모든 자료들에 대하여 전부 수행반복합니다(1pass)
   
   
3. 정렬이 끝날때 까지 1,2번을 반복 수행합니다.

또한 버블정렬에서는 최적과 과정을 통해서 두가지 경우의 낭비를 방지합니다.

1. 자료가 정렬이 되어있는 경우엔 정렬을 끝낸다.
   
   자료가 정렬되어있는 경우에 할 필요없는 비교를 전체적으로 수행하기 떄문에 1pass동안에 어떠한 변경이 없다면 정렬이 되었음을 확인하고 종료합니다.
   
   
2. 정렬된 데이터에 대해서는 비교하지 않는다.
   
   1pass가 지난후에 가장 가장 마지막의 데이터는 정렬된 데이터이기 때문에 매 pass마다 이를 제외하고 비교합니다.
   
   

버블정렬을 애니메이션은 다음과 같이 나타나게 됩니다.(거품이 올라가는거 같나요?)

버블정렬은 프로그래밍으로 다음과 같이 나타낼 수 있습니다.

#include<iostream>
void Print(int TargetArray[], int Length)                        //출력을 위한 함수
{
    for (int i = 0; i < Length; i++)
        std::cout << TargetArray[i] << " ";
    std::cout << std::endl;
}
 
void Swap(int *Target_Left, int *Target_Right)                    //값 교체를 위한 함수
{
    int Temp;
    Temp = *Target_Right;
    *Target_Right = *Target_Left;
    *Target_Left = Temp;
}
 
void BubbleSort(int TargetArray[],int Length)                    //버블 정렬 함수
{
    bool Change = false;                                        //최적화용 변수
    for (int pass = 0; pass <= Length+1; pass++)                //1pass
    {
        for (int i = 0; i < Length-pass-1; i++)                    //(제일 끝엔 정렬이 된 숫자가 들어감 - 최적화)
        {
            if (TargetArray[i] > TargetArray[i + 1])
            {
                Swap(&TargetArray[i], &TargetArray[i + 1]);
                Change = true;
            }
            Print(TargetArray, Length);
        }
        if (Change == false)                                    //값 교체가 없으면 정렬이 끝난걸로 간주한다(최적화)
            return;
    }
}
 
void main()
{
    int Array[5] = { 9,7,5,3,1 };
    BubbleSort(Array, 5);
    std::cout << "최종 결과 : ";
    Print(Array, 5);
}

결과는 다음과 같습니다.