C LANGUAGE TECHNOLOGY

【C言語】配列の要素を並び替えるソートアルゴリズム

悩んでいる人

C言語で配列の要素を並び替えるソートアルゴリズムを教えて!

こういった悩みにお答えします.

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++Solidity/Vyper,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

こういった私から学べます.

配列の要素を並び替えるソートアルゴリズム

C言語で配列の要素を並び替えるソートアルゴリズムを紹介します.

ここで,安定ソート(ソートが安定する)とは,同じ値のデータのソート前の順序が,ソート後も保存されるソートアルゴリズムのことです.

つまり,ソート途中の各状態において,常に順序関係を保っているという意味になります.

これに対して,不安定ソート(ソートが安定しない)とは,ソート後に保存されないソートアルゴリズムのことです.

また,ソートされるデータの格納領域を変更して処理を進めていくものを内部ソート,ソートされるデータの格納領域以外に\(\mathcal{O}(n)\)(nは並び替える配列の要素数)以上の一時的な記憶領域が必要なソートを外部ソートと呼びます.

それでは,配列の要素を並び替えるソートアルゴリズムを紹介していきます.

交換ソートのアルゴリズム

交換ソートのアルゴリズムを紹介していきます.

バブルソート

バブルソート(単純ソート)は,隣り合う要素の大小を比較しながら整列させるアルゴリズムです.

バブルソートは安定な内部ソートで,平均計算量は\(\mathcal{O}(n^2)\),最悪計算量は\(\mathcal{O}(n^2)\)です.

バブルソートは,処理時間が長く実用性は低いですが,実装はシンプルで理解しやすいです.

まずは,バブルソートのコードを読んで,ソートの概念を学びましょう!

バブルソートのコードは以下になります.

実行結果の例は以下になります.

※乱数の初期値を設定するsrand関数に現在時刻を返すtime関数を利用しているので,実行毎に配列の要素は変わります.他のソートも同様です.

シェーカーソート

シェーカーソート(双方向バブルソート,改良交換法)は,バブルソートを改良したソートのアルゴリズムです.

バブルソートでは一方向にしかスキャンしないのに対して,シェーカーソートでは交互に双方向でスキャンします.

バブルソートと同じく安定な内部ソートで,平均計算量は\(\mathcal{O}(n^2)\),最悪計算量は\(\mathcal{O}(n^2)\)です.

シェーカーソートのコードは以下になります.

実行結果の例は以下になります.

奇偶転置ソート

奇偶転置ソートは,バブルソートを改良したソートアルゴリズムです.

バブルソートではスキャンを一方向に順次行うのに対し,奇偶転置ソートでは組ごとにスキャンします.

バブルソートと同じく安定な内部ソートで,平均計算量は\(\mathcal{O}(n^2)\),最悪計算量は\(\mathcal{O}(n^2)\)です.

奇偶転置ソートのコードは以下になります.

実行結果の例は以下になります.

コムソート

コムソート(櫛(くし)ソート)は,バブルソートを改良したソートのアルゴリズムです.

バブルソートとは異なり,コムソートは不安定なソートです.

また,内部ソートで,平均計算時間は\(\mathcal{O}(n \log n)\),最悪計算時間は\(\mathcal{O}(n^2)\)です.

コムソートのコードは以下になります.

実行結果の例は以下になります.

ノームソート

ノームソートは,要素の移動は挿入ではなくバブルソートのような一連の交換で行うソートのアルゴリズムです.

ノームソートの特徴は,とてもシンプルで,入れ子のループが必要としないことです.

バブルソートと同じく安定な内部ソートで,平均計算量は\(\mathcal{O}(n^2)\),最悪計算量は\(\mathcal{O}(n^2)\)です.

ノームソートのコードは以下になります.

実行結果の例は以下になります.

クイックソート

クイックソートは,分割統治法に基づくソートのアルゴリズムです.

安定ソートではなく,再帰呼び出しによるメモリ利用量は\(\mathcal{O}(\log n)\)(\(\mathcal{O}(n)\)未満)なので定義上は内部ソートです.

クイックソートの名前の通り,平均計算量は\(\mathcal{O}(n \log n)\)と,理論上はほぼ最速なアルゴリズムです.

しかし,対象のデータの並びやデータ数によっては必ずしも速いわけではなく,最悪計算量は\(\mathcal{O}(n^2)\)です.

クイックソートのコードは以下になります.

実行結果の例は以下になります.

標準ライブラリでクイックソートが実行できるqsort/qsort_r関数の使い方を知りたいあなたはこちらからどうぞ.

C言語 qsort関数
【C言語】qsort/qsort_r関数の使い方

