원리
버블 정렬(Bubble Search)는 직관적인 알고리즘이다.
정렬 원리는 다음과 같다.
버블 정렬은 선택 정렬과 동일하게 이중 반복문을 통해 완전 탐색을 수행한다.
따라서 시간 복잡도는 O(n^2)에 해당한다.
(선택 정렬과 차이점은 Swap 횟수로, 버블 정렬이 좀 더 Swap이 자주 일어남)
비효율적인 정렬 방법으로, 작은 크기일 때 사용한다.
코드
#include <iostream>
#include <vector>
using namespace std;
void swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}
void bubble_sort(vector<int>& arr)
{
int min_idx;
for (int i = 0; i < arr.size(); i++)
{
min_idx = i;
for (int j = i + 1; j < arr.size(); j++)
{
if (arr[min_idx] > arr[j])
min_idx = j;
}
swap(arr[i], arr[min_idx]);
}
}
int main()
{
vector<int> arr = { 7, 2, 5, 4, 1, 3, 9, 8, 6, 10 };
bubble_sort(arr);
for (auto n : arr)
cout << n << '\n';
return 0;
}
'IT > 알고리즘' 카테고리의 다른 글
[C++] 머지 정렬 (Merge Sort) (1) | 2023.10.22 |
---|---|
[C++] 퀵 정렬 (Quick Sort) (0) | 2023.10.22 |
[C++] 선택 정렬 (Selection Sort) (0) | 2023.10.22 |
[C++] 문자열 처리 (1) | 2023.10.04 |
[C++] Map Container (0) | 2023.09.10 |