目次
はじめに
クイック ソートの背後にあるロジックを理解する
ホームページ ウェブフロントエンド jsチュートリアル JavaScript のクイックソートの詳細な分析

JavaScript のクイックソートの詳細な分析

Oct 28, 2020 pm 05:47 PM
javascript フロントエンド クイックソート アルゴリズム

JavaScript のクイックソートの詳細な分析

はじめに

並べ替えとは、線形リストの要素を特定の順序 (数値またはアルファベット順) で配置することを指します。並べ替えは、多くの場合、検索と組み合わせて使用​​されます。

並べ替えアルゴリズムは数多くありますが、これまでで最も高速なものの 1 つは Quicksort(Quicksort) です。

クイックソートは、分割統治戦略を使用して、指定されたリスト要素を並べ替えます。これは、サブ問題が直接解決できるほど単純になるまで、アルゴリズムが問題をサブ問題に分割することを意味します。

アルゴリズム的には、これは再帰またはループを使用して実現できます。しかし、この問題では再帰を使用する方が自然です。

クイック ソートの背後にあるロジックを理解する

最初にクイック ソートの仕組みを見てみましょう:

  1. 配列内の要素を選択します。この要素は Benchmark と呼ばれます(ピボット)###。通常、配列内の最初または最後の要素が基礎として使用されます。
  2. 次に、ピボットの左側のすべての要素がピボットより小さく、右側のすべての要素がピボットより大きくなるように、配列の要素を再配置します。このステップは
  3. パーティショニング と呼ばれます。要素がベースと等しい場合、それがどちら側にあるかは関係ありません。
  4. 配列がソートされるまで、ベンチマークの左側と右側でこのプロセスを繰り返します。
次に、例を通してこれらの手順を理解します。ソートされていない要素

[7, -2, 4, 1, 6, 5, 0, -4, 2] を含む配列があるとします。最後の要素をベースとして選択します。配列の分解ステップを以下の図に示します。

JavaScript のクイックソートの詳細な分析

アルゴリズムのステップ 1 でベースとして選択された要素が色付けされます。分割後、基本要素は常に配列内の正しい位置にあります。

太字の黒い境界線が付いた配列は、その特定の再帰的分岐の最後でどのようになるかを表しており、結果として得られる配列には 1 つの要素のみが含まれます。

最後に、アルゴリズムの結果の並べ替えを確認できます。

JavaScript を使用してクイック ソートを実装する

このアルゴリズムのバックボーンは「パーティショニング」ステップです。再帰を使用するかループを使用するかに関係なく、この手順は同じです。

配列分割のコードが最初に記述されるのはまさにこの機能のためです。

partition():

function partition(arr, start, end){
    // 以最后一个元素为基准
    const pivotValue = arr[end];
    let pivotIndex = start; 
    for (let i = start; i < end; i++) {
        if (arr[i] < pivotValue) {
        // 交换元素
        [arr[i], arr[pivotIndex]] = [arr[pivotIndex], arr[i]];
        // 移动到下一个元素
        pivotIndex++;
        }
    }
    
    // 把基准值放在中间
    [arr[pivotIndex], arr[end]] = [arr[end], arr[pivotIndex]] 
    return pivotIndex;
};
ログイン後にコピー

コードは最後の要素に基づいており、変数

pivotIndex を使用して、左側のすべての要素が pivotValue より小さく、右側の要素が pivotValue より大きい「中間」位置を追跡します。

最後のステップでは、ピボット (最後の要素) を

pivotIndex と交換します。

再帰的実装

partition() 関数を実装した後、問題を再帰的に解決し、パーティショニング ロジックを適用して残りの手順を完了する必要があります。 #この関数では、まず配列が分割され、次に左右の部分配列が分割されます。この関数が空でない配列、または複数の要素を含む配列を受け取る限り、このプロセスは繰り返されます。

空の配列と 1 つの要素のみを含む配列は、並べ替えられているとみなされます。