こういった悩みにお答えします. こういった私から学べます. 目次1 qsort関数1.1 qsort関数の使い方1.2 qsort関数の問題点2 qsort_r関数3 まとめ qsort関数 [cra ...

続きを見る

選択ソートのアルゴリズム

選択ソートのアルゴリズムを紹介していきます.

選択ソート

選択ソートは,配列から最小値を探し,配列の先頭要素と入れ替えていくことで並べ替えるソートアルゴリズムです.

選択ソートは,一般的には不安定ソートですが,安定ソートとして実装可能です.

また,内部ソートで,平均計算量と最悪計算量は両方とも\(\mathcal{O}(n^2)\)です.

選択ソートのコードは以下になります.

実行結果の例は以下になります.

ヒープソート

ヒープソートは,配列の要素を2分ヒープ木で並び替えるソートのアルゴリズムです.

安定ソートではなく,内部ソートで,平均計算量と最悪計算量は両方とも\(\mathcal{O}(n \log n)\)です.

ヒープソートのコードは以下になります.

実行結果の例は以下になります.

挿入ソートのアルゴリズム

挿入ソートのアルゴリズムを紹介していきます.

挿入ソート

挿入ソート(基本挿入法)は,整列してある配列に追加要素を適切な場所に挿入するソートアルゴリズムです.

安定な内部ソートで,平均計算量と最悪計算量は両方とも\(\mathcal{O}(n^2)\)です.

挿入ソートのコードは以下になります.

実行結果の例は以下になります.

シェルソート

シェルソート(改良挿入ソート)は,挿入ソートの一般化です.

配列の中である程度間隔hが離れた要素の組ごとに挿入ソートを行い,間隔hを小さくしながら同様のソートを繰り返すことで高速化するアルゴリズムです.

挿入ソートとは異なり安定ソートではないですが,挿入ソートと同様に内部ソートになります.

平均計算量は\(\mathcal{O}(n \log n)\),最悪計算量は\(\mathcal{O}(\geq n^{1.5})\)です.

※最悪計算量の正確な解析は未解決問題です.

シェルソートのコードは以下になります.

実行結果の例は以下になります.

マージソートのアルゴリズム

マージソートのアルゴリズムを紹介していきます.

マージソート

マージソートは,既に整列してある複数の列を1個の列にマージする際,小さいものから先に新しい列に並べれば,新しい列も整列されている(ボトムアップの分割統治法)によるソートのアルゴリズムです.

大きい列を複数の列に分割する処理はクイックソートと同様で,マージする処理は並列化できます.

マージソートは安定ソートですが,一般的には\(\mathcal{O}(n)\)の外部メモリを必要とするので外部ソートになります.

平均計算量と最悪計算量は両方とも\(\mathcal{O}(n \log n)\)です.

マージソートのコードは以下になります.

実行結果の例は以下になります.

非比較ソートのアルゴリズム

非比較ソートのアルゴリズムを紹介していきます.

分布数えソート

分布数えソートは,バケットソート(バケツソート,ビンソート)を基にした非比較ソートのアルゴリズムです.

バケットソートの実装方法は,主に以下の2種類があります.

  1. 可変個の要素を保持できるデータ構造を利用する方法
  2. 配列のデータを走査して値ごとの分布(出現回数)を数えて,それに応じて一つの配列の中を値ごとに分割する方法(分布数えソート)

1の方法は,C言語には可変個の要素を保持できるデータ構造がなく(realloc関数を利用する必要があり),実装が複雑になります.

※C++言語には可変個の要素を保持できるデータ構造(std::vector等)があるので実装は簡単です.

そこで,2の実装方法である分布数えソートをC言語で紹介します.

分布数えソートは安定な内部ソートで,平均計算量と最悪計算量は両方とも\(\mathcal{O}(n + 2^k)\)(kはバケットの個数)です.

分布数えソートのコードは以下になります.(入力は0~MAXの整数を仮定しています.)

実行結果の例は以下になります.

基数ソート

基数ソートは,非比較ソートのアルゴリズムの1つです.

基数はソートには,(LSD:Least Significant Digit)基数ソートと(MSD:Most Significant Digit)基数ソートがあります.

LSD基数ソートは,位取り記数法で表現可能な対象について最下位の桁から順番にソートし,最後に最上位桁でソートすると全体が順序通りに並ぶ手法です.

これに対して,MSD基数ソートは,最上位桁から順番にソートし,最後に最下位桁でソートします.

本記事では,LSD基数ソートを紹介します.

LSD基数ソートは安定ですがメモリ利用量が\(\mathcal{O}(n)\)の外部ソートで,平均計算量と最悪計算量は両方とも\(\mathcal{O}(nk)\)(kは桁数)です.

LSD基数ソートのコードは以下になります.(入力は非負の整数を仮定,分布数えソートを基にして実装しています.)

実行結果の例は以下になります.

混成ソートのアルゴリズム

混成ソートのアルゴリズムを紹介していきます.

イントロソート

イントロソートは,ヒープソートとクイックソートを組み合わせたソートアルゴリズムです(挿入ソートを含む場合あり).

イントロソートは,再帰の深さによって以下のソートを切り替えます.

  • 再帰の深さが16未満の場合:挿入ソート
  • 再帰の深さがソートされた要素数(の対数)を超える場合:ヒープソート
  • それ以外の場合:クイックソート

クイックソートと同様に,イントロソートは不安定な内部ソート(メモリ利用量が\(\mathcal{O}(\log n)\))です.

ヒープソートと同様に,平均計算量と最悪計算量は両方とも\(\mathcal{O}(n \log n)\)です.

イントロソートのコードは以下になります.

※他のソートとは異なり,Nを100,MAXを999に設定しています.

実行結果の例は以下になります.

GCCのオプションに-lmが必要ですのでつけ忘れないように注意して下さい.

横に長いのでスクロールして下さい.

ティムソート

ティムソートは,マージソートと挿入ソートを組み合わせたソートアルゴリズムです.

ティムソートは,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に設定しています.

実行結果の例は以下になります.

横に長いのでスクロールして下さい.

まとめ

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言語】マルチコアプロセッサ向け並行ソートアルゴリズム

こういった悩みにお答えします. こういった私から学べます. 目次1 C言語でマルチコアプロセッサ向けソートアルゴリズム2 並行マージソート3 並行クイックソート4 並行分布数えソート5 バイトニックソ ...

続きを見る

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

-C LANGUAGE, TECHNOLOGY
-, , , , , ,