ソートは、すべての IT エンジニアと開発者にとって不可欠な知識スキルです。コーディング面接に合格するだけでなく、アルゴリズム自体も理解する必要があります。さまざまなソート アルゴリズムは、アルゴリズムの設計がプログラムの複雑さ、速度、効率に大きな影響を与える可能性があることを示す良い例です。 面接でよく聞かれる最も一般的なソートアルゴリズムのトップ 5 を見て、それらを Python で実装する方法を見てみましょう。 1. バブルソート バブルソートは、ソートの仕組みを明確に示しながらもシンプルで理解しやすいため、入門レベルの CS コースで最もよく教えられているソートです。バブルソートはリストを順に進み、隣接する要素のペアを比較します。要素の順序が間違っている場合は、入れ替えられます。リストがソートされるまで、リストのソートされていない部分の走査を繰り返します。バブルソートはリストのソートされていない部分を繰り返し通過するため、最悪の場合の複雑さは O(n²) になります。
2. 選択ソート 選択ソートも非常に単純で、バブルソートよりも優れています。 2 つから選択する必要がある場合は、デフォルトの「右選択ソート」を使用するのが最適です。選択ソートを使用して、入力リスト/配列を 2 つの部分に分割します。1 つはソートされた項目のサブリスト、もう 1 つはリストの残りを構成する残りの項目のサブリストです。 まず、ソートされていないサブリスト内の最小の要素を見つけて、それをソートされたサブリストの最後に配置します。したがって、最小のソートされていない要素を取得し、ソートされた順序でソートされたサブリストに格納し続けます。リストが完全にソートされるまでこのプロセスが繰り返されます。
3. 挿入ソート 挿入ソートはバブルソートや選択ソートよりも高速で、よりシンプルであると言えます。カードゲームをプレイするときと同じように、カードをシャッフルするプロセスは挿入ソートの繰り返しです。ループの各反復で、挿入ソートは配列から 1 つの要素を削除します。次に、他のソートされた配列内でその要素が属する位置を検索し、そこに挿入します。入力要素がなくなるまでこのプロセスを繰り返します。
4. マージソート マージソートは分割統治アルゴリズムの完璧な例です。このアルゴリズムを使用するには、主に次の 2 つの手順だけが必要です。 (1) ソートされていないリストを、それぞれが 1 つの「ソートされていない」要素を持つ N 個のサブリストになるまで分割し続けます。ここで、N は元の配列の要素数です。 (2)繰り返しマージ、つまり、2つのサブリストを一度にマージして、すべての要素がソートされた配列に完全にマージされるまで、新しいソートされたサブリストを生成する。
5. クイックソート クイックソートも、マージソートと同様に分割統治アルゴリズムです。少し複雑ではありますが、ほとんどの標準実装ではマージソートよりもはるかに高速に実行され、最悪の場合でも O(n²) の複雑度に達することはほとんどありません。主なステップは 3 つあります。 (1)まず配列からピボットと呼ばれる要素を選択します。 (2)軸より小さい要素はすべて軸の左に移動し、軸より大きい要素はすべて軸の右に移動します。これをパーティション操作と呼びます。 (3)前の軸の値より小さいか大きい値を持つ要素の各サブ配列に対して、上記2つの手順を再帰的に適用する。
- 終わり - 多くの学生は、Python を学習する際にさまざまなアルゴリズムの問題に遭遇します。簡単に理解できるものもありますが、学習に時間と労力を要するものもあります。 この記事の 5 つのソート アルゴリズムは、Python 初心者に適しています。ほとんどのベテラン プログラマーはすでにソート アルゴリズムに精通しており、面接の過程でそれらを学習することを余儀なくされます。 |
<<: Python コーディング面接の前に解くべき 10 個のアルゴリズム
>>: 教師あり学習、教師なし学習、強化学習とは何ですか?ついに誰かが明らかにした
[[208505]]強固な経済基盤がなければ、豊かな国と強い国民は実現できません。中国共産党第19回...
この記事はLeiphone.comから転載したものです。転載する場合は、Leiphone.com公式...
最近、多くの専門家とコミュニケーションをとる中で、人工知能の3つの重要なビジネス面が徐々に明らかにな...
[[267886]]最近、あるニュースに衝撃を受け、言葉を失いました。そして、人々の収入がどこまで...
GraphSAGE は 2017 年の論文ですが、その名前に含まれる 2 つのキーワード「帰納的」と...
これまで、多くのメディアがニューラルネットワークの「ブラックボックス」問題について熱く議論してきまし...
現在、顔認識技術は広く利用されており、決済や本人認証、美容カメラなどに利用されています。 iPhon...
ディープ ニューラル ネットワーク (DNN) は、基本的に複数の接続されたパーセプトロン (パーセ...
近代化は世界を変える可能性のある新しい画期的なものをもたらしました。現実世界の問題は、単純な従来のア...
クラウド コンピューティング プロバイダーは、データを分析し、スキルの低いユーザー (または予算が限...
[[384631]] ◇コンピューティングパワーアルゴリズムの重要な基盤として、人工知能チップと人...
ロボットがいくつかの簡単な作業を実行できることは目新しいことではありません。最近、ロシア西部の都市ペ...
データによれば、わが国には60歳以上の高齢者が2億6,400万人以上おり、そのうち1億8,000万人...