Python、Java、C++がすべて含まれています。このGitHubプロジェクトは、複数の言語で古典的なアルゴリズムを実装しています。

古典的なデータ構造とアルゴリズムをいくつ知っていますか?大企業で面接を受けてみませんか？アルゴリズムエンジニアになりたいですか?この包括的なレビュー資料を入手してください。

低レベルのプログラマー、フロントエンドのカットアウトの専門家、またはバックエンドの「追加、削除、変更、チェック」の達人になりたくないですか?次に、アルゴリズムとデータ構造を確認する必要があるかもしれません。アルゴリズムエンジニアになりたい場合、基礎知識は避けられない大きな障害となります。今回推奨するプロジェクトは、データ構造とアルゴリズムに関するオープンソースプロジェクトの集合体であり、複数の主流言語を網羅し、さまざまな古典的なデータ構造とアルゴリズムを実装しています。

プロジェクトアドレス: https://github.com/trending

アルゴリズムプロジェクトの紹介

The Algorithms プロジェクトのホームページで紹介されているように、これは複数のプログラミング言語で古典的なデータ構造とアルゴリズムを実装するオープンソース プロジェクトのセットです。ここでの「あらゆるプログラミング言語」は、実際には誤った宣伝ではありません。The Algorithms には、より一般的な Python、Java、C、C++ から C#、Go、Rust、Kotlin まで、あらゆるものが含まれていることがわかります。もちろん、一部のプログラミング言語で実装されているアルゴリズムはそれほど豊富ではなく、Python と Java の方がまだよく整備されています。

この記事では、The Algorithms の Python プロジェクトを例に挙げます。

現在までに、このプロジェクトには7万以上のスターが付いており、その内容は暗号化アルゴリズム、画像処理、動的プログラミング、線形代数、古典的な機械学習アルゴリズム、検索アルゴリズム、ソートアルゴリズム、さまざまなデータ構造を網羅しています。実装されたアルゴリズムのディレクトリだけでも600行以上あります...もちろん、プロジェクト作者は、プロジェクトの主な目的はさまざまなアルゴリズムの学習教材として使用することであり、プロジェクト内の一部の実装はPython標準ライブラリの実装ほど効率的ではない可能性があることも指摘しています。

プロジェクトアドレス: https://github.com/TheAlgorithms/Python

いくつかのアルゴリズムのデモンストレーション

このプロジェクトが魅力的なのは、豊富なアルゴリズムの実装だけでなく、一部のアルゴリズムに関連する説明、Wikipedia リンク、インタラクティブな Web リンクが付属している点です。デモンストレーション用にいくつかのアルゴリズム実装を選択しました。

ソートアルゴリズム

1. バブルソート

バブルソートは単純なソートアルゴリズムです。ソートする配列を繰り返し走査し、一度に 2 つの要素を比較して、順序が間違っている場合はそれらを交換します。交換する必要がある要素がなくなるまで、つまりソートが完了するまで、上記のプロセスを繰り返します。このアルゴリズムの名前は、小さな要素が交換を通じてゆっくりとシーケンスの先頭に「浮かんで」いくという事実に由来しています。

アルゴリズムの複雑さ:

• 最悪の場合 O(n^2)
• ベストO(n)
• 平均O(n^2)

インタラクティブウェブページアドレス: https://www.toptal.com/developers/sorting-algorithms/bubble-sort

2. 挿入ソート

挿入ソートの動作原理は、順序付けられたシーケンスを構築することです。ソートされていないデータの場合は、ソートされたシーケンスを後ろから前へスキャンし、対応する位置を見つけて挿入します。挿入ソートは通常、インプレースソートを使用して実装されます。したがって、後ろから前へスキャンするプロセスでは、最新の要素を挿入するためのスペースを確保するために、ソートされた要素を繰り返し後方に移動する必要があります。

アルゴリズムの複雑さ:

• 最悪の場合 O(n^2)
• ベストO(n)
• 平均O(n^2)

インタラクティブ Web ページ アドレス: https://www.toptal.com/developers/sorting-algorithms/insertion-sort

