버블 정렬 (bubble sort) c++
무작위로 값이 들어있는 배열값을 오름차순 혹은 내림차순으로 정렬 하는 알고리즘이다. 가장 가까운 2개의 요소를 비교해 나가면서 마지막 위치까지 도달하면 이제 마지막 위치에는 정렬된 값이 들어간다.
이후 다시 처음으로 돌아가 반복하는데 반복할때마다 정렬된 위치전까지만 도달하면된다.
이 요소들이 움직이는 과정이 마치 버블이 움직이는 것 처럼 보여서 그렇게 지어진 이름이라 한다(이해안감)
{5,4,3,2,1} 배열이 있을때 버블 정렬 알고리즘을 통해 오름차순으로 정렬하는 과정이다. 긴 설명보다 한 번의 예시가 더 도움이 된다.
1번째 패스 (전체 5개의 요소 비교)
- 5와 4를 비교: 5 > 4이므로 교환 → [4, 5, 3, 2, 1]
- 5와 3을 비교: 5 > 3이므로 교환 → [4, 3, 5, 2, 1]
- 5와 2를 비교: 5 > 2이므로 교환 → [4, 3, 2, 5, 1]
- 5와 1을 비교: 5 > 1이므로 교환 → [4, 3, 2, 1, 5]
2번째 패스 (마지막 요소는 이미 정렬됨, 4개의 요소 비교)
- 4와 3을 비교: 4 > 3이므로 교환 → [3, 4, 2, 1, 5]
- 4와 2를 비교: 4 > 2이므로 교환 → [3, 2, 4, 1, 5]
- 4와 1을 비교: 4 > 1이므로 교환 → [3, 2, 1, 4, 5]
3번째 패스 (마지막 두 요소는 이미 정렬됨, 3개의 요소 비교)
- 3과 2를 비교: 3 > 2이므로 교환 → [2, 3, 1, 4, 5]
- 3과 1을 비교: 3 > 1이므로 교환 → [2, 1, 3, 4, 5]
4번째 패스 (마지막 세 요소는 이미 정렬됨, 2개의 요소 비교)
- 2와 1을 비교: 2 > 1이므로 교환 → [1, 2, 3, 4, 5]
5번째 패스 (모든 요소가 정렬됨, 비교할 필요 없음)
배열의 길이가 n인 버블 정렬의 시간 복잡도는 O(n²)이다. 로직이 간단하지만 상대적으로 느리다.
여기서 나는 궁금증이 생겼다. 위에서는 배열의 길이가 5일때 최대 10번 비교를 통해 정렬을하는데, O(n²)이 되려면 5의 제곱인 25번 비교를 해야 하는게 아닌가? 그래서 좀 알아보았더니 이러한 사실을 알게 되었다.
시간 복잡도의 O(n²)의 개념은 실제로 제곱을 말하는게 아니라, n의 크기가 커질수록 급격하게 반복횟수가 늘어난다는 의미이다. 예시를 보면 알 수 있다.
- 배열 길이가 5일 때: 5×5=25 에 비례하는 작업이 발생 (실제로는 10번 비교)
- 배열 길이가 10일 때: 10×10=100 에 비례하는 작업 발생 (실제로는 45번 비교)
즉, 시간 복잡도는 n²에 비례한다고 해서 O(n²) 라고 말한다.
아래는 버블 정렬를 C++로 구현한 내용이다.
#include<iostream>
using namespace std;
int arr[5] = { 5,3,1,2,4 };
int main()
{
int temp = 0;
int size = 5;
for (int i = 0; i < 5; i++)
{
cout << arr[i] << ", ";
}
cout << "\n--------------\n";
while (size > 0)
{
for (int i = 0; i < size - 1; i++)
{
if (arr[i] > arr[i + 1])
{
temp = arr[i + 1];
arr[i + 1] = arr[i];
arr[i] = temp;
}
}
size--;
}
for (int i = 0; i < 5; i++)
{
cout << arr[i] << ", ";
}
}
while (size > 0)
{
for (int i = 0; i < size - 1; i++)
{
if (arr[i] > arr[i + 1])
{
temp = arr[i + 1];
arr[i + 1] = arr[i];
arr[i] = temp;
}
}
size--;
}위 부분만 잘 보면 된다. temp라는 변수를 통해 요소를 바꿀때 값을 잃어 버리지 않도록 잠깐 가지고 있는 역할을 한다.
한 싸이클이 지나면 size를 -1 시켜 정렬되지 않는 요소까지만 비교하도록 한다.