一般的な基本的なソートアルゴリズムを今回から理解しましょう

一般的な基本的なソートアルゴリズムを今回から理解しましょう

[[382785]]

この記事はWeChatの公開アカウント「Beta Learns JAVA」から転載したもので、著者はSilently9527です。この記事を転載する場合は、Beta Learning JAVA パブリック アカウントにお問い合わせください。

序文

すべてのプログラマーが最初に接触するアルゴリズムはソート アルゴリズムであると私は信じています。ソートはデータ処理と計算において重要な役割を果たしており、ソート アルゴリズムは他のアルゴリズムの基礎となることが多いためです。この記事では、基本的なソート アルゴリズムからアルゴリズムの学習を始めます。

ソートアルゴリズムのテンプレート

始める前に、ソート アルゴリズムの共通テンプレートを定義しましょう。以降のすべてのソート アルゴリズムはこのテンプレートを実装します。

  1. パブリックインターフェースSortTemplate {
  2.  
  3. void sort(Comparable[] 配列);
  4.  
  5. デフォルトvoid print(Comparable[]配列) {
  6. for (比較可能な a : 配列) {
  7. システム.out.print (a + " " );
  8. }
  9. }
  10.  
  11. デフォルトのブール値 less(比較対象 a, 比較対象 b) {
  12. a.compareTo(b) < 0を返します
  13. }
  14.  
  15. デフォルトvoid exch(Comparable[] 配列、 int i、 int j) {
  16. 比較可能なtmp = array[i];
  17. 配列[i] = 配列[j];
  18. 配列[j] = tmp;
  19. }
  20.      
  21. }
  • Comparable: 実装するソート アルゴリズムをより汎用的にし、任意のオブジェクトをソートするために、ここでは Comparable 配列を使用します。
  • ソート: ソートアルゴリズムはそれぞれ異なる方法で実装されるため、サブクラスで独自に実装します。
  • less: a < b の場合に true を返すパブリックメソッドが定義されています
  • exch: 配列内の2つのオブジェクトを交換するために定義されたパブリックメソッド
  • print: データ内の各要素を印刷する

選択ソート

アルゴリズム実装のアイデア:

  • まず配列内の最小の要素を見つけます。
  • 実際には、配列の最初の要素と交換して、 1 つの要素が配置されるようにします。
  • 残りの要素の中から最小の要素を再度見つけ、それを配列の 2 番目の要素と交換し、すべての要素が整列するまでこのプロセスを繰り返します。

コード実装:

  1. パブリッククラスSelectionSortはSo​​rtTemplateを実装します。
  2.  
  3. @オーバーライド
  4. パブリックvoid ソート(比較可能な[] 配列) {
  5. int長さ = 配列.長さ;
  6. ( int i = 0; i < 長さ; i++) {
  7. 整数 最小値= i;
  8. ( int j = i + 1; j < 長さ; j++) {
  9. if (less(配列[j], 配列[ min ])) {
  10. 最小値= j;
  11. }
  12. }
  13. exch(配列、i、 min );
  14. }
  15. }
  16.  
  17. }

入力配列がソートされている場合、選択ソートの実行にはソートされていない場合と同じくらいの時間がかかることがわかります。

N要素の配列の場合、選択ソートを使用する際の時間計算量はO(n2)である。

選択ソートは、移動するデータが最も少ないソートです。スワップの数は、配列のサイズに比例します。N 要素の配列には、N 回のスワップが必要です。

バブルソート

アルゴリズム実装のアイデア:

  • 隣接する 2 つの要素を比較します。最初の要素が 2 番目の要素よりも大きい場合は、2 つの要素の位置を入れ替えます。
  • 最後の要素まで、隣接する要素の各グループに対して同じ操作を実行します。操作が完了したら、最大の要素をランク付けできます。
  • 配列内のすべての要素が整うまでこのプロセスを繰り返します。

コード実装:

  1. パブリッククラスBubbleSortはSo​​rtTemplateを実装します。
  2.  
  3. @オーバーライド
  4. パブリックvoid ソート(比較可能な[] 配列) {
  5. int長さ = 配列の長さ - 1;
  6. ( int i = 0; i < 長さ; i++) {
  7. ( int j = 0; j < 長さ - i; j++) {
  8. if (less(配列[j + 1], 配列[j])) {
  9. exch(配列、j、j + 1);
  10. }
  11. }
  12. }
  13. }
  14.  
  15. }

N要素の配列の場合、バブルソートの時間計算量はO(n2)です。

挿入ソート

ポーカーをプレイしているとき、左側の分類されたカードの適切な位置に各カードを挿入してカードを並べることを想像してください。挿入ソートの考え方は似ている

アルゴリズム実装のアイデア:

  • 最初の要素はデフォルトで最初に順序付けられ、現在のインデックスは 0 から始まります。
  • 現在のインデックス位置を 1 つずつ移動します。現在のインデックス位置の左側の要素は順番になっています。コードを後ろから前に向かってスキャンし、現在のインデックス位置の要素と比較します。
  • 現在のインデックス位置の要素が左側の順序付けられた位置に収まることを確認した後、その位置に挿入します。
  • 現在のインデックス位置の要素がソートされた最後の要素より大きいと判断された場合、現在のインデックス位置は直接後方に移動します。
  • すべての要素が整うまでこのプロセスを繰り返します。

