Loading article…
コンピュータサイエンスにおいて、ソートアルゴリズムとは、リストの要素をある順序に並べるアルゴリズムのことです。最もよく使われる順序は、数値順と辞書順、そして昇順または降順です。効率的なソートは、入力データがソート済みのリストであることを必要とする他のアルゴリズム（検索アルゴリズムやマージアルゴリズムなど）の効率を最適化するために重要です。また、ソートはデータの正規化や、人間が読みやすい出力を生成するためにもよく用いられます。
厳密に言えば、あらゆるソートアルゴリズムの出力は、次の2つの条件を満たさなければならない。
一部のアルゴリズムはシーケンシャルアクセス用に設計されているが、最も高性能なアルゴリズムは、データがランダムアクセスを可能にするデータ構造に格納されていることを前提としている。
コンピュータの黎明期から、ソート問題は多くの研究を集めてきました。これは、その単純で馴染みのある記述にもかかわらず、効率的に解決することが複雑であるためかもしれません。1951年頃の初期のソートアルゴリズムの著者の一人に、 ENIACとUNIVACに携わったベティ・ホルバートンがいます。[ 1 ] [ 2 ]バブルソートは1956年には既に分析されていました。[ 3 ]漸近的に最適なアルゴリズムは20世紀半ばから知られており、新しいアルゴリズムは今も発明され続けています。広く使われているTimsortは2002年に、ライブラリソートは2006年に初めて発表されました。
比較ソートアルゴリズムには基本的な要件があります比較に基づかないアルゴリズム、例えばカウントソートなどは、より優れたパフォーマンスを発揮する可能性があります。
ソートアルゴリズムは、コンピュータサイエンスの入門クラスでよく取り上げられます。この問題に対するアルゴリズムが豊富にあるため、ビッグオー記法、分割統治アルゴリズム、ヒープや二分木などのデータ構造、ランダム化アルゴリズム、最良・最悪・平均ケース分析、時間と空間のトレードオフ、上限と下限など、さまざまなコアアルゴリズム概念への穏やかな導入となります。
小さな配列を最適に（比較と交換の回数を最小限に抑えて）ソートすること、あるいは高速に（つまり、マシン固有の詳細を考慮して）ソートすることは、依然として未解決の研究課題であり、解決策が知られているのは非常に小さな配列（20要素未満）に限られています。同様に、並列マシン上での最適な（様々な定義による）ソートも、未解決の研究テーマです。
ソートアルゴリズムは以下のように分類できます。
安定ソートアルゴリズムは、入力された順序と同じ順序で、等しい要素をソートします。たとえば、右側のカードソートの例では、カードはランクでソートされ、スートは無視されます。これにより、元のリストの正しくソートされた複数のバージョンが存在する可能性があります。安定ソートアルゴリズムは、次のルールに従って、これらのうちの1つを選択します。2つの項目が等しいと比較された場合（たとえば、2枚の5のカード）、それらの相対的な順序が保持されます。つまり、入力で一方が他方より前に来る場合、出力でも他方より前に来ます。
同じデータセットに対して複数回ソートを行う際に、順序を維持するためには安定性が重要です。例えば、名前とクラスセクションで構成される学生レコードが、まず名前で、次にクラスセクションで動的にソートされるとします。どちらの場合も安定したソートアルゴリズムを使用すれば、クラスセクションによるソート操作で名前の順序は変わりません。一方、不安定なソートでは、クラスセクションによるソートによって名前の順序が入れ替わり、アルファベット順ではない学生リストになってしまう可能性があります。
より厳密に言うと、ソート対象のデータはレコードまたは値のタプルとして表現でき、ソートに使用されるデータの一部をキーと呼びます。カードの例では、カードはレコード（ランク、スート）として表現され、キーはランクです。ソートアルゴリズムは、同じキーを持つ2つのレコードRとSがあり、元のリストでRがSより前に現れる場合、ソート後のリストでもRが常にSより前に現れる場合に安定していると言えます。
整数などのように、等しい要素が区別できない場合、あるいはより一般的には、要素全体がキーとなるデータの場合、安定性は問題になりません。また、すべてのキーが異なる場合も、安定性は問題になりません。
不安定なソートアルゴリズムは、特別な方法で安定するように実装できます。その方法の一つとして、キー比較を人為的に拡張し、キーが同じ2つのオブジェクト間の比較において、元の入力リストのエントリの順序をタイブレーカーとして使用する方法があります。ただし、この順序を記憶するには、追加の時間とメモリが必要になる場合があります。
安定ソートアルゴリズムの応用例の一つとして、主キーと副キーを用いてリストをソートすることが挙げられます。例えば、トランプのカードを、スートがクラブ（♣）、ダイヤ（♦）、ハート（♥）、スペード（♠）の順で、各スート内でランク順にソートしたいとします。これは、まずカードをランク順にソートし（任意のソートアルゴリズムを使用）、次にスートごとに安定ソートを行うことで実現できます。
各スート内では、安定ソートは既に行われたランク順の順序を維持します。この考え方は任意の数のキーに拡張でき、基数ソートで利用されています。不安定ソートでも、辞書式キー比較を用いることで同様の効果が得られます。例えば、最初にスートで比較し、スートが同じ場合はランクで比較します。
この分析では、各キーの長さは一定であり、すべての比較、交換、その他の操作は一定時間で実行できると仮定しています。
伝説：
以下は比較ソートの表です。数学的分析によると、比較ソートは平均してO ( n log n )よりも優れたパフォーマンスを発揮することはできません。 [ 4 ]
以下の表は、整数ソートアルゴリズムと、比較ソートではないその他のソートアルゴリズムについて説明しています。これらのアルゴリズムは、以下に説明する単位コストランダムアクセスマシンモデルを満たさない限り、 Ω ( n log n )に限定されません。[ 9 ]
Samplesortは、比較ソート以外のあらゆるソート処理を並列化するために使用できます。データを複数のバケットに効率的に分散し、ソート処理を複数のプロセッサに渡すことで、バケット間は既にソートされているため、マージする必要はありません。
上記で説明したアルゴリズムと比較して、実行時間が無制限のボゴソートや、実行時間がO ( n 2.7 ) のストゥージソートなど、遅いアルゴリズムもいくつかあります。これらのソートは通常、アルゴリズムの実行時間がどのように推定されるかを示すために、教育目的で説明されます。次の表は、極めて低いパフォーマンスや特殊なハードウェア要件のために、従来のソフトウェア環境での実用には不向きなソートアルゴリズムをいくつか示しています。
Theoretical computer scientists have invented other sorting algorithms that provide better than O(n log n) time complexity assuming certain constraints, including:
ソートアルゴリズムは数多く存在しますが、実際の実装では少数のアルゴリズムが主流となっています。挿入ソートは小規模なデータセットに広く用いられ、大規模なデータセットには漸近的に効率的なソート、主にヒープソート、マージソート、クイックソートが用いられます。効率的な実装では一般的にハイブリッドアルゴリズムが用いられ、全体的なソートには漸近的に効率的なアルゴリズムを、再帰の最後に小規模なリストに対しては挿入ソートが用いられます。高度に最適化された実装では、Android、Java、Pythonで使用されるTimsort（マージソート、挿入ソート、および追加ロジック）や、一部のC++ソート実装や.NETで（変形版として）使用されるintrosort （クイックソートとヒープソート）など、より洗練されたバリアントが用いられます。
固定区間内の数値など、より制約のあるデータに対しては、計数ソートや基数ソートといった分布ソートが広く用いられます。バブルソートとその派生アルゴリズムは実務ではほとんど使われませんが、教育や理論的な議論ではよく登場します。
物理的にオブジェクトを分類する場合（書類、テスト、書籍などをアルファベット順に並べる場合など）、人々は直感的に、小さなセットには挿入ソートを使用します。より大きなセットの場合、人々はまず頭文字などでバケット分けし、複数のバケット分けを行うことで、非常に大きなセットでも実用的な分類が可能になります。多くの場合、床や広い場所にオブジェクトを広げるなど、スペースは比較的安価ですが、操作、特にオブジェクトを遠くまで移動させる操作はコストがかかります。そのため、参照の局所性が重要になります。マージソートは、特にマージするリストごとに両手を使うことができるため、物理的なオブジェクトにも実用的です。一方、ヒープソートやクイックソートなどの他のアルゴリズムは、人間の使用には適していません。スペースを残す挿入ソートの変種であるライブラリソートなどの他のアルゴリズムも、物理的な使用に実用的です。
最も単純なソートアルゴリズムには、挿入ソートと選択ソートの2種類があり、どちらもオーバーヘッドが少ないため小規模データには効率的ですが、大規模データには効率的ではありません。実際には、比較回数が少なく、ほぼソート済みのデータでも良好なパフォーマンスを発揮するため、挿入ソートの方が一般的に高速です。そのため、実際には挿入ソートが好まれますが、選択ソートは書き込み回数が少ないため、書き込みパフォーマンスがボトルネックとなる場合に使用されます。
挿入ソートは、小さなリストやほとんどソート済みのリストに対して比較的効率的な単純なソートアルゴリズムであり、より高度なアルゴリズムの一部としてよく使用されます。これは、リストから要素を 1 つずつ取り出し、財布にお金を入れるのと同様に、新しいソート済みリストの正しい位置に挿入することで機能します。 [ 17 ]配列では、新しいリストと残りの要素は配列のスペースを共有できますが、挿入はコストがかかり、後続のすべての要素を 1 つずらす必要があります。シェルソートは、より大きなリストに対してより効率的な挿入ソートの変種です。
選択ソートは、インプレース比較ソートの一種です。計算量はO ( n² )であるため、大規模なリストでは非効率であり、一般的に類似の挿入ソートよりもパフォーマンスが劣ります。選択ソートは、そのシンプルさで知られており、特定の状況ではより複雑なアルゴリズムよりもパフォーマンス面で優位性があります。
このアルゴリズムは最小値を見つけ、それを最初の位置の値と交換し、リストの残りの部分に対してこれらの手順を繰り返します。[ 18 ]交換はn回以下なので、交換コストが非常に高い場合に有効です。
実用的な汎用ソートアルゴリズムは、ほぼ例外なく平均時間計算量（および一般的に最悪の場合の計算量）が O( n log n )のアルゴリズムに基づいており、その中で最も一般的なのはヒープソート、マージソート、クイックソートです。それぞれに長所と短所があり、最も大きな欠点は、マージソートの単純な実装では O( n ) の追加スペースが必要であり、クイックソートの単純な実装では最悪の場合の計算量が O( n 2 ) になることです。これらの問題は、より複雑なアルゴリズムを用いることで解決または改善できます。
これらのアルゴリズムはランダムデータに対しては漸近的に効率的ですが、実際のデータに対して実用的な効率性を得るためには、さまざまな修正が用いられます。まず、これらのアルゴリズムのオーバーヘッドはデータサイズが小さいほど大きくなるため、多くの場合、ハイブリッドアルゴリズムが使用され、データが十分に小さくなったら挿入ソートに切り替えます。次に、これらのアルゴリズムは既にソート済みのデータやほぼソート済みのデータに対してはパフォーマンスが低下することがよくあります。これらは実際のデータではよく見られるものであり、適切なアルゴリズムを使用すればO( n )の時間でソートできます。最後に、これらのアルゴリズムは不安定になる場合もあり、ソートにおいては安定性が望ましい特性となることが多いです。そのため、マージソートに基づくTimsortや、クイックソートに基づくintrosort （ヒープソートにフォールバック）など、より高度なアルゴリズムが用いられることがよくあります。
マージソートは、既にソートされたリストを新しいソート済みリストに簡単にマージできるという利点を活用しています。まず、2 つの要素 (1 と 2、次に 3 と 4...) を比較し、最初の要素が 2 番目の要素の後に来る場合はそれらを交換します。次に、結果として得られた 2 つのリストをそれぞれ 4 つのリストにマージし、次にそれらの 4 つのリストをマージし、これを繰り返します。最終的に 2 つのリストがマージされて、最終的なソート済みリストが完成します。[ 19 ]ここで説明したアルゴリズムの中で、これは最悪の場合の実行時間が O( n log n )であるため、非常に大きなリストにもうまく対応できる最初のアルゴリズムです。また、ランダムアクセスではなくシーケンシャルアクセスのみを必要とするため、配列だけでなくリストにも簡単に適用できます。配列をソートする場合、O( n ) の空間計算量が追加され、単純な実装では多数のコピーが必要になります。ただし、リンク リストは一定の追加スペースでマージ ソートできるため、リンク リストをソートするための最適なアルゴリズムです。
マージソートは、プログラミング言語Python [ 20 ]およびJava ( JDK7 [ 21 ]以降) の標準ソートルーチンとして使用されている高度なアルゴリズムTimsortで使用されていることから、実用的な実装において比較的最近人気が急上昇しています。マージソート自体はPerl [ 22 ]などの標準ルーチンであり、Java では少なくとも 2000 年以降のJDK1.3 [ 23 ]で使用されています。
ヒープソートは、選択ソートのより効率的なバージョンです。これもリストの最大（または最小）要素を決定し、それをリストの末尾（または先頭）に配置し、残りのリストの処理を続けることで機能しますが、ヒープと呼ばれるデータ構造、つまり特殊なタイプの二分木を使用することでこのタスクを効率的に実行します。[ 24 ]データリストがヒープになると、ルートノードは最大（または最小）要素であることが保証されます。それが削除されてリストの末尾に配置されると、残りの最大の要素がルートに移動するようにヒープが再配置されます。ヒープを使用すると、次の最大の要素を見つけるのにかかる時間は、単純な選択ソートのように線形スキャンで O(n) かかるのに対し、O(log n) かかります。これにより、ヒープソートは O( n log n ) の時間で実行でき、これは最悪の場合の複雑さでもあります。
クイックソートは分割統治アルゴリズムであり、分割操作に依存しています。配列を分割するために、ピボットと呼ばれる要素が選択されます。[ 25 ] [ 26 ]ピボットより小さいすべての要素はピボットの前に移動され、ピボットより大きいすべての要素はピボットの後に移動します。これは線形時間で効率的にインプレースで実行できます。小さいサブリストと大きいサブリストは再帰的にソートされます。これにより、平均時間計算量はO( n log n )となり、オーバーヘッドが少ないため、これは人気のあるアルゴリズムです。クイックソートの効率的な実装（インプレース分割を使用）は通常不安定なソートであり、やや複雑ですが、実際には最も高速なソートアルゴリズムの1つです。控えめなO(log n )の空間使用量と相まって、クイックソートは最も人気のあるソートアルゴリズムの1つであり、多くの標準プログラミングライブラリで利用できます。
クイックソートに関する重要な注意点は、最悪の場合のパフォーマンスが O( n 2 ) であることです。これはまれなケースですが、単純な実装（最初の要素または最後の要素をピボットとして選択する）では、ソート済みのデータに対して発生します。これはよくあるケースです。したがって、クイックソートで最も複雑な問題は、適切なピボット要素を選択することです。ピボットの選択が常に不適切だと、パフォーマンスが O( n 2 ) と大幅に低下する可能性がありますが、適切なピボットを選択すれば、漸近的に最適な O( n log n ) のパフォーマンスが得られます。たとえば、各ステップで中央値をピボットとして選択すると、アルゴリズムは O( n log n ) で動作します。ただし、中央値の中央値選択アルゴリズムなどによる中央値の探索は、ソートされていないリストに対してO( n ) の操作であり、ソートに伴う大きなオーバーヘッドが発生します。実際には、ランダムなピボットを選択すると、ほぼ確実に O( n log n ) のパフォーマンスが得られます。
O( n log n )のパフォーマンスを保証することが重要であれば、それを実現する簡単な修正方法があります。Musser によるアイデアは、再帰の最大深度に制限を設けることです。[ 27 ]その制限を超えた場合は、ヒープソートアルゴリズムを使用してソートが続行されます。Musser は、制限を次のように提案しました。これは、ランダムに並べられた配列で平均的に予想される最大再帰深度の約2倍です。
シェルソートは1959年にドナルド・シェルによって発明されました。[ 28 ]挿入ソートを改良し、順序が乱れた要素を一度に複数位置移動します。シェルソートの背後にある概念は、挿入ソートは時間は、k が位置がずれた 2 つの要素間の最大距離であることを意味します。これは、一般的にはO ( n 2 ) で実行されることを意味しますが、ほとんどがソートされていて位置がずれた要素がごくわずかしかないデータの場合は、より高速に実行されます。したがって、最初に遠く離れた要素をソートし、ソートする要素間のギャップを徐々に縮小することで、最終的なソートの計算がはるかに高速になります。 1 つの実装は、データ シーケンスを 2 次元配列に配置し、次に挿入ソートを使用して配列の列をソートすることとして説明できます。
Shellsort の最悪時間計算量は未解決問題であり、使用するギャップ シーケンスに依存し、既知の計算量はO ( n 2 )からO ( n 4/3 ) および Θ( n log 2 n ) までです。このことと、Shellsort がインプレースであり、比較的少量のコードしか必要とせず、コール スタックの使用を必要としないという事実を組み合わせると、組み込みシステムやオペレーティングシステムのカーネルなど、メモリが貴重な状況で役立ちます。
バブルソート、およびコームソートやカクテルソートといった派生アルゴリズムは、単純で非常に非効率的なソートアルゴリズムである。分析が容易なため入門書によく登場するが、実際に使用されることは稀である。
バブルソートは単純なソートアルゴリズムです。このアルゴリズムはデータセットの先頭から開始します。最初の 2 つの要素を比較し、最初の要素が 2 番目の要素より大きい場合は、それらを交換します。データセットの末尾まで、隣接する要素の各ペアに対してこれを続けます。その後、最初の 2 つの要素から再び開始し、最後のパスで交換が発生しなくなるまで繰り返します。[ 29 ]このアルゴリズムの平均時間と最悪の場合のパフォーマンスは O( n 2 ) なので、大きな順序付けされていないデータセットのソートにはほとんど使用されません。バブルソートは、少数の項目をソートするために使用できます (漸近的な非効率性が大きなペナルティにならない場合)。バブルソートは、ほぼソートされている任意の長さのリスト (つまり、要素の位置が大きくずれていないリスト) に対しても効率的に使用できます。例えば、任意の数の要素が1つの位置だけずれている場合（例：0123546789と1032547698）、バブルソートの交換によって最初のパスでそれらが正しい順序になり、2回目のパスですべての要素が正しい順序で見つかるため、ソートには2nの時間しかかかりません。
コームソートは、バブルソートに基づく比較的単純なソートアルゴリズムで、元々は1980年にWłodzimierz Dobosiewiczによって設計されました。[ 30 ]後にStephen LaceyとRichard Boxによって再発見され、 1991年4月にByte Magazineに掲載された記事で普及しました。基本的な考え方は、バブルソートではソートを著しく遅くするタートル、つまりリストの末尾付近の小さな値を排除することです。（リストの先頭付近のラビット、大きな値はバブルソートでは問題になりません）これは、配列内で互いに一定の距離にある要素を最初に交換し、次に通常のバブルソートのように動作するまで選択した距離を縮小することによって実現されます。したがって、シェルソートが互いに一定の距離にある要素を交換する挿入ソートの一般化バージョンと考えることができるとすれば、コームソートはバブルソートに同じ一般化を適用したものと考えることができます。
分散ソートとは、入力データが複数の中間構造に分散され、それらが集約されて出力に配置されるソートアルゴリズム全般を指します。例えば、バケットソートとフラッシュソートはどちらも分散型ソートアルゴリズムです。分散ソートアルゴリズムは、単一のプロセッサ上で実行することも、分散アルゴリズムとして実行することもできます。分散アルゴリズムでは、個々のサブセットが異なるプロセッサ上で個別にソートされ、その後結合されます。これにより、単一のコンピュータのメモリに収まらないほど大きなデータを外部でソートすることが可能になります。
計数ソートは、各入力が特定の可能性の集合Sに属することがわかっている場合に適用できます。このアルゴリズムは、O(| S | + n ) の時間で、O(| S |) のメモリで実行されます。ここでnは入力の長さです。このアルゴリズムは、サイズ | S | の整数配列を作成し、 i番目のビンを使用して入力内のSのi番目の要素の出現回数をカウントすることで機能します。各入力は、対応するビンの値をインクリメントすることでカウントされます。その後、計数配列をループして、すべての入力を順番に並べます。このソートアルゴリズムは、アルゴリズムを効率的に動作させるにはS が十分に小さい必要があるため、多くの場合使用できませんが、非常に高速で、n が増加するにつれて優れた漸近的挙動を示します。また、安定した動作を提供するように変更することもできます。
バケットソートは、配列を有限個のバケットに分割することで計数ソートを一般化した、分割統治型のソートアルゴリズムです。各バケットは、それぞれ異なるソートアルゴリズムを使用するか、バケットソートアルゴリズムを再帰的に適用することで個別にソートされます。
バケットソートは、データセットの要素がすべてのバケットに均等に分散されている場合に最も効果を発揮します。
基数ソートは、個々の桁を処理して数値をソートするアルゴリズムです。k桁からなるn個の数値は、 O( n · k ) の時間でソートされます。基数ソートは、各数値の桁を最下位桁(LSD)から、または最上位桁(MSD) から処理できます。LSD アルゴリズムは、まず安定ソートを使用して相対的な順序を維持しながら、リストを最下位桁でソートします。次に、次の桁でソートし、最下位から最上位まで同様に処理して、ソートされたリストを作成します。LSD 基数ソートでは安定ソートの使用が必要ですが、MSD 基数ソートアルゴリズムでは (安定ソートが必要な場合を除き) 必要ありません。インプレース MSD 基数ソートは安定ではありません。基数ソートの内部で計数ソートアルゴリズムが使用されることはよくあります。小さなビンに挿入ソートを使用するなど、ハイブリッドソート方式を使用すると、基数ソートのパフォーマンスが大幅に向上します。
Niklaus Wirthは『アルゴリズムとデータ構造』 の中で、Lilithコンピュータ上でのいくつかの一般的なアルゴリズムの実行時間を比較している。[ 31 ]
ソート対象の配列のサイズが使用可能な主記憶装置のサイズに近づくか、それを超えると、（はるかに低速な）ディスクやスワップ領域を使用する必要が生じ、ソートアルゴリズムのメモリ使用パターンが重要になります。配列がRAMに容易に収まる場合にはかなり効率的だったアルゴリズムが、実用的でなくなる可能性があります。このような状況では、比較の総数は（相対的に）重要性が低くなり、メモリのセクションをディスクにコピーまたはスワップする回数がアルゴリズムのパフォーマンス特性を左右する可能性があります。したがって、比較の回数や比較の局所性は、比較の総数よりも重要になる場合があります。これは、近接する要素同士の比較はシステムバス速度（または、キャッシュを使用すればCPU速度）で行われ、ディスク速度と比較すると事実上瞬時に行われるためです。
例えば、広く用いられている再帰型クイックソートアルゴリズムは、十分なRAMがあればかなり良好なパフォーマンスを発揮しますが、配列の一部を再帰的にコピーする仕組みのため、配列がRAMに収まらない場合は、ディスクとの間で多数の低速なコピーや移動操作が発生する可能性があり、実用性が大幅に低下します。このような場合、比較回数は増えるものの、別のアルゴリズムの方が望ましいかもしれません。
この問題を回避する一つの方法は、複雑なレコード（リレーショナルデータベースなど）を比較的小さなキーフィールドでソートする場合に有効な方法として、配列にインデックスを作成し、配列全体ではなくインデックスをソートすることです。（その後、インデックスから読み取ることで、配列全体のソート済みバージョンを一度の処理で生成できますが、ソート済みのインデックスがあれば十分な場合が多いため、それすら不要な場合が多いです。）インデックスは配列全体よりもはるかに小さいため、配列全体ではメモリに収まらない場合でも、インデックスは容易にメモリに収まり、ディスクスワッピングの問題を効果的に解消できます。この手順は「タグソート」と呼ばれることもあります。[ 32 ]
メモリサイズの問題を克服するもう 1 つの手法は、外部ソートを使用することです。たとえば、2 つのアルゴリズムを組み合わせて、それぞれの強みを活かして全体的なパフォーマンスを向上させる方法があります。たとえば、配列を RAM に収まるサイズのチャンクに分割し、各チャンクの内容を効率的なアルゴリズム (クイックソートなど) を使用してソートし、マージソートで使用されるものと同様のk分割マージを使用して結果をマージすることができます。これは、リスト全体に対してマージソートまたはクイックソートを実行するよりも高速です。[ 33 ] [ 34 ]
複数の手法を組み合わせることも可能です。システムメモリを大幅に超えるような非常に大きなデータセットをソートする場合、インデックス自体も、仮想メモリを適切に処理するように設計されたアルゴリズム、あるいは複数のアルゴリズムの組み合わせを用いてソートする必要があるかもしれません。つまり、スワッピングの必要量を減らす必要があるということです。
関連する問題には、近似ソート（正しい順序から一定の範囲内でシーケンスをソートする）、部分ソート（リストの最小のk個の要素のみをソートするか、最小のk個の要素を見つけるが順序付けされていない）、および選択（k番目の最小の要素を計算する）などがあります。これらは全ソートによって非効率的に解決できますが、より効率的なアルゴリズムが存在し、多くの場合、ソートアルゴリズムを一般化することによって導出されます。最も注目すべき例は、クイックソートに関連するクイックセレクトです。逆に、一部のソートアルゴリズムは、選択アルゴリズムを繰り返し適用することによって導出できます。クイックソートとクイックセレクトは、両側（クイックソート、分割統治法）または片側（クイックセレクト、減少統治法）で再帰するかどうかだけが異なる、同じピボット操作と見なすことができます。
ソートアルゴリズムの対極にあるのがシャッフルアルゴリズムです。これらは乱数源を必要とするため、根本的に異なります。シャッフルはソートアルゴリズム、具体的にはランダムソートによっても実装できます。つまり、リストの各要素に乱数を割り当て、その乱数に基づいてソートするのです。しかし、実際にはこのような方法は一般的ではなく、シャッフルにはよく知られたシンプルで効率的なアルゴリズム、フィッシャー・イェーツシャッフルがあります。
ソートアルゴリズムは、多くの状況で順序を見つけるのに効果的ではありません。通常、要素に信頼できる比較機能がない場合（投票システムのようなクラウドソーシングによる選好）、比較に非常にコストがかかる場合（スポーツ）、またはすべての要素をすべての基準でペアワイズ比較することが不可能な場合（検索エンジン）に該当します。このような場合、問題は通常ランキングと呼ばれ、比較やランキングから推測される確率に基づいて、何らかの基準で「最良」の結果を見つけることが目標となります。一般的な例としてはチェスがあり、プレイヤーはEloレーティングシステムでランク付けされ、ランキングはソートアルゴリズムではなくトーナメントシステムによって決定されます。
「ノイズのある」（潜在的に誤った）比較器用のソートアルゴリズムと、「高速で粗雑な」（つまり「ノイズのある」）比較器と「クリーンな」比較器のペア用のソートアルゴリズムがあります。これは、完全な比較関数のコストが高い場合に役立ちます。[ 35 ]
