- 개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.
7. 정렬
자료구조에서 말하는 정렬은 다수의 자료(데이터)가 있을 때 그 자료들을 어떠한 방식으로 어떻게 정렬할 것인가를 말한다. 정렬 파트를 공부하는데 있어 교재에서는 2가지 정도의 용어를 정리하고 시작한다.
리스트(list)란 용어를 하나 이상의 필드로 된 레코드의 집합이라는 의미로 사용된다. 이 때 레코드를 서로 구별하기 위해 사용되는 필드는 키(key)라 한다. (C로쓴자료구조론_351p)
쉽게쉽게 생각하면 다음과 같다.
- 리스트 : 하나 이상의 필드로 된 레코드의 집합
- 키 : 레코드를 구분하기 위해서 사용되는 필드
예를 들어보자. 전화번호부가 리스트라고 할 때, 각 레코드는 다음과 같은 3개의 필드, 즉 이름, 주소, 전화번호를 갖는다. 이 때 키는 일반적으로 사람의 이름이 된다. (C로쓴자료구조론_351p)
전화번호부
이름 |
주소 |
전화번호 |
YoWu |
대한민국 |
01066xx |
SoBa |
보라카이 |
01077xx |
JOY |
이집트 |
01088xx |
그러나 특정 전화번호에 해당되는 레코드를 찾고자 하는 경우에는 전화번호가 키될 수도 있다. 이러한 키의 개념은 자료구조 뿐만 아니라 데이터베이스 구조에서도 사용될 수 있다.
정렬을 위해서는 탐색이 우선 실행되어야 한다. 크게 순차탐색, 이진탐색으로 나뉘는데 이는 사람이 사용하는 탐색 방법과 대응되지 않는다. (컴퓨터의 탐색 방법과 사람이 의식적으로 탐색 할 때의 방법이 다르다는 뜻)
순차탐색 (Sequential Search)
- 레코드 리스트를 왼편에서 오른편, 또는 오른편에서 왼편으로 레코드를 검사하는 것
무슨 순차탐색이라고 말하니 뭔가 있어 보이고 어려워 보인다. 그런데 조금만 생각하면 우리는 평소에 프로그래밍 할 때도 순차탐색을 많이 사용하고 있다. 이게 무슨 말인고 하니.
int arr[8] = {24,53,63,123,56,87,33,76};
위와 같은 배열이 있을 때 배열에서 87이라는 값을 찾기 위해 다음과 같이 코딩할 수 있다.
for(int i=0; i<sizeof(arr)/4; i++) {
if(arr[i] == 87) {
return i;
}
}
대충 arr 배열의 0부터 8까지를 순서대로 탐색해서 찾는 값(87)을 발견했을 때 해당 인덱스의 번호(i)를 리턴하는 코드다. (실행해보지는않았다) C를 조금 이라도 공부했다면 무슨 뜻인지 알 수 있다. 그냥 무조건 원하는 값이 나올 때까지 처음부터 탐색하는 방법이 순차탐색이다. 이 내용을 교재에서는 다음과 같이 C로 표현했다.
int seqSearch(element a[], int k, int n)
{
int i;
for(i = 1; i <= n && a[i].key != k; i++);
if(i>n) return 0;
return i;
}
a[1]부터 a[n] 까지 탐색한다. a[i].key=k를 만족하는 가장 작은 i를 반환한다. 만약 그런 k가 배열에 없으면, 0을 반환한다. 내가 즉흥적으로 짠 코드와 비교해보면 for문 내에서 if로 같은 값인지 확인한 내 코드와 달르게 for문안에서 비교 및 확인 끝난다. 이런걸 두고 세련된 코드라고 교수님이 말하셨던 것 같다.
n개의 레코드를 가진 리스트를 순차탐색하면 O(n)의 시간이 걸리며 성공적인 탐색을 위한 평균 키 비교 횟수는 다음과 같다.
아 그런데, 나는 컴공이지만 수학을 정말로 정말로 정말로 정말 싫어하기 때문에 위 수식에 대한 설명은 패스한다.
이진(이원)탐색 (Binary Search)
흔히 바이너리 서치, 이진탐색, 이원탐색 등 참 다양하게 불리는 탐색 방법이다. 저비용 고효율적인 탐색방법으로도 유명하다. 아쉽게도 교재 7장 정렬파트에서 이진탐색에 대한 자세한 내용은 나오지 않는다. 하지만 앞 부분을 통해 대강이나마 내용을 유추할 수 있다.
- searchnum < list[middle] : 이 경우는 searchnum이 list[0]과 list[middle-1] 사이에 있으므로 right가 middle-1로 설정된다.
- searchnum = list[middle] : 이 경우는 middle을 반환한다.
- searchnum > list[middle] : 이 경우는 searchnum이 list[middle+1]과 list[n-1] 사이에 있으므로 left가 middle+11로 설정된다.
(C로쓴자료구조론_11p)
아 어렵다. 잠시 컴퓨터의 아스키(ASCII) 코드 체계를 한번 짚고 넘어가자. 깊이는 말고 얕게 짚어보자. 아스키 코드로 영문자 'A'~'Z'는 10진수 65~90에 해당한다. 문자가 숫자와 매핑되기 때문에 이를 탐색에 사용할 수도 있다.
아스키 코드표.jpg
간단한 예를 생각해보자. 'A'~'Z' 중 하나의 값을 가진 미지의 문자형 변수 ch가 있다. 이것을 순차탐색으로 확인한다면 다음과 같이 코드를 작성할 수 있을 것이다.
for(int i=65; i<=90; i++) // for(int i='A; i<='Z'; i++)
{
if(ch == i) {
printf("ch is %c\n", i);
break;
}
}
운이 좋아 ch가 'A'일 경우 탐색은 1번만에 성공한다. 하지만 ch가 'Z'라면? 최악의 경우의 수 26번 만에 탐색이 성공하게 된다. 알파벳 같은 작은 표본은 상관 없지만 만약 탐색해야하는 레코드가 1,000개라면? 100,000개라면? 999999999999개라면? 탐색에 걸리는 시간은 기하급수적으로 증가한다.
그렇다면 이진탐색은 뭔가 다를까? 우선 다음 코드를 보자
int left = 65; //'A'=65
int right = 90; //'Z'=90
int middle;
while(1)
{
middle = left+((right-left)/2); //left~right의 가운데 값
if(ch < middle) {
right = middle-1;
continue;
}
else if(ch > middle) {
left = middle+1;
continue;
}
else if(ch == middle) {
printf("ch is %c\n", middle);
break;
}
}
특정 값을 찾기위해 범위를 반으로 쪼개고 반으로 쪼개고 반으로 쪼개 값을 찾는다. 어떻게 보면 소거법에 더 가깝달까? 위와 같은 방식으로 n개의 레코드를 가진 리스트를 이진탐색할 때의 시간은 O(log n)이 된다.
실제로 순차탐색과 이진탐색의 차이가 얼마나 나는지 궁금했기에 실제로 코드로 구현해 보았다. 순차탐색의 경우 ch에 'Y'문자가 있을 때 탐색은 25번 만에 성공함을 예상할 수 있다. 그렇다면 이진탐색은?
search.c
결과
(위 코드는 Ubuntu 12.04 LTS에서 gcc로 컴파일 되었습니다.)
이진탐색으로 4번 만에 탐색에 성공했다. 순차탐색과 이진탐색의 차이가 꽤 크다. 26개의 레코드에서도 차이가 이렇게 나는데 레코드의 수가 더 많아지면 당연히 차이도 더 커질테다. 이래서 자료구조나 알고리즘을 배워야 하나보다.
다음 포스팅에서는 삽입 정렬, 퀵 정렬 등 본격적인 정렬 알고리즘에 대해 포스팅해 보겠습니다.