O(n^2) 정렬 - 버블정렬(Bubble Sort)

시간복잡도 O(n^2)의 버블정렬입니다.

 

배열을 n바퀴 순회하며 인접한 인덱스의 배열 값끼리 비교연산(최대 n번) Swap함으로써 정렬을 실행합니다.

 

#include<iostream>
using namespace std;
 
#define MAX 500
int ar[MAX];
 
void Swap(int a, int b)
{
    ar[a] = ar[a] + ar[b];
    ar[b] = ar[a] - ar[b];
    ar[a] = ar[a] - ar[b];
}
 
void BubbleSort(int size)
{
    for (int i = 0; i < size - 1; i++)
    {
        for (int j = 0; j < size - 1; j++)
        {
            if (ar[j] > ar[j + 1])
            {
                Swap(j, j + 1);
            }
        }
    }
}
 
int main()
{
    int n; cin >> n;
 
    for (int j = 0; j < n; j++)
    {
        cin >> ar[j];
    }
    BubbleSort(n);
    for (int j = 0; j < n; j++)
    {
        cout << ar[j] << ' ';
    }
}