C ソートアルゴリズム
バブルソート
バブルソート（英語: Bubble Sort）は、単純なソートアルゴリズムです。ソート対象の数列を繰り返し訪れ、一度に2つの要素を比較し、それらの順序（例：大きい順、先頭文字がAからZなど）が間違っていれば、それらを交換します。
過程デモ：
例
#include <stdio.h>
// 関数宣言
void bubble_sort(int arr[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // 配列の長さを計算
bubble_sort(arr, len); // バブルソート関数を呼び出し
// ソート後の配列を出力
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// バブルソート関数
void bubble_sort(int arr[], int len) {
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len - 1 - i; j++) {
// 要素の位置を交換
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
選択ソート
選択ソート（Selection Sort）は、単純で直感的なソートアルゴリズムです。その動作原理は次のとおりです。まず、未ソートのシーケンスから最小（最大）の要素を見つけ、ソート済みシーケンスの先頭位置に格納します。次に、残りの未ソート要素から最小（最大）の要素を探し、ソート済みシーケンスの末尾に置きます。これをすべての要素がソートされるまで繰り返します。
過程デモ：
例
#include <stdio.h>
// 関数宣言
void selection_sort(int a[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // 配列の長さを計算
selection_sort(arr, len); // 選択ソート関数を呼び出し
// ソート後の配列を出力
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// 選択ソート関数
void selection_sort(int a[], int len) {
for (int i = 0; i < len - 1; i++) {
int min = i; // 最小値の位置を記録、最初の要素をデフォルトの最小値とする
for (int j = i + 1; j < len; j++) {
if (a[j] < a[min]) { // 現在の最小値を見つける
min = j; // 最小値の位置を記録
}
}
// 2つの変数を交換
if (min != i) {
int temp = a[min];
a[min] = a[i];
a[i] = temp;
}
}
}
/*// カスタム交換関数
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}*/
挿入ソート
挿入ソート（英語: Insertion Sort）は、単純で直感的なソートアルゴリズムです。その動作原理は、順序付けられたシーケンスを構築し、未ソートのデータについては、ソート済みシーケンスを後ろから前へ走査して、対応する位置を見つけて挿入します。挿入ソートは実装上、通常インプレースソート（つまり {\displaystyle O(1)} {\displaystyle O(1)} の追加スペースしか必要としないソート）を採用するため、後ろから前への走査中に、ソート済みの要素を繰り返し後方へ
移動させて、最新の要素に挿入スペースを提供します。過程デモ：
例
#include <stdio.h>
// 関数宣言
void insertion_sort(int arr[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // 配列の長さを計算
insertion_sort(arr, len); // 挿入ソート関数を呼び出し
// ソート後の配列を出力
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// 挿入ソート関数
void insertion_sort(int arr[], int len) {
for (int i = 1; i < len; i++) {
int temp = arr[i]; // 現在挿入する要素
int j = i;
// tempより大きい要素を右に移動
while (j > 0 && arr[j - 1] > temp) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = temp; // 要素を正しい位置に挿入
}
}
シェルソート
シェルソートは、減少増分ソートアルゴリズムとも呼ばれ、挿入ソートのより効率的な改良版です。シェルソートは安定ではないソートアルゴリズムです。
シェルソートは、挿入ソートの以下の2つの性質に基づいて改良方法を提案したものです：
- 挿入ソートは、ほぼソート済みのデータを操作する場合、効率が高く、線形ソートの効率を達成できます。
- しかし、挿入ソートは一般的に非効率です。挿入ソートは毎回データを1つしか移動できないためです。
過程デモ：
例
#include <stdio.h>
// 関数宣言
void shell_sort(int arr[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // 配列の長さを計算
shell_sort(arr, len); // シェルソート関数を呼び出し
// ソート後の配列を出力
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// シェルソート関数
void shell_sort(int arr[], int len) {
// 初期間隔を計算
for (int gap = len / 2; gap > 0; gap /= 2) {
// 各間隔に対して挿入ソートを行う
for (int i = gap; i < len; i++) {
int temp = arr[i]; // 現在挿入する要素
int j = i;
// tempより大きい要素を移動
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp; // 要素を正しい位置に挿入
}
}
}
マージソート
データを2つのセグメントに分割し、2つのセグメントから最小の要素を1つずつ選び、新しいデータセグメントの末尾に移動します。
上から下へ、または下から上へ行うことができます。
過程デモ：
反復法
#include <stdio.h>
#include <stdlib.h>
// 関数宣言
int min(int x, int y);
void merge_sort(int arr[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // 配列の長さを計算
merge_sort(arr, len); // マージソート関数を呼び出し
// ソート後の配列を出力
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// 2つの数値の最小値を返す
int min(int x, int y) {
return x < y ? x : y;
}
// マージソート関数
void merge_sort(int arr[], int len) {
int* a = arr;
int* b = (int*) malloc(len * sizeof(int));
if (b == NULL) { // メモリ割り当てが成功したか確認
fprintf(stderr, "Memory allocation failed\n");
exit(EXIT_FAILURE);
}
for (int seg = 1; seg < len; seg += seg) {
for (int start = 0; start < len; start += seg + seg) {
int low = start;
int mid = min(start + seg, len);
int high = min(start + seg + seg, len);
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
// 2つの部分配列をマージ
while (start1 < end1 && start2 < end2) {
b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
}
while (start1 < end1) {
b[k++] = a[start1++];
}
while (start2 < end2) {
b[k++] = a[start2++];
}
}
// 配列ポインタを交換
int* temp = a;
a = b;
b = temp;
}
// aとarrが異なる場合、aの内容をarrにコピーして戻す
if (a != arr) {
for (int i = 0; i < len; i++) {
b[i] = a[i];
}
b = a;
}
free(b); // メモリを解放
}
再帰法
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 関数宣言
void merge_sort_recursive(int arr[], int reg[], int start, int end);
void merge_sort(int arr[], const int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // 配列の長さを計算
merge_sort(arr, len); // マージソート関数を呼び出し
// ソート後の配列を出力
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// 再帰でマージソートを実装
void merge_sort_recursive(int arr[], int reg[], int start, int end) {
if (start >= end)
return;
int mid = start + (end - start) / 2;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, reg, start1, end1);
merge_sort_recursive(arr, reg, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2) {
reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
}
while (start1 <= end1) {
reg[k++] = arr[start1++];
}
while (start2 <= end2) {
reg[k++] = arr[start2++];
}
// memcpyを使用して配列をコピーし、効率を向上
memcpy(arr + start, reg + start, (end - start + 1) * sizeof(int));
}
// マージソートのエントリ関数
void merge_sort(int arr[], const int len) {
int* reg = (int*)malloc(len * sizeof(int));
if (reg == NULL) { // メモリ割り当てが成功したか確認
fprintf(stderr, "Memory allocation failed\n");
exit(EXIT_FAILURE);
}
merge_sort_recursive(arr, reg, 0, len - 1);
free(reg); // メモリを解放
}
クイックソート
区間内でランダムに1つの要素を基準として選び、基準より小さい要素を基準の前に、基準より大きい要素を基準の後に置き、その後、小さい領域と大きい領域をそれぞれソートします。
過程デモ：
反復法
#include <stdio.h>
// 範囲構造体
typedef struct _Range {
int start, end;
} Range;
// 新しい範囲を作成
Range new_Range(int s, int e) {
Range r;
r.start = s;
r.end = e;
return r;
}
// 2つの整数を交換
void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}
// クイックソート関数
void quick_sort(int arr[], const int len) {
if (len <= 0)
return; // lenが負の値のときにセグメンテーションフォールト（Segment Fault）が発生するのを防ぐ
Range r[len];
int p = 0;
r[p++] = new_Range(0, len - 1);
while (p > 0) {
Range range = r[--p];
if (range.start >= range.end)
continue;
int mid = arr[(range.start + range.end) / 2]; // 中央の点を基準点として選択
int left = range.start, right = range.end;
do {
while (arr[left] < mid) ++left; // 基準点の左側が要件を満たしているか確認
while (arr[right] > mid) --right; // 基準点の右側が要件を満たしているか確認
if (left <= right) {
swap(&arr[left], &arr[right]);
left++;
right--; // ポインタを移動して続行
}
} while (left <= right);
if (range.start < right) r[p++] = new_Range(range.start, right);
if (range.end > left) r[p++] = new_Range(left, range.end);
}
}
int main() {
int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
int len = sizeof(arr) / sizeof(arr[0]); // 配列の長さを計算
quick_sort(arr, len); // クイックソート関数を呼び出し
// ソート後の配列を出力
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
再帰法
#include <stdio.h>
// 2つの整数を交換
void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}
// 再帰でクイックソートを実装
void quick_sort_recursive(int arr[], int start, int end) {
if (start >= end)
return;
int mid = arr[end];
int left = start, right = end - 1;
while (left < right) {
while (left < right && arr[left] < mid)
left++;
while (left < right && arr[right] >= mid)
right--;
swap(&arr[left], &arr[right]);
}
if (arr[left] >= arr[end])
swap(&arr[left], &arr[end]);
else
left++;
quick_sort_recursive(arr, start, left - 1);
quick_sort_recursive(arr, left + 1, end);
}
// クイックソートのエントリ関数
void quick_sort(int arr[], int len) {
quick_sort_recursive(arr, 0, len - 1);
}
int main() {
int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
int len = sizeof(arr) / sizeof(arr[0]); // 配列の長さを計算
quick_sort(arr, len); // クイックソート関数を呼び出し
// ソート後の配列を出力
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}