학부 1학년 때 컴퓨터 개론 시간에 C를 배웠던 것 같다. 당시 전혀 학과 공부를 신경쓰지 않던 나는 수업을 통해 배우는 게 별로 없었다. 아직도 C조차 제대로 모르는 이유는 여기에서 기인한다. 어쨌든, 그 때 마지막 과제던가? 퀵 정렬을 C로 짜오라는 과제가 있었던 것 같다. 당시에 퀵 정렬이라하면 최고 수준의 프로그래밍 실력이 있어야 할 수 있다고 생각했다. 마치, 1학년 당시 '학점이 3.0을 넘는 사람은 인간이 아니다'라고 믿었던 것처럼 어이없는 믿음이였지만 말이다. 재귀(recursion)가 들어가면 일단 머리가 돌아가지 않았다.
퀵 정렬의 기본 개념을 보면, 주어진 수 중에 임의의 값(pivot)을 기준으로 그 값보다 작은 값과 큰 값으로 나눈 후 이 pivot 값을 가운데 놓은 후, 두 부분을 각각 다시 퀵 정렬한다. 머지 정렬(merge sort)와 비슷한데, 머지 정렬은 단수히 두 분으로 계속 나누다가 합쳐질 때 양쪽에서 작은 값들 부터 뽑아 내어 정렬한다. A={1,3,4}와 B={2,5,9}가 있으면 A,B,A,A,B,B 순으로 앞의 수를 뽑아 {1,2,3,4,5,9}로 만들어 준다. 둘 다 평균 O(nlgn)의 시간 복잡도를 가진다. T(n)=T(n/2)+O(n)을 풀어서 나오는 듯.
#include <iostream>
using namespace std;
void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
void quicksort(int *arr, int s, int e) {
int p = s;
if (s >= e) return;
for (int i = s; i < e; i++) {
if (arr[e] >= arr[i]) {
swap(arr[i], arr[p]);
p++;
}
}
swap(arr[p], arr[e]);
quicksort(arr, s, p-1);
quicksort(arr, p+1, e);
}
int main() {
int arr[] = {8,1,3,7,4,15,9,11};
int arr2[] = {9,4,1,3,24124,12412,412,412, 3,1};
quicksort(arr, 0, 7);
for (int i = 0; i < 8; i++)
cout << arr[i] << " ";
cout << endl;
quicksort(arr2, 0, 9);
for (int i = 0; i < 10; i++)
cout << arr2[i] << " ";
cout << endl;
}
학부 1학년으로 돌아가면 즐겁게 다시 공부할 수 있을 것 같다. ㅎㅎ
'[아는게 힘이다] > [프로그래밍]' 카테고리의 다른 글
| 생각하는(?) 실용주의(?) 프로그래머 (2) | 2010/03/04 |
|---|---|
| [CS] 연결 리스트 뒤집기 (Reverse Linked List) (6) | 2010/02/28 |
| [CS] 퀵 정렬 (Quick Sort) (2) | 2010/02/22 |
| [CS] 비트 매스크(Bit Mask) (2) | 2010/02/21 |
| [CS] 반복되지 않는 첫번째 문자를 찾아라 (3) | 2010/02/19 |
