[알고리즘] 버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)

특징

1. 안정 정렬(Stable Sort): 동일한 값에 대해 상대적인 순서가 유지됩니다. 즉, 동일한 값의 원소들은 입력 배열에서의 순서와 동일한 순서로 정렬됩니다.
2. 제자리 정렬(In-place Sort): 입력 배열 이외에 추가적인 메모리를 사용하지 않습니다. 입력 배열 내에서 정렬이 수행됩니다.
3. 비교 기반 정렬(Comparison Sort): 원소들의 상대적인 크기를 비교하여 정렬합니다.

알고리즘 동작 방식

버블 정렬은 인접한 원소들을 비교하고 필요에 따라 위치를 교환하는 과정을 반복하여 전체 배열이 정렬될 때까지 진행합니다.

1. 첫 번째 원소부터 인접한 원소와 비교합니다.
2. 인접한 두 원소의 순서가 잘못되어 있다면, 두 원소의 위치를 교환합니다.
3. 배열의 끝까지 위의 과정을 반복하면, 가장 큰 원소가 배열의 마지막 위치로 이동합니다.
4. 정렬된 부분을 제외하고 나머지 부분에 대해서도 위의 과정을 반복합니다.

장점

1. 구현이 매우 간단하고 이해하기 쉽습니다.
2. 작은 규모의 입력에 대해서는 효율적입니다.
3. 제자리 정렬이므로 메모리 사용량이 작습니다.

단점

1. 평균 및 최악의 경우에 대해 O(n^2)의 시간 복잡도를 가집니다. 배열의 모든 인접한 원소들을 비교하고 교환하는 과정을 반복하기 때문에 비효율적입니다.
2. 대량의 데이터를 정렬할 때는 다른 알고리즘들보다 성능이 떨어질 수 있습니다.
3. 안정성은 유지되지만, 입력 배열이 이미 거의 정렬되어 있는 경우에도 모든 비교 및 교환 과정을 수행해야 하므로 효율적이지 않습니다.

요약

버블 정렬은 구현이 간단하고 작은 입력에 대해서는 효율적인 정렬 알고리즘입니다.

그러나 대량의 데이터에 대해서는 다른 알고리즘들보다 성능이 떨어지며, 최악의 경우에는 시간 복잡도가 O(n^2)이기 때문에 효율적인 알고리즘이라고는 할 수 없습니다.

https://velog.io/@kich555/Algorithm-Bubble-Sort

void DoBubbleSort()
{
	vector<int> arr;
	arr.assign(rand() % 30, int());

	for (auto& num : arr)
		num = rand() % 100;

	cout << "Before Sort" << endl;

	for (auto num : arr)
		cout << num << " ";

	cout << endll << "After Sort" << endl;

	BubbleSort(arr);
	for (auto num : arr)
		cout << num << " ";

	cout << endll;

	Pause;
	return;
}

void BubbleSort(vector<int>& arr)
{
	for (int i = arr.size() - 1; i > 0; i--)
		for (int j = 0; j < i; j++)
			if (arr[j] < arr[j + 1])
				swap(arr[j], arr[j + 1]);
}

기본코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <unordered_map>
#include <fstream>
#include <ostream>
#include <sstream>
#include <cctype>
#include <cmath>

#define fastio cin.tie(0)->ios::sync_with_stdio(0); cout.tie(0);
using namespace std;

int main() 
{
    fastio;
    
    int i, j, temp;
    int array[10] = { 1,10,5,8,7,6,4,3,2,9 };
    for (int i = 0; i < 10; i++)
    {
        for (j = 0; j < 9 - i; j++)
        {
            if (array[j] > array[j+1])
            {
                swap(array[j], array[j+1]);
            }
        }
    }
    for (i = 0; i < 10; i++)
    {
        cout << array[i] <<" ";
    }
    return 0;
}