이번에는 반복적인 방법으로 해결하는 버블 정렬 알고리즘을 살펴봅시다.
정렬 알고리즘은 배열의 자료를 원하는 순으로 배치하는 것을 말합니다. 이를 위해 입력 인자로 정렬할 자료들이 있는 배열의 시작 주소와 원소 개수, 비교 알고리즘을 전달합니다. 그리고 수행 후에는 배열 내의 자료들이 원하는 순서로 보관한 상태여야 합니다.
이 중에 버블 정렬은 앞에서부터 이웃하는 원소의 값을 비교하여 위치를 교환하는 것을 반복합니다. 이를 끝까지 수행하면 제일 큰 값이 맨 뒤에 위치합니다. 그리고 정렬할 개수를 1 줄인 후에 다시 반복합니다. 정렬할 원소의 개수가 1이면 모든 작업을 완료합니다.
알고리즘
버블 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
반복(i:=n; i>1 ; i:= i-1)
반복(j:=1; j<i ; j:=j+1)
조건(compare(base[j-1], base[j]) > 0)
교환(base[j-1],base[j])
점근식 계산
이번에는 거품 정렬 알고리즘 성능을 분석합시다.
거품 정렬의 내부 반복문의 수행 시간을 S(i)라고 가정할게요. 내부 반복문은 j가 1에서 i이전까지 순차적으로 증가하므로 비교를 i-1번, 교환을 최악일 때 i-1번 한다고 볼 수 있어요. 따라서 S(i)= i-1이죠.
외부 반복문은 i가 n에서 1로 역순으로 감소하면서 내부 반복문을 수행합니다. 수행 시간을 T(n)이라 가정하면 T(n) = S(n) + S(n-1) + S(n-2) + … +1 이죠.
따라서 T(n) = S(n) + S(n-1) + … +S(2) + S(1) = n-1 + n-2 + …. + 1 + 0
따라서 T(n)= n(n-1)/2 이고 점근식 표기에서 높은 차수의 항만 남고 상수를 버리므로 O(n^2)라고 할 수 있습니다. 거품 정렬도 순차 정렬처럼 O(n^2)이네요.
소스 코드
//버블 정렬(Bubble Sort)
#include <stdio.h>
#define SWAP(a,b) {int t; t = a; a=b; b=t;}//a와 b를 교환
void BubbleSort(int *base, int n);
int main(void)
{
int arr[10] = { 9,4,3,10,5,8,7,6,2,1 };
BubbleSort(arr, 10);
return 0;
}
void ViewArr(int *arr, int n);
void BubbleSort(int *base, int n)
{
int i, j;
ViewArr(base, n);//현재 상태 출력
for (i = n; i>1; i--)//정렬할 범위를 축소해 나갑니다.
{
for (j = 1; j<i; j++)
{
if (base[j - 1]>base[j])//앞쪽 원소가 더 크면
{
SWAP(base[j - 1], base[j]);//교환
ViewArr(base, n);//상태 출력
}
}
}
}
void ViewArr(int *arr, int n)
{
int i = 0;
for (i = 0; i<n; i++)
{
printf("%2d ", arr[i]);
}
printf("\n");
}
다음은 시뮬레이션 형태로 버블 정렬 알고리즘이 동작하는 과정을 표시하는 소스 코드입니다.
//https://ehpub.co.kr
//[언제나 C언어] 거품 정렬(Bubble Sort) [예제 Center]
#pragma warning(disable:4996)
#include
#include
#include
#define LENGTH(arr) (sizeof(arr)/sizeof(arr[0]))
#define SWAP(i, j) {int t; t=i; i=j; j=t;}
#include //Sleep
enum Color
{
LACK, BLUE, GREEN, JADE, RED, PURPLE, YELLOW, WHITE, GRAY,
LIGHT_BLUE, LIGHT_GREEN, LIGHT_JADE, LIGHT_RED, LIGHT_PURPLE, LIGHT_YELLOW, LIGHT_WHITE
};
void gotoxy(int x, int y)
{
COORD Pos = { x,y };
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), Pos);
}
void changecolor(int color)
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), color);
}
void ViewSimInfo()
{
printf("\n\n==");
changecolor(YELLOW);
printf("[ j-1 ] ");
changecolor(GREEN);
printf("[ j ] ");
changecolor(PURPLE);
printf("[정렬 완료] ");
changecolor(WHITE);
printf("[기타]==\n");
printf("\n");
}
void ViewArr2(int *base, int i, int j, int n, int r)
{
int s = 0;
for (s = 0; s < n; s++)
{
if (s < j-1)
{
changecolor(WHITE);
}
else if (s == j - 1)
{
changecolor(YELLOW);
}
else if (s == j)
{
changecolor(RED);
}
else if (s < i)
{
changecolor(WHITE);
}
else if (s >= i)
{
changecolor(PURPLE);
}
printf("%2d ", base[s]);
}
changecolor(WHITE);
if (r)
{
printf(" SWAP %d %d", base[j-1], base[j]);
}
printf("\n");
}
void BubbleSort2(int *base, int n)
{
int i, j;
for (i = n; i > 1; i--)
{
for (j = 1; j < i; j++)
{
if (base[j - 1] > base[j])
{
ViewArr2(base, i, j, n, 1);
SWAP(base[j - 1], base[j]);
//getch();
}
ViewArr2(base, i, j, n, 0);
Sleep(1000);
//getch();
}
}
}
void ViewArr(int *base, int n, const char *msg)
{
int i = 0;
for (i = 0; i < n; i++)
{
printf("%2d ", base[i]);
}
puts(msg);
}
void BubbleSort(int *base, int n)
{
int i, j;
for (i = n; i >1 ; i--)
{
for (j = 1; j < i; j++)
{
if (base[j-1] > base[j])
{
SWAP(base[j-1], base[j]);
}
}
}
}
int main(void)
{
int arr[10] = { 9,4,3,0,5,8,7,6,2,1 };
ViewSimInfo();
ViewArr(arr, LENGTH(arr), "before");
getch();
//BubbleSort(arr, LENGTH(arr));
BubbleSort2(arr, LENGTH(arr));
ViewArr(arr, LENGTH(arr), "after");
system("pause");
return 0;
}