C LANGUAGE TECHNOLOGY

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

2021年12月12日

悩んでいる人

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

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

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOS(Linuxカーネル)の授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校(UNC)コンピュータサイエンス学部で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発.
  • プログラミング歴15年以上,習得している言語: C/C++PythonSolidity/Vyper,Java,Ruby,Go,Rust,D,HTML/CSS/JS/PHP,MATLAB,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)\)です.

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

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

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

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

※乱数の初期値を設定する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関数の使い方を知りたいあなたはこちらからどうぞ.

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

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

選択ソート

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

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

また,内部ソートで,平均計算量と最悪計算量は両方とも\(\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言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

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

友だち追加

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

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