アルゴリズム導論第2章コード
1、ソートの挿入
アルゴリズム:
テスト:
出力:1 2 3 4 5
2、集計ソート
アルゴリズム:
テスト:
出力:1 2 3 4 5
アルゴリズム:
void InsertionSort(int *a, int n)
{
int i, j;
for (i = 1; i < n; i++) {
int key = a[i];
j = i - 1;
while (j >= 0 && a[j] > key) {
a[j+1] = a[j];
j--;
}
a[j+1] = key;
}
}
テスト:
int main(int argc, const char * argv[])
{
int a[] = {3, 5, 1, 2, 5, 4};
int n = sizeof(a) / sizeof(*a);
InsertionSort(a, n);
int i = 0;
for (; i < n; i++) {
printf("%d ", a[i]);
}
return 0;
}
出力:1 2 3 4 5
2、集計ソート
アルゴリズム:
void Merge(int *a, int low, int mid, int high)
{
int i = low;
int j = mid + 1;
int *temp = malloc((high-low+1) * sizeof(int));
int k = 0;
while (i <= mid && j <= high) {
if (a[i] <= a[j]) {
temp[k++] = a[i++];
}else{
temp[k++] = a[j++];
}
}
while (i <= mid) {
temp[k++] = a[i++];
}
while (j <= high) {
temp[k++] = a[j++];
}
for (i = low, k = 0; i <= high; i++, k++) {
a[i] = temp[k];
}
free(temp);
}
void MergeSort(int *a, int low, int high)
{
if (low < high) {
int mid = (low + high) / 2;
MergeSort(a, low, mid);
MergeSort(a, mid+1, high);
Merge(a, low, mid, high);
}
}
テスト:
int main(int argc, const char * argv[])
{
int a[] = {3, 5, 1, 2, 5, 4};
int n = sizeof(a) / sizeof(*a);
int low = 0;
int high = n - 1;
MergeSort(a, low, high);
int i = 0;
for (; i < n; i++) {
printf("%d ", a[i]);
}
return 0;
}
出力:1 2 3 4 5