구체적인 정렬방법 개요
정렬할 데이터가 배열에 있다고 했을때
- 정렬할 배열의 상한과 하한값을 구한다.
- 하한값이 상한값보다 작으면 배열을 나눈다.
- 두 배열간 비교하여 교환하고 두 배열의 작업대상도 이동한다.
- 나누어진 각각의 배열에 대해 위의 단계를 반복한다.
이러한 절차를 다음과 같은 하나의 예를 통해 그림으로 표현하면 다음과 같습니다. 이번 예는 총 23단계에 걸쳐 소트가 진행되지만 편의상 원리만 설명하고자 7단계만 설명합니다. 참고로 이번 예와 퀵소트 코드는 제가 만든 것이 아니라 제가 가진 책을 참조했습니다. 즉 다른 말로 하면 베꼈습니다. 책은 Ken Getz와 Mike Gilbert가 공저한 VBA Developer's Handbook 입니다.
원래의 데이터는 79,30,24,48,26,34,05,48,21,86(10개)입니다. 이걸 퀵소트로 정렬하여 보는 겁니다. 위의 그림에서 각 단계를 숫자로 표시하였으며 각 단계를 설명하겠습니다.
1단계:
배열의 하한위치(i)의 값이 상한위치(j)의 값보다 작으면 중간위치(값은 26)를 구합니다. 그리고 하한위치값(79)과 중간위치값(26)보다 작으면 하한위치(i)를 오른쪽으로 증가합니다. 마찬가지로 상한위치값(86)이 중간위치값(26)보다 크면 상한위치(j)를 왼쪽으로 옮긴다. 여기에선 86이 26보다 크므로 한 포인트 옮겨 21을 가리키도록 하였습니다.
i=0
j=9->8로 이동함.
2단계:
하한위치가 상한위치보다 작으면(i<j)이면 서로의 값을 교환합니다.
3단계:
교환후 하한값은 1증가하고(i=i+1) 상한값은 1 감소시킵니다(j=j-1)
i=0->1
j=8->7
4단계:
하한위치값(30)이 중간위치값(26)보다 작지 않으므로 그대로 하한위치는 그대로 두고, 상한위치값(48)이 중간위치값(26)보다 크므로 상한위치를 왼쪽으로 옮겨(j=j-1) 상한위치값이 05가 됩니다. 하한위치가 1이고 상한위치가 6입니다. 하한위치가 상한위치보다 적으므로 서로의 위치값을 교환합니다.
5단계:
3단계와 같이 하한값과 상한값의 위치를 증가/감소시킵니다.
6단계와 7단계 역시 위의 단계를 반복합니다. 이 예에서 정렬이 완료되려면 총23단계를 거칩니다. 사실 이러한 알고리즘을 훤히 알면 좋지만 저 역시 그런 분야를 보면 하품이 나는 처지라 퀵소트가 어떻게 이루어 지는가만 알아 보았습니다.
// 퀵소트
***************퀵소트소스*************
#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )
#define MAX_SIZE 1000000 /* 최대 배열 크기 */
int list[MAX_SIZE];
int n; /* 실제 레코드의 수 */
void quick_sort(int, int); /* 퀵정렬 */
int main()
{
int i;
clock_t a,b;
printf("Enter the number of numbers to generate : ");
scanf("%d", &n);
srand((unsigned)time(NULL)); /* 난수 발생 함수 초기화 */
for(i=0; i<n; i++) { /* 난수 생성 및 출력 */
list[i] = (rand()*rand())%1000000;/*난수 발생 범위 0~999999*/
printf("%d ", list[i]);
}
a=clock();
quick_sort(0,n-1); /* 퀵정렬 호출 */
b=clock();
printf("\n\nSorted array :\n"); /* 정렬된 레코드 출력 */
for(i=0; i<n; i++)
printf("%d ", list[i]);
printf("\n"); /* 실행시간 출력 */
printf("Execution Duration=%f\n",(double)(b-a)/CLK_TCK);
}
void quick_sort(int left, int right)
{
int pivot, i, j, temp;
if(left<right) { /* 리스트에 2개 이상의 레코드가 있을 경우 */
i = left; j = right+1; pivot = list[left]; /* 피벗 설정 */
do {
do /* 왼쪽 리스트에서 피벗보다 큰 레코드 선택 */
i++;
while(list[i]<pivot);
do /* 오른쪽 리스트에서 피벗보다 작은 레코드 선택 */
j--;
while(list[j]>pivot);
if(i<j) SWAP(list[i], list[j], temp); /* 레코드 i, j 교환 */
} while(i<j); /* 인덱스 i,j가 엇갈리지 않는 한 반복 */
SWAP(list[left], list[j], temp); /* 레코드 j와 피벗 교환 */
quick_sort(left, j-1); /* 왼쪽 부분리스트를 퀵정렬 */
quick_sort(j+1, right); /* 오른쪽 부분리스트를 퀵정렬 */
}
}
// 버블소트
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )
#define MAX_SIZE 1000000 /* 최대 배열 크기 */
int list[MAX_SIZE];
int n; /* 실제 레코드의 수 */
void bubble_sort(); /* 버블정렬 함수의 원형 */
int main()
{
int i;
clock_t a, b;
printf("Enter the number of number to generate : ");
scanf("%d", &n);
srand((unsigned)time(NULL)); /* 난수 발생 함수 초기화 */
for (i=0; i<n; i++) { /* 난수 생성 및 출력 */
list[i] = (rand()*rand())%1000000; /* 난수 발생 범위 0-999999 */
printf("%d ", list[i]);
}
a = clock();
bubble_sort();
b = clock();
printf("\n\nSorted array :\n");
for (i=0; i<n; i++)
printf("%d ", list[i]);
printf("\n");
printf("Execution Duration=%f\n", (double)(b - a)/CLK_TCK);
}
void bubble_sort()
{
int i, j, temp;
for (i=n-1; i>0; i--) {
for (j=0; j<i; j++)
if(list[j] > list[j+1])
SWAP(list[j], list[j+1], temp);
}
}
0