[9]

ソートアルゴリズム

1.内部ソート:ソートするすべてのデータを1つの配列に格納します.
2.外部ソート:ソートするデータが多すぎて1つの配列に格納できない場合
使用します.

1.泡の位置合わせ

隣接する2つの要素のサイズ関係を比較して繰り返し交換

#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グループ)