小さな整数の配列を並べ替えるのに最適な並べ替えアルゴリズムは何ですか

1. 概要

このチュートリアルでは、小さな整数の配列を並べ替えるのに最適な並べ替えアルゴリズムについて説明します。まず、問題を定義します。次に、それを説明するための例を示します。

最後に、そのアルゴリズムを使用するための2つの異なる状況を示します。最初の1つは小さな整数の配列用で、もう1つはその数の任意のペア間の絶対差が小さい配列に関するものです。

小さな整数値で構成される配列があるとします。この配列をできるだけ速くソートするように求められました。

理解を深めるために、次の例を見てみましょう。整数配列が与えられたら、それをソートしましょう。

次の条件が満たされるように、配列の番号を再配置します。ここで。

ご覧のとおり、前の条件を満たす唯一の配列はであり、これをソートされた配列と呼びます。

この問題は、一般的なsorting問題の特殊なケースであることに注意してください。このバージョンでは、配列内の値が小さいという事実を使用する必要があります。また、配列のサイズが小さいかどうかは関係ありません。

このアプローチの主なアイデアは、配列の各番号の出現をカウントすることです。次に、可能なすべての値を昇順で繰り返し、現在の値の時間を並べ替えられた配列に追加します。ここで、は現在の値の出現回数です。

まず、指定された配列の数値ごとに、その値のカウントを1つ増やします。反復が完了すると、各発生回数がカウントされます。

次に、配列に表示されるすべての可能な値を繰り返し処理します。配列は小さな整数で構成されているため、この反復は手頃な価格である必要があります。次に、値ごとに、出現回数で並べ替えられた配列に追加します。

最後に、並べ替えられた配列には、番号を昇順で追加するため、配列のすべての番号が降順ではない順序で並べ替えられます。

アルゴリズムの実装を見てみましょう。

最初に、ソートされた配列を返す関数を宣言します。関数には、並べ替える特定の配列を表す1つのパラメーターがあります。

まず、指定された配列内の各数値の出現回数を格納する配列を宣言します。次に、配列内の各要素を反復処理し、その要素を1つ増やします。

次に、配列が指定された配列のソートされたバージョンになることを宣言します。次に、指定された配列で可能なすべての値を昇順で繰り返します。値ごとに、ソートされた配列に時間で追加します。

最後に、指定された配列のソートされたバージョンであるを返します。

このアルゴリズムの時間計算量はです。ここで、は指定された配列の長さであり、は指定された配列に存在する可能性のある最大値です。この複雑さの背後にある理由は、配列内の各値を1回反復し、すべての可能な値の出現の合計が正確にになるためです。

このアプローチの主なアイデアは、特定の配列内のすべての数値を特定のオフセットだけシフトして、特定の配列番号の値を減らし、数値を負でない状態に保つことです。次に、シフトされた配列を並べ替えることは、最初の配列を並べ替えることと同じです。

最適なオフセットは、配列番号をシフトして非負に保つために使用できる最大値です。したがって、指定された配列の最小値に等しくなります。次に、の数値ごとに、オフセットだけシフトされた数値を1つ増やします。

次に、シフトされた可能性のあるすべての値を繰り返し処理します。これらの値の範囲は、ゼロから最大値から最小値を引いたものまでです。ソートされた配列に、それぞれのシフトされた値の出現回数によって元の値を追加します。

最後に、並べ替えられた配列には、配列のすべての番号が降順ではない順序で並べ替えられます。

アルゴリズムの実装を見てみましょう。

前のアプローチと同じ関数を宣言します。

最初に、指定された配列内のシフトされた各数値の出現回数を格納する配列を宣言します。また、を宣言します。これは、配列の数値から減算できる最大値を表し、すべての数値を非負に保ちます。

次に、配列内の各要素を反復処理し、現在の数値から1を引いた値を増やします。

次に、配列が指定された配列のソートされたバージョンになることを宣言します。また、を宣言します。これは、指定された配列で考えられるすべての違いの帯域幅を格納します。

次に、指定された配列で考えられるすべての違いを昇順で繰り返します。違いごとに、イニシャルを時間で追加した後、ソートされた配列に追加します。

最後に、指定された配列のソートされたバージョンであるを返します。

このアルゴリズムの時間計算量はです。ここで、は指定された配列の長さであり、は指定された配列の任意のペア間の最大絶対差です。この複雑さの背後にある理由は、前のアプローチと同じです。

この記事では、小さな整数の配列を並べ替えるのに最適な並べ替えアルゴリズムを紹介しました。

まず、問題を説明する例を示しました。次に、そのアルゴリズムを使用できる2つの異なる状況を調査しました。

最後に、それらの実装をウォークスルーし、それぞれの背後にある考え方を説明しました。