20260630_3

20260623_3

ソート

• 選択ソート
• 挿入ソート
• バブルソート

---

ソート=整列

データ(キーを含むレコード)をキーによって線形順序で並べ替える

内部整列(メモリしか使わない)
外部整列(ストレージも使う)

ソートの安定性
→同じキーの値のデータの並びが保持されているのか

ソートの操作

• 交換
• 選択
• 挿入

---

レコードの定義

typedef struct{
	keytype key;
	elementtype element;
}recordtype;
 
recordtype a[LIMIT];
 
void swap(recordtype *x, recordtype *y){
	recordtype tmp;
	tmp=*x;
	*x=*y;
	*y=tmp;
}

---

選択ソート

1. 最小値を見つけてa[1]へ移動する
2. 2番めに小さい値を見つけてa[2]へ移動する
3. ………

a[0]は使わない実装とする

→最小/最大は見つけやすい

void selection_sort(recordtype a[],int n){
	int i,j,minindex;
	for(i=1;i<n;i++){
		minindex=i;
		for(j=i+1;j<=n;j++){
			if(a[j].key<a[minindex].key){
				minindex=j;
			}
		}
		swap(&a[minindex],&a[i]);
	}
}

選択ソートでは要素の移動は一個あたり一回($O(n)$)だが、比較が$O(n^2)$になってしまう
→低速

---

挿入ソート

• 先頭から$i$番目まで整列済みのときa[i+1]を正しい位置に挿入する

• 自分の一個前が自分より小さくなったら入れ替え操作を行う

→これを先頭から行えば大丈夫

void insertion_sort(recordtype a[],int n){
	int i,j;
	recordtype v;
	a[0].key=INT_MIN;
	for(i=2;i<=n;i++){
		v=a[i];
		j=i;
		while(a[j-1].key>v.key){
			a[j]=a[j-1];
			j--;
		}
		a[j]=v;
	}
}

番兵としてINT_MINを利用している

最良では$O(n)$だが、一般の場合には$O(n^2)$

---

バブルソート

隣同士を入れ替え続けて少しずつ目的の形にしていく

void bubble_sort(recordtype a[],int n){
	int i,j;
	for(i=1;i<n;i++){
		for(j=n;j>=i+1;j--){
			if(a[j].key<a[j-1].key){
				swap(&a[j],&a[j-1]);
			}
		}
	}
}

比較回数が$O(n^2)$
交換回数は最良だと0だが、最悪の場合は$O(n^2)$

効率は良くない

---