Pythonでのソートと検索

1,000個の名前がリストされている紙が手に入っていて、そのうちの1つを見つける必要があると想像してください。このリストはアルファベット順ではありません。とてもイライラするでしょうね。このリストを整理するのに長い時間がかかりますが、名前を見つけるのははるかに簡単になります。したがって、物事を並べ替えることは私たちの人間の自然な欲求であり、ソートされたリストを検索することは、明らかに秩序だったリストを検索するよりも明らかに労力を節約します。

コンピューターの世界では、検索のリストは非常に大きく、高速なコンピューターでさえ、パフォーマンスが影響を受ける可能性があります。この場合、適切なソートおよび検索アルゴリズムがこのような問題の解決策となります。ソートは、値のリストを順番に並べ替えるプロセスであり、検索はリスト内の値の位置を見つけるプロセスです。

この問題の重要性を説明するために、アメリカの偉大なコンピューター科学者のドナルドクヌースが言ったことをお見せしましょう。

1960年代のコンピューターメーカーは、すべての顧客を考慮して、コンピューターランタイムの25％以上がソートに費やされたと推定しました。実際、多くのインストールの場合、ソートタスクは計算時間の半分以上を占めています。これらの統計から、（i）並べ替えには多くの重要なアプリケーションがある、または（ii）そうすべきではない場合に多くの人々がソートするか、（iii）非効率的なソートアルゴリズムが広く使用されていると結論付けることができます。 - - 「コンピュータープログラミングの技術」ボリューム3：ソートと検索、3ページ

このチュートリアルでは、選択ソートアルゴリズムと線形検索アルゴリズムの実装方法を示します。

しかし、始める前に、Pythonコードをソートして検索したい場合は、組み込みの方法を示します。

Pythonの組み込みのソートメソッドと機能

Pythonを使用して多くのソートアルゴリズムを作成できます。これは優れた学習演習ですが、生産アプリケーションでは、Pythonに組み込みの保存機能と方法に固執する必要があります。

Pythonには、リストを内側に並べ替えるために使用できる

メソッドがあります。 Pythonの舞台裏で使用されるソートアルゴリズムは、Timsortと呼ばれます。これは、多くの実際の生活で優れたパフォーマンスを提供する挿入並べ替えとマージソートに基づいたハイブリッドソートアルゴリズムです。これらの2つの機能と方法の使用方法の例は次のとおりです。

上記のコードの状況の一部に気付くかもしれません。

関数は、元のリストを変更せずに新しい並べ替えられたリストを返します。ただし、元のリストは同じままです。一方、list.sort()の

メソッドを呼び出すと、

marks_a = [61, 74, 58, 49, 95, 88]
marks_b = [94, 85, 16, 47, 88, 59]

# [49, 58, 61, 74, 88, 95]
print(sorted(marks_a))

# None
print(marks_b.sort())

# [61, 74, 58, 49, 95, 88]
print(marks_a)

# [16, 47, 59, 85, 88, 94]
print(marks_b)

を返します。

いくつかのパラメーターを渡して、ソート動作を変更できます。たとえば、関数をパラメーターなしでアルファベット順に並べ替えるreverseパラメーターに関数を渡します。 2番目のケースでは、ソートされた単語の順序を逆にするためにsorted()を使用します。 reverse=True

並べ替えアルゴリズム

を選択します

並べ替えアルゴリズムは、最小値または最大値の継続的な選択に基づいています。昇順で並べ替えたいリストがあるとします（小さいから大規模）。最小の要素はリストの先頭にあり、最大の要素はリストの最後にあります。

元のリストが次のように見えるとします：

| 7 | 5 | 3.5 | 4 | 3.1 |

最初にしなければならないことは、リスト内の

最小値、この場合はの値を見つけることです。 3.1

最小値が見つかった場合、リストの最初の要素と最小値を交換

。つまり、と交換します。このリストは次のようになります： 3.1 7

リスト内の最初の要素の正しい位置を決定したので、リストの2番目の要素から上記の手順（最小値を見つけます）を繰り返します。リスト内の最小値（2番目の要素から始まる）は| 3.1 | 5 | 3.5 | 4 | 7 |であることがわかります。したがって、

と交換します。リストは次のようになります

この時点で、最初の要素と2番目の要素が正しい位置にあることを確認します。 3.5 3.5次に、リストの残りの部分の最小値を確認します。つまり、3番目の要素5から始めます。リストの残りの残りの値は

であり、これを

と交換します。したがって、リストは次のようになります | 3.1 | 3.5 | 5 | 4 | 7 |

したがって、

最初の3つの要素が正しい位置にあり、この方法でプロセスが継続されると判断しました。

Pythonで選択並べ替えアルゴリズムを実装する方法を見てみましょう（Isai Damierに基づく）：5 4 5上記のスクリプトの最後に次のステートメントを追加して、アルゴリズムをテストしましょう。

この場合、次の出力を取得する必要があります。 | 3.1 | 3.5 | 4 | 5 | 7 |

線形検索アルゴリズム

線形検索

アルゴリズムは、リスト内の各アイテムが目的のアイテムが見つかるか、リストの最後に到達するまでチェックされる（最初のアイテムから開始）単純なアルゴリズムです。

marks_a = [61, 74, 58, 49, 95, 88]
marks_b = [94, 85, 16, 47, 88, 59]

# [49, 58, 61, 74, 88, 95]
print(sorted(marks_a))

# None
print(marks_b.sort())

# [61, 74, 58, 49, 95, 88]
print(marks_a)

# [16, 47, 59, 85, 88, 94]
print(marks_b)

線形検索アルゴリズムは、次のようにPythonで実装されています（Python Schoolに基づく）：

def selectionSort(aList):
    for i in range(len(aList)):
        least = i
        for k in range(i+1, len(aList)):
            if aList[k] < aList[least]:
                least = k

        swap(aList, least, i)

def swap(A, x, y):
    temp = A[x]
    A[x] = A[y]
    A[y] = temp

コードをテストしましょう。上記のPythonスクリプトの最後に次のステートメントを入力してください。

入力するときは、単一​​の引用符または二重引用符の間にあることを確認してください（つまり

）。たとえば、[4.6, 4.7, 5.76, 7.3, 7.6, 25.3, 32.4, 43.5, 52.3, 55.3, 86.7]と入力する場合、次の出力を取得する必要があります。

そして、入力としてを入力すると、次の出力が得られます。

Oops, your item seems not to be in the bag

結論

私たちが見たように、Pythonは、ここでソートと検索のアルゴリズムを扱うように、アルゴリズムの概念を簡単にプログラムできるプログラミング言語として再び証明します。

他の種類のソートおよび検索アルゴリズムがあることに注意する必要があります。 Pythonを使用してこれらのアルゴリズムをより深く掘り下げたい場合は、無料のPythonオブジェクト指向のプログラミングテキストを参照できます。

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