C言語の非数値計算でよく使われる5つの古典的なソートアルゴリズム

概要: ソートとは、一連の「順序付けられていない」レコードシーケンスを「順序付けられた」レコードシーケンスに調整することを目的としたコンピュータ操作方法であり、主に内部ソートと外部ソートに分けられます。

ソート

ソートとは、一連の「順序のない」レコードシーケンスを「順序のある」レコードシーケンスに調整することを目的としたコンピュータ操作方法であり、主に内部ソートと外部ソートに分けられます。

（１）バブルソート

バブルソートの基本的な考え方は、ソートする要素列のセットに対して、2 つの隣接する数値を順番に比較し、小さい方の数値を前に、大きい方の数値を後ろに置き、最後の 2 つの数値を比較するまでこれを続け、小さい方の数値を前に、大きい方の数値を後ろに置き、すべての数値がソートされるまでこの手順を繰り返すというものです。

利点: 安定している;

欠点: 速度が遅く、一度に 2 つの隣接するデータしか移動できません。

n 個の数値を含むシーケンスを昇順で並べ替えると仮定すると、バブルソートアルゴリズムの手順は次のようになります。

① シーケンスを格納する配列の最初の要素から最後の要素まで、隣接する 2 つの数値を順番に比較します。前者が後者よりも大きい場合は、2 つの数値の位置を交換します。

②1回目の比較後、最大の数字は配列の最後の要素に格納されます。次に、最初の要素から最後から2番目の要素まで、隣接する2つの数字を順番に比較します。前者が後者よりも大きい場合は、2つの数字の位置が入れ替わります。

③ 手順①を n-1 回繰り返し、各ラウンドで前回よりも 1 つ少ない比較を実行すると、目的が達成されます。

1. 10個の整数をランダムに読み込み、バブル法で昇順に並べて出力します。

2. 伝統的な方法:

（２）選択方法の分類

選択ソート法では、n-i+1 ( i=1 , 2 , …n-1 ) 個のレコードから、最小のキーワードを持つレコードを毎回順序付けられたシーケンスのi番目のレコードとして選択します。この考え方に基づくアルゴリズムには、主に単純選択ソート、ツリー選択ソート、ヒープソートなどがあります。

利点: データが移動される回数がわかっている (n-1 回)。

デメリット: 比較が多く、不安定。

選択ソートは比較的理解しやすいソートアルゴリズムです。 n 個の数値のシーケンスを昇順に並べ替えるとします。アルゴリズムの手順は次のようになります。

① 配列に格納されている n 個の数値から最小の数値の添え字を見つけ（アルゴリズムについては、以下の「最小値を見つける」を参照）、最小の数値を最初の数値と交換します。

②最初の数字を除いて、残りのn-1個の数字から最小の数字（つまりn個の数字の中で2番目に小さい数字）の添え字を探し、この数字の位置を2番目の数字と入れ替えます。

③手順①をn-1回繰り返して、目的の結果を達成します。

1. 10個の整数をランダムに読み込み、選択法を使って昇順に並べて出力します。

2. 伝統的な方法:

関数メソッド:

（３）挿入ソート

利点: 安定していて高速です。

デメリット: 比較の回数は固定ではありません。比較の回数が増えるほど、挿入ポイントの後に移動するデータが増えます。特に、データの総量が膨大な場合はそうです。ただし、この問題はリンクリストを使用することで解決できます。

このアルゴリズムを習得するには、まず「順序付きシーケンス挿入アルゴリズム」を理解してください。つまり、順序付きシーケンスに特定のデータを挿入した後、シーケンスは順序付きのままになります。挿入アルゴリズムについては、以下の「配列要素の挿入」を参照してください。

1. 任意の整数 x を昇順のシーケンスに挿入した後、シーケンスは昇順のままになります。

挿入方式によるソートの鍵は、読み取った各数値を最終配列にすぐに挿入し、挿入するたびに配列が順序付けられることです。

2. 10個の整数をランダムに読み込み、挿入法を使って降順で並べて出力します。

（4）マージソート

マージソートは、マージ操作に基づいた効果的なソートアルゴリズムです。このアルゴリズムは、分割統治法の非常に典型的な応用です。順序付けられたサブシーケンスをマージして、完全に順序付けられたシーケンスを取得します。つまり、最初に各サブシーケンスを順序付けし、次にサブシーケンスのセグメントを順序付けます。 2 つの順序付きリストが 1 つの順序付きリストに結合される場合は、双方向結合と呼ばれます。

つまり、昇順 (または降順) になっている 2 つのデータシーケンスを、元の順序のまま 1 つのシーケンスにマージします。

1. 6 個のデータを含む昇順シーケンスと 4 個のデータを含む昇順シーケンスがあります。この 2 つを 10 個のデータを含む昇順シーケンスに結合します。