最後に、次の例を使用してテストします。

function quickSortRecursive(arr, start, end) {
    // 终止条件
    if (start >= end) {
        return;
    }
    
    // 返回 pivotIndex
    let index = partition(arr, start, end);
    
    // 将相同的逻辑递归地用于左右子数组
    quickSort(arr, start, index - 1);
    quickSort(arr, index + 1, end);
}
ログイン後にコピー

出力:

array = [7, -2, 4, 1, 6, 5, 0, -4, 2]
quickSortRecursive(array, 0, array.length - 1)

console.log(array)
ログイン後にコピー

ループ実装

クイック ソートの再帰的方法は、より直感的です。ただし、ループを使用してクイック ソートを実装することは、面接で比較的よくある質問です。

ほとんどの再帰的からループへの変換ソリューションと同様に、最初に思い浮かぶのは、スタックを使用して再帰的呼び出しをシミュレートすることです。これにより、使い慣れた再帰ロジックを再利用してループ内で使用できるようになります。

残りの未ソートの部分配列を追跡する方法が必要です。 1 つのアプローチは、特定のソートされていない部分配列の

start

end を表す要素の「ペア」をスタック上に単純に保持することです。 JavaScript には明示的なスタック データ構造がありませんが、配列は push()

関数と

pop() 関数をサポートします。ただし、peek() 関数はサポートされていないため、stack [stack.length-1] を使用してスタックの先頭を手動で確認する必要があります。 再帰的方法と同じ「分割」機能を使用します。クイックソート部分の書き方を見てみましょう:

-4,-2,0,1,2,4,5,6,7
ログイン後にコピー

テスト コードは次のとおりです:

function quickSortIterative(arr) {
    // 用push()和pop()函数创建一个将作为栈使用的数组
    stack = [];
    
    // 将整个初始数组做为“未排序的子数组”
    stack.push(0);
    stack.push(arr.length - 1);
    
    // 没有显式的peek()函数
    // 只要存在未排序的子数组,就重复循环
    while(stack[stack.length - 1] >= 0){
        
        // 提取顶部未排序的子数组
        end = stack.pop();
        start = stack.pop();
        
        pivotIndex = partition(arr, start, end);
        
        // 如果基准的左侧有未排序的元素,
        // 则将该子数组添加到栈中,以便稍后对其进行排序
        if (pivotIndex - 1 > start){
            stack.push(start);
            stack.push(pivotIndex - 1);
        }
        
        // 如果基准的右侧有未排序的元素,
        // 则将该子数组添加到栈中,以便稍后对其进行排序
        if (pivotIndex + 1 < end){
            stack.push(pivotIndex + 1);
            stack.push(end);
        }
    }
}
ログイン後にコピー

出力:

ourArray = [7, -2, 4, 1, 6, 5, 0, -4, 2]
quickSortIterative(ourArray)

console.log(ourArray)
ログイン後にコピー

ビジュアル デモンストレーション

並べ替えアルゴリズムについて言えば、それらを視覚化すると、アルゴリズムがどのように機能するかを直感的に理解するのに役立ちます。次の例は Wikipedia からの引用です:

図の最後の要素は、基準。分割された配列を指定して、完全にソートされるまで左側を再帰的に走査します。次に右側を並べ替えます。 JavaScript のクイックソートの詳細な分析

クイックソートの効率

次に、その時間と空間の複雑さについて説明します。クイック ソートの最悪の場合の時間計算量は $O(n^2)$ です。平均時間計算量は $O(n\log n)$ です。通常、最悪のシナリオは、ランダム化されたバージョンのクイックソートを使用することで回避できます。

クイックソート アルゴリズムの弱点は、ベンチマークの選択です。間違ったピボット (ほとんどの要素よりも大きいまたは小さいピボット) を選択するたびに、時間計算量は最悪の状態になります。基底を繰り返し選択するときに、要素の値が要素の基底より小さいか大きい場合、時間計算量は $O(n\log n)$ になります。

