문제 상황
C 언어에서 정렬은 왜 검색을 더 쉽게 만들어 줄까요? 그리고 정렬 알고리즘의 효율성은 어떤 기준으로 판단할 수 있을까요?
정렬이란 무엇인가?
정렬(Sorting)이란 데이터 요소들을 오름차순 또는 내림차순으로 체계적으로 배열하는 과정을 말합니다.
정렬이라는 개념은 인간이 '빠른 검색'의 중요성을 깨닫면서 자연스럽게 등장했습니다.
우리는 일상에서 다양한 것을 검색해야 합니다. 데이터베이스 속 특정 레코드, 명단 속 학번, 전화번호부의 번호, 책의 특정 페이지 등이 대표적인 예입니다.
데이터가 무질서하고 정렬되지 않은 상태로 보관되면 원하는 정보를 찾기가 매우 어려워집니다. 다행히 정렬 개념의 등장으로 누구나 데이터를 일정한 순서로 정리할 수 있게 되었습니다.
정렬은 데이터를 일정한 순서로 배열함으로써 검색 과정을 훨씬 쉽고 빠르게 만들어 줍니다.
정렬의 효율성 판단 기준
카드 한 벌을 순서대로 정리한다고 가정해 봅시다. 사람은 모든 카드를 하나씩 확인하면서 차례대로 카드 더미를 만들어 갈 것입니다.
이런 방식으로 카드를 정리하려면 많은 시간이 걸리지만, 사람들은 여전히 같은 방식으로 작업합니다. 하지만 컴퓨터는 이렇게 동작하지 않습니다.
프로그래밍 시대가 시작된 이래로 과학자들은 다양한 알고리즘을 활용해 데이터를 정렬하는 문제를 해결하기 위해 끊임없이 연구해 왔습니다. 그렇다면 어떤 정렬 알고리즘이 다른 알고리즘보다 우수한지는 무엇으로 판단할 수 있을까요? 판단 기준은 크게 두 가지입니다.
- 주어진 데이터를 정렬하는 데 소요되는 시간(Time)
- 정렬 작업을 수행하는 데 필요한 메모리 공간(Memory Space)
즉, 더 적은 시간과 더 적은 메모리로 정렬을 완료하는 알고리즘이 더 효율적이라고 평가할 수 있습니다.
C 언어 정렬 예제 코드
다음은 선택 정렬(Selection Sort) 방식으로 데이터를 오름차순 정렬하는 C 프로그램입니다.
#include<stdio.h>
int main(){
int a[50], i, j, n, t, sm;
printf("enter the No: of elements in the list:\n");
scanf("%d", &n);
printf("enter the elements:\n");
for (i=0; i<n; i++){
scanf("%d", &a[i]);
}
for (i=0; i<n-1; i++){
sm=i;
for (j=i+1; j<n; j++){
if (a[j] < a[sm]){
sm=j;
}
}
t=a[i];
a[i]=a[sm];
a[sm]=t;
}
printf("after selection sorting the elements are:\n");
for (i=0; i<n; i++)
printf("%d\t", a[i]);
return 0;
}
코드 동작 원리
이 프로그램은 선택 정렬(Selection Sort) 알고리즘을 사용합니다. 먼저 사용자로부터 데이터의 개수(n)와 각 요소를 입력받은 뒤, 전체 배열을 반복적으로 탐색하며 현재 위치에 들어가야 할 최솟값을 찾아 서로 교환(swap)합니다. 이 과정을 마지막에서 두 번째 위치까지 반복하면 배열 전체가 오름차순으로 정렬됩니다. 선택 정렬의 시간 복잡도는 O(n²)으로, 비교적 단순하지만 데이터 양이 많아지면 효율이 떨어지는 특징이 있습니다.
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
enter the No: of elements in the list:
4
enter the elements:
34
12
56
7
after selection sorting the elements are:
7 12 34 56
입력된 값 34, 12, 56, 7이 정렬 후 7, 12, 34, 56 순서로 오름차순 출력되는 것을 확인할 수 있습니다.