버블 정렬 (거품정렬) Bubble Sort

정렬정리

버블정렬은 구현하기 매우쉽고 이해하기도 가장쉽다

하지만 시간복잡도가 평균과 최악의경우 O(n^2)로 크기때문에 개수가 몇개안될때만 사용가능하다.

정렬해야할 원소의 개수가많아진다면 퀵소트나 병합정렬을 이용하는게 더  나을수 있다.

10만개의 배열을 랜덤하게 생성후 정렬한 결과.

#include<iostream>
#include <time.h>
using namespace std;
#define MAX 100000
 
void bubble(int *arr, int right);
int arr[MAX];
int main(void)
{
 
    for (int i = 0; i < MAX; i++)
    {
        arr[i] = rand();
    }
    double now = clock();
    bubble(arr, MAX);
    double finish = clock();
 
    for (int i = 0; i < MAX; i++)
        cout << arr[i] << " ";
 
    cout << endl << "버블정렬 " << MAX << "개 소요시간 : " << finish - now << "ms" << endl;
 
    return 0;
}
 
void bubble(int *arr, int right)
{
    for (int i = 0; i < right-1; i++)
    {
        for (int j = 0; j < right -i -1; j++)
        {
            if (arr[j]>arr[j + 1])
            {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}