どのデータ ベンチマーク選択戦略が採用されても、クイック ソートの時間計算量は $O(n\log n)$ になる傾向があることが経験から観察できます。

クイックソートは追加のスペースを必要としません (再帰呼び出し用に予約されたスペースを除く)。このアルゴリズムは in-place アルゴリズムと呼ばれ、余分なスペースは必要ありません。

プログラミング関連の知識について詳しくは、プログラミング入門をご覧ください。 !

以上がJavaScript のクイックソートの詳細な分析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

CLIP-BEVFormer: BEVFormer 構造を明示的に監視して、ロングテール検出パフォーマンスを向上させます。 CLIP-BEVFormer: BEVFormer 構造を明示的に監視して、ロングテール検出パフォーマンスを向上させます。 Mar 26, 2024 pm 12:41 PM

上記および筆者の個人的な理解: 現在、自動運転システム全体において、認識モジュールが重要な役割を果たしている。道路を走行する自動運転車は、認識モジュールを通じてのみ正確な認識結果を得ることができる。下流の規制および制御モジュール自動運転システムでは、タイムリーかつ正確な判断と行動決定が行われます。現在、自動運転機能を備えた自動車には通常、サラウンドビューカメラセンサー、ライダーセンサー、ミリ波レーダーセンサーなどのさまざまなデータ情報センサーが搭載されており、さまざまなモダリティで情報を収集して正確な認識タスクを実現しています。純粋な視覚に基づく BEV 認識アルゴリズムは、ハードウェア コストが低く導入が容易であるため、業界で好まれており、その出力結果はさまざまな下流タスクに簡単に適用できます。

C++ での機械学習アルゴリズムの実装: 一般的な課題と解決策 C++ での機械学習アルゴリズムの実装: 一般的な課題と解決策 Jun 03, 2024 pm 01:25 PM

C++ の機械学習アルゴリズムが直面する一般的な課題には、メモリ管理、マルチスレッド、パフォーマンスの最適化、保守性などがあります。解決策には、スマート ポインター、最新のスレッド ライブラリ、SIMD 命令、サードパーティ ライブラリの使用、コーディング スタイル ガイドラインの遵守、自動化ツールの使用が含まれます。実践的な事例では、Eigen ライブラリを使用して線形回帰アルゴリズムを実装し、メモリを効果的に管理し、高性能の行列演算を使用する方法を示します。

C++sort 関数の基礎となる原則とアルゴリズムの選択を調べる C++sort 関数の基礎となる原則とアルゴリズムの選択を調べる Apr 02, 2024 pm 05:36 PM

C++sort 関数の最下層はマージ ソートを使用し、その複雑さは O(nlogn) で、クイック ソート、ヒープ ソート、安定したソートなど、さまざまなソート アルゴリズムの選択肢を提供します。

PHP と Vue: フロントエンド開発ツールの完璧な組み合わせ PHP と Vue: フロントエンド開発ツールの完璧な組み合わせ Mar 16, 2024 pm 12:09 PM

PHP と Vue: フロントエンド開発ツールの完璧な組み合わせ 今日のインターネットの急速な発展の時代において、フロントエンド開発はますます重要になっています。 Web サイトやアプリケーションのエクスペリエンスに対するユーザーの要求がますます高まっているため、フロントエンド開発者は、より効率的で柔軟なツールを使用して、応答性の高いインタラクティブなインターフェイスを作成する必要があります。フロントエンド開発の分野における 2 つの重要なテクノロジーである PHP と Vue.js は、組み合わせることで完璧なツールと見なされます。この記事では、PHP と Vue の組み合わせと、読者がこれら 2 つをよりよく理解し、適用できるようにするための詳細なコード例について説明します。

フロントエンドの面接官からよく聞かれる質問 フロントエンドの面接官からよく聞かれる質問 Mar 19, 2024 pm 02:24 PM

