[9]

정렬알고리즘

1. 내부 정렬: 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용.
2. 외부 정렬: 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없을때
사용.

1. 버블 정렬

이웃한 두 요소의 대소 관계를 비교하여 교환을 반복

#define swap (type, x, y) do { type t=x; x=y; y=t; } while(0)

void bubble(int a[], int n){
	int k=0;
    while(k<n-1){
    	int j;
        int last = n-1;
        for(j=n-1; j>k; j--)
        	if(a[j-1] > a[j]{
            	swap(int, a[j-1], a[j]);
                last = j; // 마지막으로 교환을 수행한 위치저장
            }
        k=last; 
    }
}

2. 단순 선택 정렬

가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘

#define swap (type, x, y) do { type t=x; x=y; y=t; } while(0)

void selection(int a[], int n){
	int i,j;
    	for(i=0; i<n-1; i++){
        	int min=i;
            	for(j=i+1; j<n; j++){
                	if(a[j]<a[min]) min=j;
                	swap(int, a[i], a[min]);
                }
        }
}

3. 단순 삽입 정렬

선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하여 정렬하는 알고리즘.

void insertion(int a[], int n){
	int i,j;
    for(i=1; i<n; i++){
    	int tmp=a[i];
        for(j=i; j>0 && a[j-1] >tmp; j--)
        	a[j] = a[j-1];
           a[j] = tmp;
    }
}

4. 셸 정렬

단순 삽입 정렬의 장점을 살리고 단점을 보완하여 더 빠르게 정렬하는 알고리즘

void shell(int a[], int n){
	int i,j,h;
    for(h=n/2; h>0; h/=2)
    	for(i=h; i<n; i++){
        	int tmp=a[i];
            for(j=i-h; j>=0; && a[j] > tmp; j-=h)
            	a[j+h] = a[j];
            a[j+h] = tmp;
        }
}

위 코드는 n=8 개의 요소에서 h(증분값)을 h=4, h=2, h=1로 설정하여
1. 2개 요소에 대해 4-정렬(4개그룹) 예) { a[0], a[4]}, {a [1], a[5] }, ...
2. 4개 요소에 대해 2-정렬(2개그룹) 예) { a[0], a[2],a [4], a[6] }, { ...
3. 8개 요소에 대해 1-정렬(1개그룹)