버블 정렬이란 ?
거품이 올라오듯 천천히 자료가 올라오며 정렬되는 알고리즘이다.
버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.1회 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.
이처럼 버블 정렬은 최악, 평균 ,최상의 경우 항상 똑같은 T(n)을 가진다.
그리고 위 알고리즘 설명처럼 진행되기에 버블 정렬은 Θ(n2)의 T(n)을 가진다.
버블 정렬 구현
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <malloc.h>
void swap(int* arr, int a, int b) {
int tmp;
tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
void BubbleSort(int* arr, int n) {
//하나가 선택되어서 계속 올라가는게 아니라 두개씩 비교하다 보면 가장 큰 수가 오른쪽으로 가게 됨
for (int i = n - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
int main() {
srand((unsigned int)time(NULL));
int n;
scanf_s("%d", &n);
int* arr = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++) {
arr[i] = rand() / (double)RAND_MAX * 1000;
printf("%d ", arr[i]);
}
printf("\n");
BubbleSort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
}
일반 버블 정렬의 코드를 짜본 것이다.
2회 반복문을 들어와 연산을 할 때마다 count를 해주어 연산 횟수를 기록해보았다.
10개의 데이터를 입력하고
몇 번을 실행하든 최악, 평균, 최상의 상황에 관계 없이 45번의 비교 연산 횟수가 기록이 되었다.
버블 정렬의 고도화
임의 loop에서 남은 원소들이 모두 정렬되어 있다면?
버블 정렬은 언제나 수행 횟수가 같기 때문에 다 정렬이 되었는데도 불구하고 계속해서 비교 연산을 하게 된다.
정렬이 다 되었다면 연산을 멈추고 필요 없는 연산을 멈출 수 있는 방법이 없을까 ?
버블 정렬을 고도화 시키는 방법에 대해 조사하고 그 수행시간 분석
방법은 1회 반복문에서 임의에 변수에 true값으로 초기화를 해놓고 한번이라도 2회 반복문에서 if문을 들어와 연산이 수행된다면(정렬이 덜 된 상태) false값을 대입해 1회 for문에서 if문을 들어가 break되지 않게 하는 방법이다. 반대로 2회 반복문에서 한번도 연산이 수행되지 않는다면(정렬이 다 되어있는 상태) true 값을 그대로 받아 break가 있는 1회 반복문의 if문으로 들어가 정렬을 종료하는 방법이다.
그렇게 되면 최상의 경우(정렬이 다 되어있는 경우) Θ(n)의 수행시간을 갖게 된다.
여전히 평균, 최악의 경우 수행시간은 Θ(n2)이지만 매번 상한을 넘지 않는 선에서 수행 횟수가 계속 바뀌기 때문에 전보다 훨씬 효율적인 알고리즘이 될 수 있는 것이다.
그리고 최상의 경우 Θ(n)을 포함하는 알고리즘이 되기 때문에
T(n) = O(n2) 이라고 정의할 수 있다.
버블 정렬의 고도화 구현
이처럼 버블 정렬을 고도화 시켜준다면 10개의 데이터를 넣어 주었을 때 45번의 횟수를 넘지 않는 범위에서 수행 횟수가 결정된다.
10번 정도 실행한 결과 최소:18, 최대:32에 실행 횟수가 나왔다.
상한을 넘지 않는 선에서 필요 없는 연산을 줄인 전보다 더 효율적인 알고리즘이 된 것이다.