フロントエンド開発のインタビューでは、HTML/CSS の基本、JavaScript の基本、フレームワークとライブラリ、プロジェクトの経験、アルゴリズムとデータ構造、パフォーマンスの最適化、クロスドメイン リクエスト、フロントエンド エンジニアリング、デザインパターン、新しいテクノロジーとトレンド。面接官の質問は、候補者の技術スキル、プロジェクトの経験、業界のトレンドの理解を評価するように設計されています。したがって、候補者はこれらの分野で自分の能力と専門知識を証明するために十分な準備をしておく必要があります。

改良された検出アルゴリズム: 高解像度の光学式リモートセンシング画像でのターゲット検出用 改良された検出アルゴリズム: 高解像度の光学式リモートセンシング画像でのターゲット検出用 Jun 06, 2024 pm 12:33 PM

01 今後の概要 現時点では、検出効率と検出結果の適切なバランスを実現することが困難です。我々は、光学リモートセンシング画像におけるターゲット検出ネットワークの効果を向上させるために、多層特徴ピラミッド、マルチ検出ヘッド戦略、およびハイブリッドアテンションモジュールを使用して、高解像度光学リモートセンシング画像におけるターゲット検出のための強化されたYOLOv5アルゴリズムを開発しました。 SIMD データセットによると、新しいアルゴリズムの mAP は YOLOv5 より 2.2%、YOLOX より 8.48% 優れており、検出結果と速度のバランスがより優れています。 02 背景と動機 リモート センシング技術の急速な発展に伴い、航空機、自動車、建物など、地表上の多くの物体を記述するために高解像度の光学式リモート センシング画像が使用されています。リモートセンシング画像の判読における物体検出

人工知能は犯罪を予測できるのか? CrimeGPT の機能を調べる 人工知能は犯罪を予測できるのか? CrimeGPT の機能を調べる Mar 22, 2024 pm 10:10 PM

人工知能 (AI) と法執行機関の融合により、犯罪の予防と検出の新たな可能性が開かれます。人工知能の予測機能は、犯罪行為を予測するためにCrimeGPT (犯罪予測技術) などのシステムで広く使用されています。この記事では、犯罪予測における人工知能の可能性、その現在の応用、人工知能が直面する課題、およびこの技術の倫理的影響について考察します。人工知能と犯罪予測: 基本 CrimeGPT は、機械学習アルゴリズムを使用して大規模なデータセットを分析し、犯罪がいつどこで発生する可能性があるかを予測できるパターンを特定します。これらのデータセットには、過去の犯罪統計、人口統計情報、経済指標、気象パターンなどが含まれます。人間のアナリストが見逃す可能性のある傾向を特定することで、人工知能は法執行機関に力を与えることができます

58 ポートレート プラットフォームの構築におけるアルゴリズムの適用 58 ポートレート プラットフォームの構築におけるアルゴリズムの適用 May 09, 2024 am 09:01 AM

1. 58 Portraits プラットフォーム構築の背景 まず、58 Portraits プラットフォーム構築の背景についてお話ししたいと思います。 1. 従来のプロファイリング プラットフォームの従来の考え方ではもはや十分ではありません。ユーザー プロファイリング プラットフォームを構築するには、複数のビジネス分野からのデータを統合して、ユーザーの行動や関心を理解するためのデータ マイニングも必要です。最後に、ユーザー プロファイル データを効率的に保存、クエリ、共有し、プロファイル サービスを提供するためのデータ プラットフォーム機能も必要です。自社構築のビジネス プロファイリング プラットフォームとミドルオフィス プロファイリング プラットフォームの主な違いは、自社構築のプロファイリング プラットフォームは単一のビジネス ラインにサービスを提供し、オンデマンドでカスタマイズできることです。ミッドオフィス プラットフォームは複数のビジネス ラインにサービスを提供し、複雑な機能を備えていることです。モデリングを提供し、より一般的な機能を提供します。 2.58 中間プラットフォームのポートレート構築の背景のユーザーのポートレート 58

See all articles