アルゴリズム。

Apr 27 2023

プログラミングやアルゴリズム的思考に慣れていない場合は、二分探索とクイックソートという 2 つの主要なアルゴリズムを学習する必要があります。これらのアルゴリズムはコンピューターサイエンスで広く使用されており、現実世界でも多くの応用例があります。

この記事では、バイナリ検索とクイックソートの実装、使用例、実際のアプリケーションを含む詳細なガイドを提供します。これらのアルゴリズムとその仕組みを理解するのに役立つ例と説明も提供します。

したがって、初心者でも経験豊富なプログラマーでも、これらの強力なアルゴリズムと、それらがコード内および現実世界の問題の解決にどのように役立つかについて詳しく学ぶために読み続けてください。

アルゴリズムについてさらに詳しく知りたい場合は、 Aditya Bhargava 著『Grokking Algorithms: An Illustrationed Guide for Programmers and other好奇心旺盛な人々』という本を読むとよいでしょう。

Unsplash の SCREEN POST による写真

二分探索

二分探索は、探索間隔を繰り返し半分に分割し、各ステップで残りの要素の半分を削除する探索アルゴリズムです。このアプローチでは、対数的な時間計算量がになりますO(log n)。二分検索は、データベースの検索、コンピュータプログラム内の特定の項目の検索、数値データセット内の値の検索など、多くのアプリケーションで広く使用されています。

実装

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

7inのインデックスを見つけるには[1, 2, 3, 4, 5, 6, 7, 8, 9]、それを中央の要素と比較します5。より大きい場合は5上半分を検索します[6, 7, 8, 9]。未満の場合は8下半分を検索します[1, 2, 3, 4, 5, 6]。を見つけると7、そのインデックスはになります6。

使用例

ソートされたリスト内の要素の検索、またはソートされたリスト内の要素のインデックスの検索: 二分探索は両方のタスクをO(log n)時間計算量で実行できます。
指定された値に最も近い並べ替えられたリスト内の要素を検索する: 二分検索を使用して、指定された値と等しいか、その直前または直後の要素を検索します。
昇順、降順でソートされた配列内のピーク要素の検索: 二分検索を使用して、近傍より大きいピーク要素を検索します。

二分検索は、Web ページや医療記録などの大規模なデータベースを効率的に検索し、関連する結果をユーザーに返します。
このアルゴリズムは、コンピュータネットワークでネットワークデータパケットのソート順から特定のデータパケットを迅速に見つけるために使用され、金融取引では大規模なデータセット内の特定のデータに基づいて情報に基づいた意思決定を行うために使用されます。
二分探索は、特定のモデルに最適なハイパーパラメータを見つけるための機械学習や、大規模なデータセット内の特定の遺伝子や変異を特定するための DNA シーケンシングでも使用されます。

クイックソートは、配列を 2 つのサブ配列に再帰的に分割することで効率的に配列を並べ替える、広く使用されている並べ替えアルゴリズムです。このアルゴリズムは、配列からピボット要素を選択し、残りの要素を 2 つのグループ (ピボット以下の要素とピボット以上の要素) に分割します。次に、配列全体がソートされるまで、2 つのグループを再帰的にソートします。クイックソートは、分割統治戦略により最も高速なソートアルゴリズムの 1 つであり、平均時間計算量はですO(n log n)。大規模なデータセットを処理でき、さまざまなアプリケーションで一般的に使用されます。

実装

def quick_sort(arr):
    if len(arr) <= 1:
        return arrp
    else:
        pivot = arr[0]
        left = [x for x in arr[1:] if x <= pivot]
        right = [x for x in arr[1:] if x > pivot]
        return quick_sort(left) + [pivot] + quick_sort(right)

次の要素を含む配列があるとします[9, 7, 5, 11, 12, 2, 14, 3, 10, 6]。

クイックソートアルゴリズムを使用して配列を並べ替えるには、次の手順に従います。

この場合は、配列内の最初の要素をピボット要素として選択します9。
配列を 2 つのサブ配列に分割します。1 つはピボット以下の要素を持つサブ配列で、もう 1 つはピボットより大きい要素を持つサブ配列です。

[9, 7, 5, 11, 12, 2, 14, 3, 10, 6]
 ^ pivot
[7, 5, 2, 3, 6]   [9]   [11, 12, 14, 10]

[7, 5, 2, 3, 6]
 ^ pivot
[5, 2, 3, 6]   [7]
 ^ pivot
[2, 3]   [5]   [6]   [7]
 ^ pivot
[2]   [3]   [5]   [6]   [7]
[2, 3, 5, 6, 7]

[11, 12, 14, 10]
 ^ pivot
[10]   [11]   [12, 14]
               ^ pivot
[10]   [11]   [12]   [14]
[10, 11, 12, 14]

[2, 3, 5, 6, 7]   [9]   [10, 11, 12, 14]
[2, 3, 5, 6, 7, 9, 10, 11, 12, 14]

クイックソートは、コンピューターサイエンスの教育とプログラミングで使用される古典的な分割統治アルゴリズムです。
クイックソートは、組み込みシステムやリアルタイムアプリケーションなど、メモリ使用量が懸念されるアプリケーションで役立ちます。

クイックソートは、大規模なデータセットやデータ構造をソートするためにデータベースやプログラミング言語でよく使用されます。
クイックソートは、科学計算や数値解析で、シミュレーションや実験で生成された大規模なデータセットを並べ替えるために使用されます。
クイックソートは、電子商取引において、ユーザーの好みに基づいて製品、レビュー、その他のデータをすばやく並べ替えるのに役立ちます。これは、大規模なカタログを持つオンライン小売業者に役立ちます。

Unsplash の Viktor Ritsvall による写真

二分探索とクイックソートは、すべてのプログラマが知っておくべき 2 つの基本的なアルゴリズムです。二分探索はコンピュータプログラム内の特定の項目を見つけるのに役立つ検索アルゴリズムであり、クイックソートは大規模なデータセットを効率的に並べ替えることができる並べ替えアルゴリズムです。どちらのアルゴリズムも、データベースの検索や金融取引から機械学習や DNA シーケンスに至るまで、数多くの実世界に応用できます。この記事では、両方のアルゴリズムの実装、使用例、実際のアプリケーションを含む詳細なガイドを提供します。初心者でも経験豊富なプログラマーでも、これらの強力なアルゴリズムは、コード内および現実世界の問題を解決するのに役立ちます。アルゴリズムについて詳しく知りたい場合は、この本を読んでください。『Grokking Algorithms: プログラマーやその他の好奇心旺盛な人のための図解ガイド』 Aditya Bhargava 著。

次の記事では、もう 1 つの人気のあるアルゴリズムである BFS (Breadth-First Search) について説明します。このアルゴリズムは、グラフのすべての頂点を探索するために使用されます。