안녕하세요 기린입니다 :)
알고리즘을 공부할 때 가장 먼저 풀어보는 문제로 '정렬(Sort)' 에 대해 알아보겠습니다.
수많은 알고리즘 중에서 이 정렬 알고리즘은 효율성의 차이를 극명하게 보여주기 때문에 단계적으로 공부하시면 효과적일 것 같습니다
자 바로 간단한 문제부터 시작해보겠습니다
다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.
1 10 5 8 7 6 4 3 2 9
위와 같은 문제를 만났을때 여러분들은 어떻게 푸실 건가요? 만약 처음 알고리즘을 공부하시는 분들이라면
머릿속이 복잡하실수도 있습니다.. 하하 만약 사람이라면 전체 숫자를 확인하고 1부터 10까지 숫자를 써내려 가겠죠 ?
하지만 컴퓨터에게는 그 과정을 구체적으로 명시해줘야 제대로 작동할 수 있습니다
그 과정을 알고리즘이라고 할 수 있죠
먼저 알고리즘 중 하나인 '선택정렬' 을 사용하여 문제를 풀어보겠습니다
자 선택해서 정렬한다 설명하자면 '가장 작은 것을 선택해서 제일 앞으로 보낸다' 가 될 수 있겠죠?
이 정렬은 가장 원시적이고 기초적인 방법 중 하나인데요 소스코드로 확인해 보겠습니다
#include <stdio.h>
int main(void) {
int i, j, min, index, temp;
int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
for(i = 0; i < 10; i++) {
min = 9999;
for(j = i; j < 10; j++) {
if(min > array[j]) {
min = array[j];
index = j;
}
}
temp = array[i];
array[i] = array[index];
array[index] = temp;
}
for(i = 0; i < 10; i++) {
printf("%d ", array[i]);
}
return 0;
}자 소스코드를 보시면 min 은 가장 적은 숫자를 일시적으로 담는 변수이고, temp는 배열에서 두 숫자의 위치를 서로 바꾸기 위해 사용하는 변수입니다
여기서 기본적인 소스이기 때문에 반복문에 대해서는 설명 드리지 않겠습니다 :]
위 소스를 컴파일하면 정상적으로 정렬되는걸 볼 수 있을텐데요
여기서 중요한 것은 데이터의 갯수가 N개일 때 총 몇 번의 비교 연산을 해야 되는지 입니다
선택 정렬은 대략 N * (N + 1) / 2 번 가량의 연산을 수행 해야 합니다.
이를 컴퓨터에서는 가장 큰 차수를 가지고 표현합니다
선택 정렬의 시간 복잡도는 O(N^2) 입니다.
위와 같이 표현하게 되는데 다시 말해 정렬해야 할 데이터의 갯수가 1,000 개라면 대략 1,000,000번 (1,000^2) 정도 계산을 해야한다는거죠.
그렇다면 이 복잡도를 왜 알아야 할까요 ? 그건 바로 컴퓨터가 해야할 연산을 줄여 정렬의 효율을 높이고자 함이죠
앞으로 이 복잡도를 줄이는 정렬 방법에 대해 하나씩 배워보도록 하겠습니다 !
자 그럼 즐거운 코딩하세요 !
문의: ralla0405@gmail.com