コード実装:

  1. パブリッククラスInsertionSortはSo​​rtTemplateを実装します。
  2.  
  3. @オーバーライド
  4. パブリックvoid ソート(比較可能な[] 配列) {
  5. int長さ = 配列.長さ;
  6. ( int i = 1; i < 長さ; i++) {
  7. for ( int j = i; j > 0 && less(array[j], array[j - 1]); j --) {  
  8. exch(配列、j、j - 1);
  9. }
  10. }
  11. }
  12.  
  13. }

コードの実装から、現在のインデックスの要素が左側の順序付き配列の最後の要素よりも大きい場合、内部ループが直接終了し、ソートする配列に部分的な順序があり、挿入ソート アルゴリズムが非常に高速になることがわかります。

最悪のケースを考えると、入力配列が反転されている場合、挿入ソートの効率は選択ソートと同じで、「時間計算量はO(n2)」です。

シェルソート

挿入ソートは、隣接する要素を交換するだけであり、要素は配列から正しい位置に少しずつしか移動できないため、大規模な順序不同の配列では遅くなります。挿入ソートは、部分的に順序付けられた配列をソートするのに非常に効率的です。

シェルソートは、これら 2 つの特性に基づいて挿入ソートを改良します。

アルゴリズム実装のアイデア

  • まず、サブ配列を分離するためのステップ サイズ h を設定します。
  • 挿入ソートを使用してhサブ配列を個別にソートする
  • hステップサイズを減らし、hステップサイズが1になるまでサブ配列のソートを続けます。
  • ステップサイズが 1 の場合、通常の挿入ソートになるため、配列は順序どおりに並んでいる必要があります。

シェル ソートが効率的な理由は、ソートの開始時に各サブ配列が非常に短く、ソート後にサブ配列が部分的に順序付けられるためです。どちらの状況も挿入ソートに非常に適しています。

コード実装:

  1. パブリッククラス ShellSort は SortTemplate を実装します {
  2.  
  3. @オーバーライド
  4. パブリックvoid ソート(比較可能な[] 配列) {
  5. ギャップ= 1;
  6. int長さ = 配列.長さ;
  7.  
  8. (ギャップ<長さ/3){
  9. ギャップ = 3 * ギャップ + 1;
  10. }
  11.  
  12. ギャップ >= 1 の場合
  13. ( int i = ギャップ; i < 長さ; i++) {
  14. for ( int j = i; j >= gap && less(array[j], array[j - gap]); j -= gap) {
  15. exch(配列、j、j - ギャップ);
  16. }
  17. }
  18. ギャップ = ギャップ / 3;
  19. }
  20. }
  21.  
  22. }

<<:  図解による古典的なプロセススケジューリングアルゴリズム

>>:  自動運転・ホログラム投影!映画に出てくるブラックテクノロジーは私たちからどれくらい遠いのでしょうか?

ブログ    

推薦する

なぜほとんどの人工知能は「人工的な知的障害」のように見えるのでしょうか?

[[431114]]当時流行した「インターネット+」を覚えている人はいるだろうか...「衣食住交通...

AI は教育にどのように役立つのでしょうか?

教育改革と人工知能の普及に伴い、キャンパスのインテリジェント構築もデジタルキャンパスからスマートキャ...

人工知能がサイバーセキュリティを変える5つの方法

人工知能は、ネットワーク セキュリティの攻撃側と防御側の両方で重要な役割を果たす中立的なテクノロジで...

ChatGPTヘルプ! 4歳の男の子は3年間で17人の専門医に治療を受けたが、効果はなかった。大型模型が病気の原因を正確に特定した

3年間「奇妙な病気」の治療を求めても効果がなかったのですが、ついにChatGPTによって診断に成功し...

製造業における機械学習

機械学習と人工知能:違いは何ですか?機械学習は人工知能のサブフィールドですが、すべての人工知能技術が...

Google VideoPoet の責任者 Jiang Lu が TikTok に参入しました! AIビデオモデル戦争が迫る

OpenAIを去った技術の第一人者、カルパシー氏はついにオンラインで2時間のAI講座を開始した。 —...

中国でApp Storeのランキング操作を禁止しアルゴリズムを調整

国内アプリプロモーション機関APPYINGはこのほど、アップルのApp Store Chinaランキ...

人工知能が都市の健康に革命をもたらす方法

今日、健康は精神的、社会的、政治的、経済的、都市的健康など、さまざまな分野に関連しています。今日、都...

強化学習を使用して、顧客が注目する広告を選択する方法

[51CTO.com クイック翻訳] 現在、世界中のデジタル広告代理店は、ニュースサイト、検索エンジ...

...

...

人工知能はスマートシティの夢の実現にどのように役立つか

2008 年の金融危機後、都市計画とサービス提供に対する新しいアプローチが世界中で定着し始めました。...

2025年までに世界のAIヘルスケア市場は272億ドルに達する

4月17日、市場調査会社リサーチ・アンド・マーケッツが最近発表したレポートでは、2025年までに世界...

AI時代のセキュリティ情勢にはどのような新たな変化が起こっているのでしょうか?

近年、世界の人工知能産業は急速な発展の勢いを見せており、セキュリティ状況はますます複雑になっています...

GPT-4ではMITでコンピュータサイエンスの学位を取得できない

ある研究者が、MITのコンピューターサイエンスの学位の宿題や試験問題を解くことができると主張するチャ...