3. マージソート

マージソートは、ジョン・フォン・ノイマンによって最初に提案された、マージ操作に基づく効率的なソートアルゴリズムです。このアルゴリズムは分割統治法の非常に典型的な応用であり、分割統治法の再帰の各レベルを同時に実行できます。

アルゴリズムの複雑さ:

• 最悪の場合 O(n log n)
• ベストO(n)
• 平均O(n)

インタラクティブウェブページアドレス: https://www.toptal.com/developers/sorting-algorithms/merge-sort

4. クイックソート

クイックソートアルゴリズムは、Tony Hall によって最初に提案されました。分割統治戦略を使用して、シーケンスを小さいサブシーケンスと大きいサブシーケンスの 2 つのサブシーケンスに分割し、2 つのサブシーケンスを再帰的にソートします。

アルゴリズムの複雑さ:

• 最悪の場合 O(n^2)
• 最適O(n log n)またはO(n)
• 平均O(n^2)

インタラクティブウェブページアドレス: https://www.toptal.com/developers/sorting-algorithms/quick-sort

5. シェルソート

シェル ソートは降順増分ソート アルゴリズムとも呼ばれ、挿入ソートのより効率的な改良版です。設計者のドナルド シェルにちなんで名付けられ、1959 年に発表されました。シェルソートは不安定なソートアルゴリズムです。

アルゴリズムの複雑さ:

• 最悪の場合O(nlog2 2n)
• ベストO(n log n)
• 平均的な複雑さはステップの順序によって決まる

インタラクティブ Web ページ アドレス: https://www.toptal.com/developers/sorting-algorithms/shell-sort

検索アルゴリズム

1. 線形探索アルゴリズム

線形検索 (シーケンシャル検索とも呼ばれます) では、ループを使用して配列を順番に反復処理し、各要素を検索対象の値と比較し、値が見つかるか配列の末尾に達すると停止します。

アルゴリズムの特徴:

• 最悪のアルゴリズムの複雑さ O(n)
• 最適なアルゴリズムの複雑さはO(1)である
• 平均アルゴリズム複雑度 O(n)
• 最悪の場合の空間計算量 O(1)

2. 二分探索アルゴリズム

バイナリ検索アルゴリズムは、バイナリ検索アルゴリズムまたは対数検索アルゴリズムとも呼ばれ、順序付けられた配列内の特定の要素を見つけるための検索アルゴリズムです。検索プロセスは配列の中央の要素から始まります。中央の要素がまさに検索対象の要素である場合、検索プロセスは終了します。特定の要素が中央の要素より大きいか小さい場合、その要素は配列の中央の要素より大きいか小さい半分で検索され、比較は最初と同様に中央の要素から始まります。特定のステップで配列が空の場合、配列が見つからないことを意味します。この検索アルゴリズムは、比較ごとに検索範囲を半分に減らします。

• アルゴリズムの特徴:
• 最悪のアルゴリズムの複雑さ O(log n)
• 最適なアルゴリズムの複雑さはO(1)である
• 平均アルゴリズムの複雑さ O(log n)
• 最悪の場合の空間計算量 O(1)

著者について

このプロジェクトの作者は、技術開発に非常に熱心なインド人エンジニアです。彼は自分が非常に「野心的な」人間であり、将来は起業家になりたいと認めています。著者は技術的な観点から、フルスタック開発、Android 開発、ディープラーニング、ブロックチェーンなどの技術に興味を持っています。現在、3つのスタートアップで勤務し、開発分野で2年間の経験を持つ。

過去の経験から判断すると、このインド人男性の職歴は、当初はソフトウェア エンジニアとして働いていたものの、現在は Gojek で製品エンジニアとして働くなど、非常に「多彩」です。

ゴジェックは2010年にインドネシアで設立されたインドネシア初のユニコーン企業です。この会社は、消費者と宅配便や二輪車の配車サービスをつなぐコールセンターと考えることができます。同社はインドネシア、ベトナム、シンガポール、タイ、フィリピンでも大きな事業展開を行っています。