73 배열 정렬하기
프로그래밍을 하다 보면 수많은 값들을 처리하게 됩니다. 보통 특별한 순서 없이 섞여있는 값들은 오름차순이나 내림차순으로 정렬해야 할 경우가 많습니다. 특히 정렬은 매우 중요한 문제라서 정렬을 빠르고 효율적으로 처리하기 위한 알고리즘들이 다양하게 나와있습니다.
이번에는 정렬 알고리즘 중에서 가장 간단한 알고리즘인 거품 정렬(bubble sort)을 구현해보고, C 언어에서 제공하는 퀵 정렬(quick sort) 함수 사용 방법을 알아보겠습니다.
1부터 10까지의 숫자가 무작위로 들어있는 배열을 거품 정렬 알고리즘으로 정렬해보겠습니다. 다음 내용을 소스 코드 편집 창에 입력한 뒤 실행해보세요.
bubble_sort.c
#include <stdio.h>
void bubble_sort(int arr[], int count) // 매개변수로 정렬할 배열과 요소의 개수를 받음
{
int temp;
for (int i = 0; i < count; i++) // 요소의 개수만큼 반복
{
for (int j = 0; j < count - 1; j++) // 요소의 개수 - 1만큼 반복
{
if (arr[j] > arr[j + 1]) // 현재 요소의 값과 다음 요소의 값을 비교하여
{ // 큰 값을
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp; // 다음 요소로 보냄
}
}
}
}
int main()
{
int numArr[10] = { 8, 4, 2, 5, 3, 7, 10, 1, 6, 9 }; // 정렬되지 않은 배열
bubble_sort(numArr, sizeof(numArr) / sizeof(int)); // 거품 정렬 함수 호출
for (int i = 0; i < 10; i++)
{
printf("%d ", numArr[i]); // 1 2 3 4 5 6 7 8 9 10
}
printf("\n");
return 0;
}
Plain Text
복사
실행 결과
1 2 3 4 5 6 7 8 9 10
Plain Text
복사
거품 정렬 알고리즘의 규칙은 다음과 같습니다.
•
처음부터 끝까지 요소를 순회하면서 모든 요소를 비교
•
현재 값과 다음 값을 비교하여 큰 값을 다음으로 보냄(오름차순)
이제 bubble_sort 함수를 살펴보겠습니다. bubble_sort 함수는 int arr[]과 같이 정렬할 배열을 매개변수로 받습니다. 또한, 매개변수 arr[]로는 요소의 개수를 모르니 요소의 개수도 함께 받습니다.
void bubble_sort(int arr[], int count) // 매개변수로 정렬할 배열과 요소의 개수를 받음
Plain Text
복사
for 반복문으로 배열을 처음부터 끝까지 순회합니다. 이때 요소 하나를 반복할 때마다 다시 처음부터 끝 - 1까지, 즉, 0부터 count - 1까지 반복합니다. 여기서 -1을 하는 이유는 현재 값과 다음 값을 비교할 때 맨 마지막 요소는 배열의 인덱스를 벗어난 값과 비교하게 됩니다. 따라서 배열의 인덱스를 벗어나지 않도록 마지막 요소의 바로 앞에서 반복을 끝냅니다.
for (int i = 0; i < count; i++) // 요소의 개수만큼 반복
{
for (int j = 0; j <count - 1; j++) // 요소의 개수 - 1만큼 반복
{
Plain Text
복사
현재값 arr[j]와 그다음에 있는 값 arr[j + 1]을 비교하여 큰 값을 다음 요소로 보냅니다. 즉, 작은 값이 먼저 오는 오름차순(ascending) 정렬입니다. 부등호를 반대로 해주면 내림차순(descending)이 되겠죠? 여기서 큰 값을 다음 요소로 보낼 때는 기존 값을 임시 변수 temp에 저장해놓고 다음 요소에 있는 값을 가져온 뒤 temp의 값을 다음 요소에 저장해서 값을 서로 바꿉니다. 이를 자리 바꾸기(swap)라 합니다.
if (arr[j] > arr[j + 1]) // 현재 요소의 값과 다음 요소의 값을 비교하여
{ // 큰 값을
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp; // 다음 요소로 보냄
}
Plain Text
복사
▼ 그림 73‑1 거품 정렬의 과정
이제 정렬되지 않은 배열 numArr을 bubble_sort 함수에 넣은 뒤 printf로 각 요소를 출력해보면 배열이 1부터 10까지 순서대로 정렬된 것을 볼 수 있습니다.
int main()
{
int numArr[10] = { 8, 4, 2, 5, 3, 7, 10, 1, 6, 9 }; // 정렬되지 않은 배열
bubble_sort(numArr, sizeof(numArr) / sizeof(int)); // 거품 정렬 함수 호출
for (int i = 0; i < 10; i++)
{
printf("%d ", numArr[i]); // 1 2 3 4 5 6 7 8 9 10
}
printf("\n");
return 0;
}
Plain Text
복사
여기서 설명한 거품 정렬은 이해를 돕기 위해 최적화를 하지 않고 간단하게 구현했습니다. 좀 더 효율적으로 정렬하려면 이미 정렬된 맨 마지막 원소는 건너뛰어도 됩니다. 여러분들이 한 번 최적화해서 구현해보기 바랍니다.
거품 정렬은 요소 개수 * 요소 개수(n2)로 비교하기 때문에 효율이 좋지 않습니다. 정렬 알고리즘은 여러 개가 있는데 그 중에서 퀵 정렬이 효율이 좋아서 널리 쓰이며 C 언어 표준 함수에도 포함되어 있습니다.