버블 정렬 구현하기

자료구조 복습 삼아 버블 정렬을 C로 구현해 보았다.

전체 코드

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAX_VALUE 10
void bubble_sort(int arr[], int size);
void swap(int* a, int* b);
int* generate_random_arr(int size);
void print_arr(int arr[], int size);

int main(void)
{
	srand((unsigned)time(NULL));
	const int SIZE = 10;
	int* arr = generate_random_arr(SIZE);
	print_arr(arr, SIZE);

	bubble_sort(arr, SIZE);
	print_arr(arr, SIZE);

}

void bubble_sort(int arr[], int size)
{
	for (int i = size - 1; i > 0; i--) {
		for (int j = 0; j < i; j++)
			if (arr[j] > arr[j + 1])
				swap(&arr[j], &arr[j + 1]);
	}
}

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int* generate_random_arr(int size)
{
	int* arr = (int*)malloc(sizeof(int) * size);
	if (arr == NULL) return NULL;

	for (int i = 0; i < size; i++)
		arr[i] = rand() % MAX_VALUE + 1;
	return arr;
}

void print_arr(int arr[], int size)
{
	for (int i = 0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

설명

void bubble_sort(int arr[], int size);

주어진 배열에 대해 버블 정렬을 수행하는 함수이다.

void bubble_sort(int arr[], int size)
{
	for (int i = size - 1; i > 0; i--) {
		for (int j = 0; j < i; j++)
			if (arr[j] > arr[j + 1])
				swap(&arr[j], &arr[j + 1]);
	}
}

반복문을 두 번 사용한다. 코드에서 알 수 있는 것처럼 빅오 표기법으로 시간 복잡도를 나타내면 O(n^2)이다.

void swap(int* a, int* b);

두 수의 위치를 바꾸어 저장하는 함수이다.

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

거의 포인터 처음 배울 때 예제로 나올 것 같은 함수이다.
파이썬은 a, b = b, a로 했었던 것 같은데 이런건 역시 파이썬이 편하다.

int* generate_random_arr(int size);

랜덤 배열을 생성하여 포인터를 반환하는 함수이다. 동적으로 생성하여 랜덤 값을 넣는다.

int* generate_random_arr(int size)
{
	int* arr = (int*)malloc(sizeof(int) * size);
	if (arr == NULL) return NULL;

	for (int i = 0; i < size; i++)
		arr[i] = rand() % MAX_VALUE + 1;
	return arr;
}

1부터 MAX_VALUE까지의 범위에서 랜덤으로 수를 생성하여 배열의 요소로 저장한다. 테스트할 때 일일이 정렬할 배열을 초기화하지 않아도 된다.

void print_arr(int arr[], int size);

배열의 모든 요소를 출력하는 함수

void print_arr(int arr[], int size)
{
	for (int i = 0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

실행 결과

버블 정렬 최적화

버블 정렬을 조금 개선시킬 수 있다.

버블 정렬은 주어진 배열이 정렬이 되어 있는지 아닌지에 관계 없이 O(n^)의 시간 복잡도를 갖는다.

두 개의 반복문 중 안쪽의 반복문에서 스왑이 발생하지 않으면 정렬이 이미 된 배열이므로 반복문을 중단함으로써 버블 정렬을 개선시킬 수 있다.

개선된 bubble_sort 함수

#define TRUE 1
#define FALSE 0
void bubble_sort(int arr[], int size)
{
	int swapped;
	for (int i = size - 1; i > 0; i--) {
		swapped = FALSE;
		for (int j = 0; j < i; j++) {
			if (arr[j] > arr[j + 1]) {
				swap(&arr[j], &arr[j + 1]);
				swapped = TRUE;
			}
		}

		if (swapped == FALSE) break;
	}
}