[Algorithm] C++ Bubble Sort (거품정렬)
거품정렬
- 두개의 인접한 원소를 비교하는 정렬이다.
- 선택정렬과 유사하나, 다른점은 앞에서부터 차례로 정렬하기때문에 '안정정렬' 이라고도 한다.
- 정렬 방식중 가장 간단하며 쉬우나, 다른 정렬보다 원소의 교환이 많아, 소요되는 시간이 길다.
원소들의 정렬과정에서 원소의 이동이 거품처럼 수면위로 올라온다는 뜻으로 거품 정렬이라는 이름이 붙기도하였다.
거품정렬 알고리즘
- 앞에서부터 현재 원소와 바로 다음 원소를 비교한다.
- 현재 원소가 바로 다음의 원소보다 클 경우 교환한다. (오름차순 기준)
- 그 이후 바로 다음 원소로 이동하여, 해당 원소와 다음 원소를 비교한다.
예시
원소들 정렬 흐름은 아래 gif 파일로 확인할 수 있다.
거품정렬 특징
- 추가적인 메모리 소비가 적다.
- 구현이 매우 간단하다.
- 안정정렬이 가능하다.
- 다른 정렬과는 다르게 교환 횟수가 많아 소비 시간이 크다. 그래서 실제로 많이 사용하지 않는 정렬이다.
시간복잡도
거품 정렬의 평균 시간 복잡도는 O(n^2)의 시간 복잡도를 갖는다.
- 비교 횟수
- 두개의 for루프의 실행 횟수
- 외부 루프 : (n - 1) 번
- 내부 루프 : n-1, n-2, n-3 .... 2, 1번 (최솟값 찾기)
일반화 시킨 공식은 다음과 같다.
즉, T(N) 시간복잡도 또한 도출이 가능하다.
관련 알고리즘 문제
https://www.acmicpc.net/problem/1838
1838번: 버블 정렬
버블 정렬이란 배열에서 서로 인접해 있는 값을 비교해서 작은 값이 더 뒤에 있을 때 두 값을 바꾸어 주는 과정을 계속 반복하는 정렬 방법이다. N개의 서로 다른 정수가 A[0], A[1], ..., A[N-1]의 정
www.acmicpc.net
https://www.acmicpc.net/problem/2750
2750번: 수 정렬하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
Code
이미 정렬이 된 원소의 집합이여도, 그 이후 원소들까지 전부 정렬을 하기 때문에 시간복잡도가 O(n^2)가 되지만,
O(n)까지 개선시킬 수 있다.
우선 아래 코드는 일반적인 거품 정렬이다.
#include <iostream>
using namespace std;
int main() {
int arr[] = { 54, 26, 93, 17, 77, 31, 44, 55, 20 };
int arrSize = 9;
for (int i = 0; i < arrSize - 1; i++) {
for (int j = 0; j < arrSize - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
for (int a = 0; a < arrSize; a++)
cout << arr[a] << ' ';
cout << i + 1 << " Exchange\n";
}
}해당 원소와 다음 원소를 비교하였을때, 교환이 이루어지는 해당 반복문 내에서 원소가 교환되지 않는다면,
즉, swap이 발생하지 않는다면 이미 정렬된 데이터로 가정하고, 종료할 수 있다.
이 경우 Best Case로 시간복잡도가 O(n) 가 될 수 있다.
아래 코드를 한번 살펴 보자.
#include <iostream>
using namespace std;
int main() {
/* Worst Case
int arr[] = { 54, 26, 93, 17, 77, 31, 44, 55, 20 };
int arrSize = 9;
for (int i = 0; i < arrSize - 1; i++) {
for (int j = 0; j < arrSize - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
for (int a = 0; a < arrSize; a++)
cout << arr[a] << ' ';
cout << i + 1 << " Exchange\n";
}
*/
/* Best Case*/
int arr[] = { 54, 26, 93, 17, 77, 31, 44, 55, 20 };
int arrSize = 9;
for (int i = 0; i < arrSize - 1; i++) {
bool isSwap = false;
for (int j = 0; j < arrSize - 1 - i; j++) {
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
isSwap = true;
}
}
if (isSwap == false)
break;
for (int a = 0; a < arrSize; a++)
cout << arr[a] << ' ';
cout << i + 1 << " Exchange\n";
}
}
이 경우, 교환이 이미 이루어져 있거나, 정렬이 된 경우 바로 종료 하게 된다.