Python を使用した配列の波形ソート

この記事では、配列の波形を並べ替えるための Python プログラムを学習します。

ソートされていない入力配列があるとします。次に、入力配列を波形形式で並べ替えます。配列 'arr [0..n-1]' が arr [0] >= arr [1] = arr [3] = を満たす場合. ....、配列が波形にソートされます。

使用される方法

このタスクを実行するためのさまざまな方法を次に示します &miinus;

• 組み込みのsort()関数を使用します

• 組み込み関数を使用しない場合

方法 1: 組み込みの sort() 関数を使用する

アルゴリズム (ステップ)

以下は、目的のタスクを実行するために従うべきアルゴリズム/手順です。

• 入力配列と配列の長さをパラメータとして受け取り、入力配列を波形で並べ替える関数を作成します。

• sort() 関数 (リストを昇順/降順に並べ替える) を使用して、入力配列を昇順に並べ替えます。

• for ループ

  を使用して、配列の長さになるまで交互に走査します(ステップ=2)

「,」演算子を使用して、隣接する要素、つまり現在の要素と次の要素を入れ替えます。
入力配列を保存する変数を作成します。
• len()

  関数 (オブジェクト内の項目数を返す) を使用して、入力配列の長さを取得します。

入力配列と配列の長さを引数として渡して、上記で定義した
• sortingInWaveform()

  関数を呼び出します。 for ループを使用します

  配列のすべての要素を走査します

• 配列の現在の要素を出力します。

＃＃＃例＃＃＃
• 次のプログラムは、Python の組み込み sort() 関数を使用して波形内の入力配列を並べ替えます。 -

  リーリー ＃＃＃出力＃＃＃

  実行すると、上記のプログラムは次の出力を生成します &miinus;
リーリー

時間計算量

− O(nLogn).

ここでは、指定された配列は sort 関数を使用して並べ替えられています。通常、この関数の時間計算量は O(NlogN) です。

マージ ソート、ヒープ ソート

などの O(nLogn) ソート アルゴリズムを適用する場合、上記の方法の時間計算量は O(nLogn) です。

方法 2: ループを 1 つだけ使用する アルゴリズム (ステップ)

以下は、目的のタスクを実行するために従うべきアルゴリズム/手順です。

for ループ を使用して、引数として 0、配列の長さ、ステップ値を渡して偶数のインデックス要素をすべて走査します。

if 条件付き

ステートメントを使用して、現在の偶数インデックス要素が前の要素より小さいかどうかを確認します。

条件が
• true の場合に要素を交換します。

• if 条件文

  を使用して、現在の偶数インデックス要素が次の要素より小さいかどうかを確認します。

条件が
• true の場合に要素を交換します。

入力配列と配列の長さを引数として渡して、上記で定義した
• sortingInWaveform()

  関数を呼び出します。

  for ループ
を使用して、配列の要素を走査します。

• 配列/リストの対応する要素を出力します。

• ＃＃＃例＃＃＃

  次のプログラムは、for ループを 1 つだけ使用し、組み込み関数を使用せずに入力配列を波形で並べ替えます。 − リーリー ＃＃＃出力＃＃＃ 上記のプログラムを実行すると、次の出力が生成されます -

  リーリー
• 時間計算量

  - O(n)。 ここでは、sort 関数を使用しませんでした。代わりに、for ループを使用して、平均して O(N) 時間の計算量を持つ、指定された配列の要素を反復処理しました。 ＃＃＃結論は＃＃＃

  この記事では、2 つの異なる方法を使用して、指定された波形の配列を並べ替える方法を学びました。最初の方法と比較して時間計算量が O(log N) 削減された新しいロジックを使用しました。多くの場合、この種のアルゴリズムは時間の複雑さを軽減し、効率的なソリューションを実装するのに役立ちます。

以上がPython を使用した配列の波形ソートの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。