悩んでいる人
C言語で配列の要素を並び替えるソートアルゴリズムを教えて！
こういった悩みにお答えします．
本記事の信頼性
- リアルタイムシステムの研究歴12年．
- 東大教員の時に，英語でOS（Linuxカーネル）の授業．
- 2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
- プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/Vyper，Java，Ruby，Go，Rust，D，HTML/CSS/JS/PHP，MATLAB，Verse（UEFN）, Assembler (x64，ARM)．
- 東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．
- 2020年1月～現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務．2022年6月～現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO．
- 最近は自然言語処理AIとイーサリアムに関する有益な情報発信に従事．
- （AI全般を含む）自然言語処理AIの論文の日本語訳や，AIチャットボット（ChatGPT，Auto-GPT，Gemini（旧Bard）など）の記事を50本以上執筆．アメリカのサンフランシスコ（広義のシリコンバレー）の会社でプロンプトエンジニア・マネージャー・Quality Assurance（QA）の業務委託の経験あり．
- （スマートコントラクトのプログラミングを含む）イーサリアムや仮想通貨全般の記事を200本以上執筆．イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり．
こういった私から学べます．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
目次
配列の要素を並び替えるソートアルゴリズム
C言語で配列の要素を並び替えるソートアルゴリズムを紹介します．
ここで，安定ソート（ソートが安定する）とは，同じ値のデータのソート前の順序が，ソート後も保存されるソートアルゴリズムのことです．
つまり，ソート途中の各状態において，常に順序関係を保っているという意味になります．
これに対して，不安定ソート（ソートが安定しない）とは，ソート後に保存されないソートアルゴリズムのことです．
また，ソートされるデータの格納領域を変更して処理を進めていくものを内部ソート，ソートされるデータの格納領域以外に\(\mathcal{O}(n)\)（nは並び替える配列の要素数）以上の一時的な記憶領域が必要なソートを外部ソートと呼びます．
それでは，配列の要素を並び替えるソートアルゴリズムを紹介していきます．
交換ソートのアルゴリズム
交換ソートのアルゴリズムを紹介していきます．
バブルソート
バブルソート（単純ソート）は，隣り合う要素の大小を比較しながら整列させるアルゴリズムです．
バブルソートは安定な内部ソートで，平均計算量は\(\mathcal{O}(n^2)\)，最悪計算量は\(\mathcal{O}(n^2)\)です．
バブルソートは，処理時間が長く実用性は低いですが，実装はシンプルで理解しやすいです．
まずは，バブルソートのコードを読んで，ソートの概念を学びましょう！
バブルソートのコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <time.h> #define N 10 #define MAX 99 void swap(int *pa, int *pb) { int tmp; tmp = *pa; *pa = *pb; *pb = tmp; } void bubble_sort(int n, int a[]) { int i, j; for (i = 0; i < n; i++) { for (j = 1; j < n - i; j++) { if (a[j] < a[j - 1]) { swap(&a[j], &a[j - 1]); } } } } int main(void) { int a[N]; int i; srand(time(NULL)); printf("Before:"); for (i = 0; i < N; i++) { a[i] = rand() / (RAND_MAX / (MAX + 1) + 1); printf(" %2d", a[i]); } printf("\n"); bubble_sort(N, a); printf("After: "); for (i = 0; i < N; i++) { printf(" %2d", a[i]); } printf("\n"); return 0; } |
実行結果の例は以下になります．
※乱数の初期値を設定するsrand関数に現在時刻を返すtime関数を利用しているので，実行毎に配列の要素は変わります．他のソートも同様です．
|
1 2 3 4 |
$ gcc bubble_sort.c $ a.out Before: 34 25 32 80 50 56 12 17 55 54 After: 12 17 25 32 34 50 54 55 56 80 |
シェーカーソート
シェーカーソート（双方向バブルソート，改良交換法）は，バブルソートを改良したソートのアルゴリズムです．
バブルソートでは一方向にしかスキャンしないのに対して，シェーカーソートでは交互に双方向でスキャンします．
バブルソートと同じく安定な内部ソートで，平均計算量は\(\mathcal{O}(n^2)\)，最悪計算量は\(\mathcal{O}(n^2)\)です．
シェーカーソートのコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <time.h> #define N 10 #define MAX 99 void swap(int *pa, int *pb) { int tmp; tmp = *pa; *pa = *pb; *pb = tmp; } void shaker_sort(int n, int a[]) { int i, last_swap_index; int top_index = 0, bottom_index = n - 1; while (true) { last_swap_index = top_index; for (i = top_index; i < bottom_index; i++) { if (a[i] > a[i + 1]) { swap(&a[i], &a[i + 1]); last_swap_index = i; } } bottom_index = last_swap_index; if (top_index == bottom_index) { break; } last_swap_index = bottom_index; for (i = bottom_index; i > top_index; i--) { if (a[i] < a[i - 1]) { swap(&a[i], &a[i - 1]); last_swap_index = i; } } top_index = last_swap_index; if (top_index == bottom_index) { break; } } } int main(void) { int a[N]; int i; srand(time(NULL)); printf("Before:"); for (i = 0; i < N; i++) { a[i] = rand() / (RAND_MAX / (MAX + 1) + 1); printf(" %2d", a[i]); } printf("\n"); shaker_sort(N, a); printf("After: "); for (i = 0; i < N; i++) { printf(" %2d", a[i]); } printf("\n"); return 0; } |
実行結果の例は以下になります．
|
1 2 3 4 |
$ gcc shaker_sort.c $ a.out Before: 3 93 93 10 81 10 21 50 68 63 After: 3 10 10 21 50 63 68 81 93 93 |
奇偶転置ソート
奇偶転置ソートは，バブルソートを改良したソートアルゴリズムです．
バブルソートではスキャンを一方向に順次行うのに対し，奇偶転置ソートでは組ごとにスキャンします．
バブルソートと同じく安定な内部ソートで，平均計算量は\(\mathcal{O}(n^2)\)，最悪計算量は\(\mathcal{O}(n^2)\)です．
奇偶転置ソートのコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <time.h> #define N 10 #define MAX 99 void swap(int *pa, int *pb) { int tmp; tmp = *pa; *pa = *pb; *pb = tmp; } void odd_even_sort(int n, int a[]) { int i; bool is_changed; do { is_changed = false; for (i = 0; i < N - 1; i += 2) { if (a[i] > a[i + 1]) { swap(&a[i], &a[i + 1]); is_changed = true; } } for (i = 1; i < N - 1; i += 2) { if (a[i] > a[i + 1]) { swap(&a[i], &a[i + 1]); is_changed = true; } } } while (is_changed); } int main(void) { int a[N]; int i; srand(time(NULL)); printf("Before:"); for (i = 0; i < N; i++) { a[i] = rand() / (RAND_MAX / (MAX + 1) + 1); printf(" %2d", a[i]); } printf("\n"); odd_even_sort(N, a); printf("After: "); for (i = 0; i < N; i++) { printf(" %2d", a[i]); } printf("\n"); return 0; } |
実行結果の例は以下になります．
|
1 2 3 4 |
$ gcc odd_even_sort.c $ a.out Before: 83 23 53 71 58 11 67 66 79 91 After: 11 23 53 58 66 67 71 79 83 91 |
コムソート
コムソート（櫛（くし）ソート）は，バブルソートを改良したソートのアルゴリズムです．
バブルソートとは異なり，コムソートは不安定なソートです．
また，内部ソートで，平均計算時間は\(\mathcal{O}(n \log n)\)，最悪計算時間は\(\mathcal{O}(n^2)\)です．
コムソートのコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <time.h> #define N 10 #define MAX 99 void swap(int *pa, int *pb) { int tmp; tmp = *pa; *pa = *pb; *pb = tmp; } void comb_sort(int n, int a[]) { int h = n; bool is_swapped = false; int i; while (h > 1 || is_swapped) { if (h > 1) { h = (h * 10) / 13; } is_swapped = false; for (i = 0; i < n - h; i++) { if (a[i] > a[i + h]) { swap(&a[i], &a[i + h]); is_swapped = true; } } } } int main(void) { int a[N]; int i; srand(time(NULL)); printf("Before:"); for (i = 0; i < N; i++) { a[i] = rand() / (RAND_MAX / (MAX + 1) + 1); printf(" %2d", a[i]); } printf("\n"); comb_sort(N, a); printf("After: "); for (i = 0; i < N; i++) { printf(" %2d", a[i]); } printf("\n"); return 0; } |
実行結果の例は以下になります．
|
1 2 3 4 |
$ gcc comb_sort.c $ a.out Before: 4 15 20 19 33 87 55 73 78 48 After: 4 15 19 20 33 48 55 73 78 87 |
ノームソート
ノームソートは，要素の移動は挿入ではなくバブルソートのような一連の交換で行うソートのアルゴリズムです．
ノームソートの特徴は，とてもシンプルで，入れ子のループが必要としないことです．
バブルソートと同じく安定な内部ソートで，平均計算量は\(\mathcal{O}(n^2)\)，最悪計算量は\(\mathcal{O}(n^2)\)です．
ノームソートのコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <time.h> #define N 10 #define MAX 99 void swap(int *pa, int *pb) { int tmp; tmp = *pa; *pa = *pb; *pb = tmp; } void gnome_sort(int n, int a[]) { int i = 1; while (i < n) { if (a[i - 1] <= a[i]) { i++; } else { swap(&a[i - 1], &a[i]); i--; if (i == 0) { i++; } } } } int main(void) { int a[N]; int i; srand(time(NULL)); printf("Before:"); for (i = 0; i < N; i++) { a[i] = rand() / (RAND_MAX / (MAX + 1) + 1); printf(" %2d", a[i]); } printf("\n"); gnome_sort(N, a); printf("After: "); for (i = 0; i < N; i++) { printf(" %2d", a[i]); } printf("\n"); return 0; } |
実行結果の例は以下になります．
|
1 2 3 4 |
$ gcc gnome_sort.c $ a.out Before: 4 94 70 98 70 15 26 86 44 51 After: 4 15 26 44 51 70 70 86 94 98 |
クイックソート
クイックソートは，分割統治法に基づくソートのアルゴリズムです．
安定ソートではなく，再帰呼び出しによるメモリ利用量は\(\mathcal{O}(\log n)\)（\(\mathcal{O}(n)\)未満）なので定義上は内部ソートです．
クイックソートの名前の通り，平均計算量は\(\mathcal{O}(n \log n)\)と，理論上はほぼ最速なアルゴリズムです．
しかし，対象のデータの並びやデータ数によっては必ずしも速いわけではなく，最悪計算量は\(\mathcal{O}(n^2)\)です．
クイックソートのコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <time.h> #define N 10 #define MAX 99 void swap(int *pa, int *pb) { int tmp; tmp = *pa; *pa = *pb; *pb = tmp; } void quick_sort(int left, int right, int a[]) { int i, last; if (left >= right) { return; } swap(&a[left], &a[(left + right) / 2]); last = left; for (i = left + 1; i <= right; i++) { if (a[i] < a[left]) { swap(&a[++last], &a[i]); } } swap(&a[left], &a[last]); quick_sort(left, last - 1, a); quick_sort(last + 1, right, a); } int main(void) { int a[N]; int i; srand(time(NULL)); printf("Before:"); for (i = 0; i < N; i++) { a[i] = rand() / (RAND_MAX / (MAX + 1) + 1); printf(" %2d", a[i]); } printf("\n"); quick_sort(0, N - 1, a); printf("After: "); for (i = 0; i < N; i++) { printf(" %2d", a[i]); } printf("\n"); return 0; } |
実行結果の例は以下になります．
|
1 2 3 4 |
$ gcc quick_sort.c $ a.out Before: 14 98 67 70 40 4 21 43 59 63 After: 4 14 21 40 43 59 63 67 70 98 |
標準ライブラリでクイックソートが実行できるqsort/qsort_r関数の使い方を知りたいあなたはこちらからどうぞ．
選択ソートのアルゴリズム
選択ソートのアルゴリズムを紹介していきます．
選択ソート
選択ソートは，配列から最小値を探し，配列の先頭要素と入れ替えていくことで並べ替えるソートアルゴリズムです．
選択ソートは，一般的には不安定ソートですが，安定ソートとして実装可能です．
また，内部ソートで，平均計算量と最悪計算量は両方とも\(\mathcal{O}(n^2)\)です．
選択ソートのコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <time.h> #define N 10 #define MAX 99 void swap(int *pa, int *pb) { int tmp; tmp = *pa; *pa = *pb; *pb = tmp; } void selection_sort(int n, int a[]) { int i, j, min; for (i = 0; i < n; i++) { min = i; for (j = i + 1; j < n; j++) { if (a[j] < a[min]) { min = j; } } swap(&a[i], &a[min]); } } int main(void) { int a[N]; int i; srand(time(NULL)); printf("Before:"); for (i = 0; i < N; i++) { a[i] = rand() / (RAND_MAX / (MAX + 1) + 1); printf(" %2d", a[i]); } printf("\n"); selection_sort(N, a); printf("After: "); for (i = 0; i < N; i++) { printf(" %2d", a[i]); } printf("\n"); return 0; } |
実行結果の例は以下になります．
|
1 2 3 4 |
$ gcc selection_sort.c $ a.out Before: 33 64 12 71 88 78 38 71 78 22 After: 12 22 33 38 64 71 71 78 78 88 |
ヒープソート
ヒープソートは，配列の要素を2分ヒープ木で並び替えるソートのアルゴリズムです．
安定ソートではなく，内部ソートで，平均計算量と最悪計算量は両方とも\(\mathcal{O}(n \log n)\)です．
ヒープソートのコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <time.h> #define N 10 #define MAX 99 void swap(int *pa, int *pb) { int tmp; tmp = *pa; *pa = *pb; *pb = tmp; } void heapify(int n, int i, int a[]) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && a[left] > a[largest]) { largest = left; } if (right < n && a[right] > a[largest]) { largest = right; } if (largest != i) { swap(&a[i], &a[largest]); heapify(n, largest, a); } } void heap_sort(int n, int a[]) { int i; for (i = n / 2 - 1; i >= 0; i--) { heapify(n, i, a); } for (i = n - 1; i >= 0; i--) { swap(&a[0], &a[i]); heapify(i, 0, a); } } int main(void) { int a[N]; int i; srand(time(NULL)); printf("Before:"); for (i = 0; i < N; i++) { a[i] = rand() / (RAND_MAX / (MAX + 1) + 1); printf(" %2d", a[i]); } printf("\n"); heap_sort(N, a); printf("After: "); for (i = 0; i < N; i++) { printf(" %2d", a[i]); } printf("\n"); return 0; } |
実行結果の例は以下になります．
|
1 2 3 4 |
$ gcc heap_sort.c $ a.out Before: 13 38 37 16 86 74 23 51 20 18 After: 13 16 18 20 23 37 38 51 74 86 |
挿入ソートのアルゴリズム
挿入ソートのアルゴリズムを紹介していきます．
挿入ソート
挿入ソート（基本挿入法）は，整列してある配列に追加要素を適切な場所に挿入するソートアルゴリズムです．
安定な内部ソートで，平均計算量と最悪計算量は両方とも\(\mathcal{O}(n^2)\)です．
挿入ソートのコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <time.h> #define N 10 #define MAX 99 void swap(int *pa, int *pb) { int tmp; tmp = *pa; *pa = *pb; *pb = tmp; } void insertion_sort(int n, int a[]) { int i = 1, j; while (i < n) { j = i; while (j > 0 && a[j - 1] > a[j]) { swap(&a[j - 1], &a[j]); j--; } i++; } } int main(void) { int a[N]; int i; srand(time(NULL)); printf("Before:"); for (i = 0; i < N; i++) { a[i] = rand() / (RAND_MAX / (MAX + 1) + 1); printf(" %2d", a[i]); } printf("\n"); insertion_sort(N, a); printf("After: "); for (i = 0; i < N; i++) { printf(" %2d", a[i]); } printf("\n"); return 0; } |
実行結果の例は以下になります．
|
1 2 3 4 |
$ gcc insertion_sort.c $ a.out Before: 23 33 97 55 7 88 60 54 10 95 After: 7 10 23 33 54 55 60 88 95 97 |
シェルソート
シェルソート（改良挿入ソート）は，挿入ソートの一般化です．
配列の中である程度間隔hが離れた要素の組ごとに挿入ソートを行い，間隔hを小さくしながら同様のソートを繰り返すことで高速化するアルゴリズムです．
挿入ソートとは異なり安定ソートではないですが，挿入ソートと同様に内部ソートになります．
平均計算量は\(\mathcal{O}(n \log n)\)，最悪計算量は\(\mathcal{O}(\geq n^{1.5})\)です．
※最悪計算量の正確な解析は未解決問題です．
シェルソートのコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <time.h> #define N 10 #define MAX 99 void swap(int *pa, int *pb) { int tmp; tmp = *pa; *pa = *pb; *pb = tmp; } void shell_sort(int n, int a[]) { int h = 13; int i, j; while (h < n) { h = 3 * h + 1; } for (h /= 9; h > 0; h /= 3) { for (i = h; i < n; i++) { j = i; while ((j > h - 1) && (a[j - h] > a[j])) { swap(&a[j - h], &a[j]); j -= h; } } } } int main(void) { int a[N]; int i; srand(time(NULL)); printf("Before:"); for (i = 0; i < N; i++) { a[i] = rand() / (RAND_MAX / (MAX + 1) + 1); printf(" %2d", a[i]); } printf("\n"); shell_sort(N, a); printf("After: "); for (i = 0; i < N; i++) { printf(" %2d", a[i]); } printf("\n"); return 0; } |
実行結果の例は以下になります．
|
1 2 3 4 |
$ gcc shell_sort.c $ a.out Before: 57 30 45 97 76 29 32 90 31 26 After: 26 29 30 31 32 45 57 76 90 97 |
マージソートのアルゴリズム
マージソートのアルゴリズムを紹介していきます．
マージソート
マージソートは，既に整列してある複数の列を1個の列にマージする際，小さいものから先に新しい列に並べれば，新しい列も整列されている（ボトムアップの分割統治法）によるソートのアルゴリズムです．
大きい列を複数の列に分割する処理はクイックソートと同様で，マージする処理は並列化できます．
マージソートは安定ソートですが，一般的には\(\mathcal{O}(n)\)の外部メモリを必要とするので外部ソートになります．
平均計算量と最悪計算量は両方とも\(\mathcal{O}(n \log n)\)です．
マージソートのコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <time.h> #define N 10 #define MAX 99 void merge(int left, int mid, int right, int dst[], int src[]) { int i = left; int j = mid; int k = 0; int l; while ((i < mid) && (j < right)) { if (src[i] <= src[j]) { dst[k++] = src[i++]; } else { dst[k++] = src[j++]; } } if (i == mid) { while (j < right) { dst[k++] = src[j++]; } } else { while (i < mid) { dst[k++] = src[i++]; } } for (l = 0; l < k; l++) { src[left + l] = dst[l]; } } void merge_sort(int left, int right, int dst[], int src[]) { int mid; if ((left == right) || (left == right - 1)) { return; } mid = (left + right) / 2; merge_sort(left, mid, dst, src); merge_sort(mid, right, dst, src); merge(left, mid, right, dst, src); } int main(void) { int src[N], dst[N]; int i; srand(time(NULL)); printf("Before:"); for (i = 0; i < N; i++) { src[i] = rand() / (RAND_MAX / (MAX + 1) + 1); printf(" %2d", src[i]); } printf("\n"); merge_sort(0, N, dst, src); printf("After: "); for (i = 0; i < N; i++) { printf(" %2d", dst[i]); } printf("\n"); return 0; } |
実行結果の例は以下になります．
|
1 2 3 4 |
$ gcc merge_sort.c $ a.out Before: 23 34 50 66 48 59 88 53 1 17 After: 1 17 23 34 48 50 53 59 66 88 |
非比較ソートのアルゴリズム
非比較ソートのアルゴリズムを紹介していきます．
分布数えソート
分布数えソートは，バケットソート（バケツソート，ビンソート）を基にした非比較ソートのアルゴリズムです．
バケットソートの実装方法は，主に以下の2種類があります．
- 可変個の要素を保持できるデータ構造を利用する方法
- 配列のデータを走査して値ごとの分布（出現回数）を数えて，それに応じて一つの配列の中を値ごとに分割する方法（分布数えソート）
1の方法は，C言語には可変個の要素を保持できるデータ構造がなく（realloc関数を利用する必要があり），実装が複雑になります．
※C++言語には可変個の要素を保持できるデータ構造（std::vector等）があるので実装は簡単です．
そこで，2の実装方法である分布数えソートをC言語で紹介します．
分布数えソートは安定な内部ソートで，平均計算量と最悪計算量は両方とも\(\mathcal{O}(n + 2^k)\)（kはバケットの個数）です．
分布数えソートに相当する結果をヒストグラムで表示する方法を知りたいあなたはこちらからどうぞ．
分布数えソートのコードは以下になります．（入力は0～MAXの整数を仮定しています．）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <time.h> #define N 10 #define MAX 99 void counting_sort(int n, int a[]) { int output[n]; int i, count[MAX + 1]; for (i = 0; i < MAX + 1; i++) { count[i] = 0; } for (i = 0; i < n; i++) { count[a[i]]++; } for (i = 1; i < MAX + 1; i++) { count[i] += count[i - 1]; } for (i = n - 1; i >= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; } for (i = 0; i < n; i++) { a[i] = output[i]; } } int main(void) { int a[N]; int i; srand(time(NULL)); printf("Before:"); for (i = 0; i < N; i++) { a[i] = rand() / (RAND_MAX / (MAX + 1) + 1); printf(" %2d", a[i]); } printf("\n"); counting_sort(N, a); printf("After: "); for (i = 0; i < N; i++) { printf(" %2d", a[i]); } printf("\n"); return 0; } |
実行結果の例は以下になります．
|
1 2 3 4 |
$ gcc counting_sort.c $ a.out Before: 23 33 40 51 51 6 46 49 71 90 After: 6 23 33 40 46 49 51 51 71 90 |
基数ソート
基数ソートは，非比較ソートのアルゴリズムの1つです．
基数はソートには，（LSD：Least Significant Digit）基数ソートと（MSD：Most Significant Digit）基数ソートがあります．
LSD基数ソートは，位取り記数法で表現可能な対象について最下位の桁から順番にソートし，最後に最上位桁でソートすると全体が順序通りに並ぶ手法です．
これに対して，MSD基数ソートは，最上位桁から順番にソートし，最後に最下位桁でソートします．
本記事では，LSD基数ソートを紹介します．
LSD基数ソートは安定ですがメモリ利用量が\(\mathcal{O}(n)\)の外部ソートで，平均計算量と最悪計算量は両方とも\(\mathcal{O}(nk)\)（kは桁数）です．
LSD基数ソートのコードは以下になります．（入力は非負の整数を仮定，分布数えソートを基にして実装しています．）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <time.h> #define N 10 #define MAX 99 int get_max(int n, int a[]) { int max = a[0]; int i; for (i = 1; i < n; i++) { if (a[i] > max) { max = a[i]; } } return max; } void counting_sort(int exp, int n, int a[]) { int output[n]; int i, count[n]; for (i = 0; i < n; i++) { count[i] = 0; } for (i = 0; i < n; i++) { count[(a[i] / exp) % 10]++; } for (i = 1; i < n; i++) { count[i] += count[i - 1]; } for (i = n - 1; i >= 0; i--) { output[count[(a[i] / exp) % 10] - 1] = a[i]; count[(a[i] / exp) % 10]--; } for (i = 0; i < n; i++) { a[i] = output[i]; } } void radix_sort(int n, int a[]) { int m = get_max(n, a); int exp; for (exp = 1; (m / exp) > 0; exp *= 10) { counting_sort(exp, n, a); } } int main(void) { int a[N]; int i; srand(time(NULL)); printf("Before:"); for (i = 0; i < N; i++) { a[i] = rand() / (RAND_MAX / (MAX + 1) + 1); printf(" %2d", a[i]); } printf("\n"); radix_sort(N, a); printf("After: "); for (i = 0; i < N; i++) { printf(" %2d", a[i]); } printf("\n"); return 0; } |
実行結果の例は以下になります．
|
1 2 3 4 |
$ gcc radix_sort.c $ a.out Before: 45 89 18 29 97 76 77 86 30 29 After: 18 29 29 30 45 76 77 86 89 97 |
混成ソートのアルゴリズム
混成ソートのアルゴリズムを紹介していきます．
イントロソート
イントロソートは，ヒープソートとクイックソートを組み合わせたソートアルゴリズムです（挿入ソートを含む場合あり）．
イントロソートは，再帰の深さによって以下のソートを切り替えます．
- 再帰の深さが16未満の場合：挿入ソート
- 再帰の深さがソートされた要素数（の対数）を超える場合：ヒープソート
- それ以外の場合：クイックソート
クイックソートと同様に，イントロソートは不安定な内部ソート（メモリ利用量が\(\mathcal{O}(\log n)\)）です．
ヒープソートと同様に，平均計算量と最悪計算量は両方とも\(\mathcal{O}(n \log n)\)です．
イントロソートのコードは以下になります．
※他のソートとは異なり，Nを100，MAXを999に設定しています．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <time.h> #include <math.h> #define N 100 #define MAX 999 #define PARTITION_SIZE 16 void swap(int *pa, int *pb) { int tmp; tmp = *pa; *pa = *pb; *pb = tmp; } void insertion_sort(int n, int a[]) { int i = 1, j; while (i < n) { j = i; while (j > 0 && a[j - 1] > a[j]) { swap(&a[j - 1], &a[j]); j--; } i++; } } void heapify(int n, int i, int a[]) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && a[left] > a[largest]) { largest = left; } if (right < n && a[right] > a[largest]) { largest = right; } if (largest != i) { swap(&a[i], &a[largest]); heapify(n, largest, a); } } void heap_sort(int n, int a[]) { int i; for (i = n / 2 - 1; i >= 0; i--) { heapify(n, i, a); } for (i = n - 1; i >= 0; i--) { swap(&a[0], &a[i]); heapify(i, 0, a); } } void quick_sort(int left, int right, int a[]) { int i, last; if (left >= right) { return; } swap(&a[left], &a[(left + right) / 2]); last = left; for (i = left + 1; i <= right; i++) { if (a[i] < a[left]) { swap(&a[++last], &a[i]); } } swap(&a[left], &a[last]); quick_sort(left, last - 1, a); quick_sort(last + 1, right, a); } int partition(int left, int right, int a[]) { int pivot = a[right]; int i = left, j; for (j = left; j < right; j++) { if (a[j] <= pivot) { swap(&a[j], &a[i]); i++; } } a[right] = a[i]; a[i] = pivot; return i; } void intro_sort(int n, int a[]) { int size = partition(0, n - 1, a); if (size < PARTITION_SIZE) { insertion_sort(n, a); } else if (size > 2 * log(n)) { heap_sort(n, a); } else { quick_sort(0, n - 1, a); } } int main(void) { int a[N]; int i; srand(time(NULL)); printf("Before:"); for (i = 0; i < N; i++) { a[i] = rand() / (RAND_MAX / (MAX + 1) + 1); printf(" %3d", a[i]); } printf("\n"); intro_sort(N, a); printf("After: "); for (i = 0; i < N; i++) { printf(" %3d", a[i]); } printf("\n"); return 0; } |
実行結果の例は以下になります．
GCCのオプションに-lmが必要ですのでつけ忘れないように注意して下さい．
横に長いのでスクロールして下さい．
|
1 2 3 4 |
$ gcc intro_sort.c -lm $ a.out Before: 351 557 546 15 214 569 840 187 893 248 360 367 543 898 577 827 531 876 389 839 529 966 273 382 658 321 104 775 942 964 142 293 521 688 309 735 257 149 922 151 398 283 518 941 181 96 768 712 972 158 551 502 124 825 885 783 147 989 558 89 954 700 383 475 389 692 211 647 842 134 798 240 417 317 182 598 413 951 310 385 109 862 888 234 687 773 18 834 763 576 924 717 277 307 192 666 0 403 313 843 After: 0 15 18 89 96 104 109 124 134 142 147 149 151 158 181 182 187 192 211 214 234 240 248 257 273 277 283 293 307 309 310 313 317 321 351 360 367 382 383 385 389 389 398 403 413 417 475 502 518 521 529 531 543 546 551 557 558 569 576 577 598 647 658 666 687 688 692 700 712 717 735 763 768 773 775 783 798 825 827 834 839 840 842 843 862 876 885 888 893 898 922 924 941 942 951 954 964 966 972 989 |
ティムソート
ティムソートは，マージソートと挿入ソートを組み合わせたソートアルゴリズムです．
ティムソートは，Python言語（バージョン2.3以降），Java SE 7，Androidプラットフォーム，Rust言語等で採用されています．
ティムソートは安定ですがメモリ利用量が\(\mathcal{O}(n)\)の外部ソートで，平均計算量と最悪計算量は両方とも\(\mathcal{O}(n \log n)\)です．
マージは配列数が2のべき乗に等しいか，それよりわずかに少ない場合が最も効率的です．
また，ティムソートでは配列数が2のべき乗よりわずかに多い場合は特に効率が低いため，MINRUN（32から64までの範囲から選択）を設定して事前状態を確認します．
ティムソートのコードは以下になります．
※MINRUNを32に設定するため，他のソートとは異なり，Nを100，MAXを999に設定しています．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <time.h> #define N 100 #define MAX 999 #define MIN(a, b) ((a) < (b) ? (a) : (b)) #define MINRUN 32 void insertion_sort(int left, int right, int a[]) { int i, j; int tmp; for (i = left + 1; i <= right; i++) { tmp = a[i]; j = i - 1; while (j >= left && a[j] > tmp) { a[j + 1] = a[j]; j--; } a[j + 1] = tmp; } } void merge_sort(int left, int mid, int right, int a[]) { int len1 = mid - left + 1, len2 = right - mid; int left_a[len1], right_a[len2]; int i, j, k; for (i = 0; i < len1; i++) { left_a[i] = a[left + i]; } for (i = 0; i < len2; i++) { right_a[i] = a[mid + 1 + i]; } i = j = 0; k = left; while (i < len1 && j < len2) { if (left_a[i] <= right_a[j]) { a[k] = left_a[i]; i++; } else { a[k] = right_a[j]; j++; } k++; } while (i < len1) { a[k] = left_a[i]; k++; i++; } while (j < len2) { a[k] = right_a[j]; k++; j++; } } void tim_sort(int n, int a[]) { int i; int size; int left, mid, right; for (i = 0; i < n; i += MINRUN) { insertion_sort(i, MIN(i + MINRUN - 1, n - 1), a); } for (size = MINRUN; size < n; size *= 2) { for (left = 0; left < n; left += 2 * size) { mid = left + size - 1; right = MIN(left + 2 * size - 1, n - 1); if (mid < right) { merge_sort(left, mid, right, a); } } } } int main(void) { int a[N]; int i; srand(time(NULL)); printf("Before:"); for (i = 0; i < N; i++) { a[i] = rand() / (RAND_MAX / (MAX + 1) + 1); printf(" %3d", a[i]); } printf("\n"); tim_sort(N, a); printf("After: "); for (i = 0; i < N; i++) { printf(" %3d", a[i]); } printf("\n"); return 0; } |
実行結果の例は以下になります．
横に長いのでスクロールして下さい．
|
1 2 3 4 |
$ gcc tim_sort.c $ a.out Before: 112 161 543 683 225 783 899 762 672 308 136 59 38 457 209 387 221 785 692 528 521 827 845 167 687 376 649 390 387 98 794 499 259 337 183 484 121 82 246 793 390 382 852 428 839 61 815 60 847 508 589 368 336 434 536 23 810 185 414 198 283 208 697 542 545 880 26 666 962 273 460 353 655 312 781 495 374 597 556 221 106 145 590 442 580 126 465 391 312 880 589 596 88 286 139 634 167 166 301 129 After: 23 26 38 59 60 61 82 88 98 106 112 121 126 129 136 139 145 161 166 167 167 183 185 198 208 209 221 221 225 246 259 273 283 286 301 308 312 312 336 337 353 368 374 376 382 387 387 390 390 391 414 428 434 442 457 460 465 484 495 499 508 521 528 536 542 543 545 556 580 589 589 590 596 597 634 649 655 666 672 683 687 692 697 762 781 783 785 793 794 810 815 827 839 845 847 852 880 880 899 962 |
まとめ
C言語で配列の要素を並び替えるソートアルゴリズムを紹介しました．
本記事で紹介したソートアルゴリズムをまとめると下表になります（nは並び替える配列の要素数）．
| ソート | 手法 | 安定性 | メモリ利用量 | 平均計算量 | 最悪計算量 |
|---|---|---|---|---|---|
| バブルソート | 交換 | 安定 | \(\mathcal{O}(1)\) | \(\mathcal{O}(n^2)\) | \(\mathcal{O}(n^2)\) |
| シェーカーソート | 交換 | 安定 | \(\mathcal{O}(1)\) | \(\mathcal{O}(n^2)\) | \(\mathcal{O}(n^2)\) |
| 奇偶転置ソート | 交換 | 安定 | \(\mathcal{O}(1)\) | \(\mathcal{O}(n^2)\) | \(\mathcal{O}(n^2)\) |
| コムソート | 交換 | 不安定 | \(\mathcal{O}(1)\) | \(\mathcal{O}(n \log n)\) | \(\mathcal{O}(n^2)\) |
| ノームソート | 交換 | 安定 | \(\mathcal{O}(1)\) | \(\mathcal{O}(n^2)\) | \(\mathcal{O}(n^2)\) |
| クイックソート | 交換 | 不安定 | \(\mathcal{O}(\log n)\) | \(\mathcal{O}(n \log n)\) | \(\mathcal{O}(n^2)\) |
| 選択ソート | 選択 | 不安定 | \(\mathcal{O}(1)\) | \(\mathcal{O}(n^2)\) | \(\mathcal{O}(n^2)\) |
| ヒープソート | 選択 | 不安定 | \(\mathcal{O}(1)\) | \(\mathcal{O}(n \log n)\) | \(\mathcal{O}(n \log n)\) |
| 挿入ソート | 挿入 | 安定 | \(\mathcal{O}(1)\) | \(\mathcal{O}(n^2)\) | \(\mathcal{O}(n^2)\) |
| シェルソート | 挿入 | 不安定 | \(\mathcal{O}(1)\) | \(\mathcal{O}(n \log n)\) | \(\mathcal{O}(\geq n ^{1.5})\) |
| マージソート | マージ | 安定 | \(\mathcal{O}(n)\) | \(\mathcal{O}(n \log n)\) | \(\mathcal{O}(n \log n)\) |
| 分布数えソート | 非比較 | 安定 | \(\mathcal{O}(n + 2^k)\) kはバケットの個数 | \(\mathcal{O}(n + 2^k)\) kはバケットの個数 | \(\mathcal{O}(n + 2^k)\) kはバケットの個数 |
| 基数ソート （LSD基数ソート） | 非比較 | 安定 | \(\mathcal{O}(n)\) | \(\mathcal{O}(nk)\) kは桁数 | \(\mathcal{O}(nk)\) kは桁数 |
| イントロソート | 混成 | 不安定 | \(\mathcal{O}(\log n)\) | \(\mathcal{O}(n \log n)\) | \(\mathcal{O}(n \log n)\) |
| ティムソート | 混成 | 安定 | \(\mathcal{O}(n)\) | \(\mathcal{O}(n \log n)\) | \(\mathcal{O}(n \log n)\) |
C言語でマルチコアプロセッサ向け並行ソートアルゴリズムを知りたいあなたはこちらからどうぞ．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
