Objective-C でのソートアルゴリズムを学ぶ

データ構造とアルゴリズムを学習していたとき、ソートアルゴリズムをアニメーションで表現して、理解しやすく覚えやすくしてみました。この記事は、[Demo Learning Data Structures and Algorithms in Object-C - Sorting Algorithm](https://github.com/MisterBooo/Play-With-Sort-OC)と合わせて読むと良いでしょう。

目次

* 選択ソート

* バブルソート

* 挿入ソート

* クイックソート

* 双方向クイックソート

* 3ウェイクイックソート

* ヒープソート

* まとめと収穫

* 参考文献と参考文献

選択ソート

選択ソートは、シンプルで直感的なソートアルゴリズムです。どのようなデータが入力されても、時間の計算量は O(n?) です。したがって、使用する場合、データサイズが小さいほど良いです。唯一の利点は、余分なメモリスペースを占有しないことです。

1. アルゴリズムの手順

1. まず、ソートされていないシーケンス内の最小（最大）の要素を見つけ、それをソートされたシーケンスの先頭に格納します。

2. 残りのソートされていない要素から最小 (最大) の要素を探し続け、それをソートされたシーケンスの最後に配置します。

3. すべての要素がソートされるまで手順 2 を繰り返します。

2. コードの実装

#pragma mark - /**選択ソート*/  
 - ( void )mb_selectionSort{
 ( int i = 0; i < self.count; i++) {
 ( int j = i + 1; j < self.count; j++) {
 （self.comparator（self[i]、self[j]）== NSOrderedDescending）の場合{
                [自分自身 mb_exchangeWithIndexA:i indexB:j];
            }
        }
    }
 }

バブルソート

バブルソートもシンプルで直感的なソートアルゴリズムです。ソートする配列を繰り返し処理し、一度に 2 つの要素を比較して、順序が間違っている場合はそれらを交換します。シーケンスを訪問する作業は、交換が不要になるまで、つまりシーケンスがソートされるまで繰り返されます。このアルゴリズムの名前は、小さな要素が交換を通じてゆっくりとシーケンスの先頭に「浮かんで」いくという事実に由来しています。

1. アルゴリズムの手順

1. 隣接する要素を比較します。最初の値が 2 番目の値より大きい場合は、それらを交換します。

2. 先頭の最初のペアから最後のペアまで、隣接する要素の各ペアに対して同じ操作を実行します。このステップが完了すると、*** 要素は *** 数値になります。

3. 最後の要素を除くすべての要素に対して上記の手順を繰り返します。

4. 比較する必要のある数値のペアがなくなるまで、要素の数を減らしながら上記の手順を繰り返します。

2. コードの実装

#pragma mark - /**バブルソート*/  
 - ( void )mb_bubbleSort{
    bool が交換されました。
する{
        スワップ = false ;
 ( int i = 1; i < self.count; i++) {
 （self.comparator（self[i - 1]、self[i]）== NSOrderedDescending）の場合{
                スワップ = true ;
                [自分自身 mb_exchangeWithIndexA:i indexB:i- 1];
            }
        }
    } while (スワップ済み);
 }

挿入ソート

挿入ソートのコード実装はバブルソートや選択ソートほど単純で粗雑ではありませんが、その原理は最も理解しやすいはずです。ポーカーをプレイしたことがある人なら誰でも数秒で理解できるはずです。挿入ソートは、最も単純で直感的なソート アルゴリズムです。順序付けられたシーケンスを構築することで機能します。ソートされていないデータの場合は、ソートされたシーケンスの後ろから前へスキャンし、対応する位置を見つけて挿入します。

1. アルゴリズムの手順

1. ソートするシーケンスの最初の要素を順序付きシーケンスとして扱い、最初の要素の 2 番目の要素をソートされていないシーケンスとして扱います。

2. ソートされていないシーケンスを最初から最後までスキャンし、スキャンした各要素を順序付けられたシーケンスの適切な位置に挿入します。 (挿入する要素が順序付けられたシーケンス内の要素と等しい場合、挿入する要素は等しい要素の後に挿入されます。)

2. コードの実装

#pragma mark - /**挿入ソート*/  
 - ( void )mb_insertionSort{
 ( int i = 0; i < self.count; i++) {
        id e = 自己[i];
整数j;
 ( j = i; j > 0 && self.comparator(self[j - 1],e) == NSOrderedDescending; j--) {
            [自己 mb_exchangeWithIndexA:j インデックスB:j- 1];
        }
        自己[j] = e;
    }
 }

マージソート

マージソートは、マージ操作に基づいた効果的なソートアルゴリズムです。このアルゴリズムは、分割統治法の非常に典型的な応用です。

分割統治の考え方の典型的なアルゴリズムの応用として、マージソートは次の 2 つの方法で実装されます。

>1. トップダウン再帰（すべての再帰メソッドは反復を使用して書き換えることができるため、2番目のメソッドがあります）

>2. ボトムアップの反復

この記事では**トップダウン**マージソートを使用しています

1. アルゴリズムの手順

1. ソートされた 2 つのシーケンスの合計に等しいサイズのスペースを申請します。このスペースは、結合されたシーケンスを格納するために使用されます。

2. 2 つのソートされたシーケンスの開始位置を初期位置とする 2 つのポインタを設定します。

3. 2 つのポインタが指す要素を比較し、比較的小さい要素を選択してマージ スペースに配置し、ポインタを次の位置に移動します。

4. ポインタがシーケンスの末尾に到達するまで手順 3 を繰り返します。

5. 他のシーケンスの残りの要素をすべて、結合されたシーケンスの末尾に直接コピーします。

2. コードの実装

#pragma mark - /**上から下へのマージソート*/  
 - ( void )mb_mergeSort{
    [self mb_mergeSortArray:self 左インデックス:0 右インデックス:( int )self.count - 1];
 }
 - ( void )mb_mergeSortArray:(NSMutableArray *)配列 左インデックス:( int )l 右インデックス:( int )r{
 (l >= r)の場合、戻り値は;
 int中間 = (l + r) / 2;
    [self mb_mergeSortArray:self 左インデックス:l 右インデックス:mid];
    [self mb_mergeSortArray:self 左インデックス:mid + 1 右インデックス:r];
    [self mb_mergeSortArray:self 左インデックス:l 中間インデックス:mid 右インデックス:r];
 }
 - ( void )mb_mergeSortArray:(NSMutableArray *)array 左インデックス:( int )l 中央インデックス:( int )mid 右インデックス:( int )r{
    SEL関数 = NSSelectorFromString(@ "resetSortArray:" );
 // 新しいスペースを開く r-l+1 スペース 
    NSMutableArray *aux = [NSMutableArray 配列の容量:r-l+1];
 for ( int i = l; i r){ // 右半分の要素がすべて処理された場合 
            自己比較子(nil, nil);
            自己[k] = 補助[i - l];
            私は++;
        }それ以外  if (self.comparator(aux[i - l], aux[j - l]) == NSOrderedAscending){ // 左半分が指す要素 < 右半分が指す要素 
            自己[k] = 補助[i - l];
            私は++;
        }それ以外{
            自己比較子(nil, nil);
            自己[k] = aux[j - l];
            j++;
        } 
          
        NSMutableArray *mutArray = [NSMutableArray 配列];
        [self enumerateObjectsUsingBlock:^(MBBarView * _Nonnull obj、NSUInteger idx、BOOL * _Nonnull stop) {
            [mutArray addObject:[NSString stringWithFormat:@ "%f" ,obj.frame.size.height]];
        }]; 
          
        objc_msgSendSortArray(self.vc,func,mutArray);
    }
 }

クイックソート

クイックソートは、Tony Hall によって開発されたソートアルゴリズムです。平均すると、n 個の項目をソートするには O(nlogn) 回の比較が必要です。最悪の場合、O(n2) 回の比較が必要になりますが、これはまれです。実際、クイックソートは、その内部ループがほとんどのアーキテクチャで効率的に実装できるため、他の O(nlogn) アルゴリズムよりも大幅に高速になることがよくあります。

クイックソートでは、分割統治戦略を使用してリストを 2 つのサブリストに分割します。

クイックソートは、ソートアルゴリズムにおける分割統治の考え方のもう 1 つの典型的な応用です。本質的に、クイックソートはバブルソートに基づく再帰的な分割統治法とみなされるべきです。

クイック ソートという名前は単純で大雑把です。この名前を聞くと、その存在目的が高速かつ効率的であることがすぐにわかるからです。これは、大規模データに対する最も高速なソート アルゴリズムの 1 つです。

1. アルゴリズムの手順

1. シーケンスから「ピボット」と呼ばれる要素を選択します。

2. 基本値より小さいすべての要素が基本値の前に配置され、基本値より大きいすべての要素が基本値の後に配置されるようにシーケンスを並べ替えます (同じ数字をどちらの側にも配置できます)。このパーティションを抜けると、ベンチマークはシリーズの途中になります。これはパーティション操作と呼ばれます。

3. 基本値より小さい要素の部分列と基本値より大きい要素の部分列を再帰的にソートします。

クイックソートの最適化では、パーティション間隔が小さい場合に挿入ソートを使用することが考えられます。

2. コードの実装

#pragma mark - /**クイックソート*/  
 - ( void )mb_quickSort{
 // 国境の状況に特に注意してください 
    [self mb_quickSort:self indexL:0 indexR: (int )self.count - 1];
 }
 - ( void )mb_quickSort:(NSMutableArray *)配列インデックスL:( int )l インデックスR:( int )r{
 (l >= r)の場合、戻り値は;
 int p = [self __partition:配列 indexL:l indexR:r];
    [self mb_quickSort:配列インデックスL:l インデックスR:p-1];
    [self mb_quickSort:配列 indexL:p + 1 indexR:r];
 }
 /**
 arr[l...r]に対してパーティション操作を実行する
 arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p] となるようなpを返す
  
 @param 配列 配列
 @param l 左
 @param r 右
 @return pを返す
 */  
 - ( int )__partition:(NSMutableArray *)配列インデックスL:( int )l インデックスR:( int )r{
 int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v  
 ( int i = l + 1; i <= r; i++)の場合{
 （self.comparator（配列[i]、配列[l]）== NSOrderedAscending）の場合）{
            j++;
 //交換 
            [自己 mb_exchangeWithIndexA:j インデックスB:i];
        }
    }
    自己比較子(nil, nil);
    [自己 mb_exchangeWithIndexA:j インデックスB:l];
 jを返します。
 }

マルチウェイクイックソート

重複キーが多すぎると、クイックソートは O(n^2) に減少します。

ダブルクイックソートを使用すると、クイックソートアルゴリズムは多数の要素を含む配列を簡単に処理できるようになります。

クイックソートの最適化では、パーティション間隔が小さい場合に挿入ソートを使用することが考えられます。

1. アルゴリズム図

2. コードの実装

#pragma mark - /**双方向高速ソート*/  
 ///ダブルクイックソートを使用した後、クイックソートアルゴリズムは多数の要素を含む配列を簡単に処理できます 
 - ( void )mb_identicalQuickSort{
 // 国境の状況に特に注意してください 
    [self mb_quickSort:self indexL:0 indexR: (int )self.count - 1];
 }
 - ( void )mb_identicalQuickSort:(NSMutableArray *)配列インデックスL:( int )l インデックスR:( int )r{
 (l >= r)の場合、戻り値は;
 int p = [self __partition2:配列 indexL:l indexR:r];
    [self mb_quickSort:配列インデックスL:l インデックスR:p-1];
    [self mb_quickSort:配列 indexL:p + 1 indexR:r];
 }
 - ( int )__partition2:(NSMutableArray *)配列インデックスL:( int )l インデックスR:( int )r{
 // ピボットポイントとしてarr[l...r]の範囲内の値をランダムに選択する 
    [自己 mb_exchangeWithIndexA:l indexB:(arc4random()%(r-l+1))];
    id v = 配列[l];
 // arr[l+1...i) = v  
 i = l + 1、j = r;
 （真）の間{ 
          
 (i l + 1 && self.comparator(array[j],v) == NSOrderedDescending)の間
            j--; 
          
もし（i>j）{
壊す;
        }
        [自分自身 mb_exchangeWithIndexA:i indexB:j]; 
          
        私は++;
        j--;
    }
    [自己 mb_exchangeWithIndexA:l indexB:j];
 jを返します。
 }

3ウェイクイックソート

大量の繰り返しデータを含む配列の場合、3方向クイックソートは大きな利点がある。

一般的なランダム配列やほぼ順序付けられた配列の場合、3 方向クイックソートの効率は完璧ではありませんが、非常に許容できる範囲内です。

したがって、一部の言語では、3 方向クイック ソートが言語ライブラリ関数で使用されるデフォルトのソート アルゴリズムになります。たとえば、Java :)

クイックソートの最適化では、パーティション間隔が小さい場合に挿入ソートを使用することが考えられます。

1. アルゴリズム図

2. コードの実装

#pragma mark - /**3方向高速ソート*/  
 // 大量の繰り返しデータを含む配列の場合、3方向クイックソートには大きな利点があります 
 - ( void )mb_quick3WaysSort{
 // 国境の状況に特に注意してください 
    [self mb_quick3WaysSort:self indexL:0 indexR: (int )self.count - 1];
 }
 /// 再帰的な3方向クイックソートアルゴリズム 
 - ( void )mb_quick3WaysSort:(NSMutableArray *)配列インデックスL:( int )l インデックスR:( int )r{
 (l >= r)の場合、戻り値は; 
      
    自己比較子(nil, nil);
 // ピボットポイントとしてarr[l...r]の範囲内の値をランダムに選択する 
    [自己 mb_exchangeWithIndexA:l indexB:(arc4random_uniform(r-l+1) + l)]; 
      
    id v = 配列[l]; 
      
 int lt = l; // 配列[l+1...lt] < v  
 int gt = r + 1; // 配列[gt...r] > v  
 int i = l + 1; // 配列[lt+1...i) == v   
      
 （i < gt） {
 if ( [self compareWithBarOne:array[i] andBarTwo:v] == NSOrderedAscending) {
            自己比較子(nil, nil);
            [自分自身 mb_exchangeWithIndexA:i indexB:lt + 1];
            私は++;
            lt++;
        }それ以外  if ([self compareWithBarOne:array[i] andBarTwo:v] == NSOrderedDescending){
            自己比較子(nil, nil);
            [自分自身 mb_exchangeWithIndexA:i indexB:gt - 1];
            gt--;
        }そうでない場合{ //配列[i] == v  
            私は++;
        }
    }
    自己比較子(nil,nil);
    [自己 mb_exchangeWithIndexA:l indexB:lt];
    [self mb_quick3WaysSort:配列インデックスL:l インデックスR:lt-1];
    [self mb_quick3WaysSort:配列インデックスL:gtインデックスR:r]; 
      
 }

積み重ね順序

ヒープソートとは、ヒープ データ構造を使用して設計されたソート アルゴリズムを指します。スタックは、完全な二分木を近似し、スタックの特性を満たす構造です。つまり、子ノードのキー値またはインデックスは常に親ノードよりも小さい (または大きい) です。ヒープソートは、ヒープの概念を使用してソートする選択ソートであると言えます。方法は2つあります。

最大トップヒープ: 各ノードの値は、その子ノードの値以上であり、ヒープソートアルゴリズムの昇順のために使用されます。

ミニトップヒープ: 各ノードの値は、その子ノードの値以下であり、ヒープソートアルゴリズムの降順のために使用されます。

ヒープソートの平均時間計算量は O(nlogn) です。

1. アルゴリズムの手順

1. ヒープH[0...n-1]を作成します。

2. ヒープ先頭 (最高値) とヒープ末尾を交換します。

3. ヒープサイズを1減らし、shift_down(1)を呼び出して、新しい配列の先頭データを対応する位置に調整します。

4. ヒープサイズが1になるまで手順2を繰り返します。

2. コードの実装

///shift_down 操作 
 - ( void )shiftDown:( int )k{
 （2 * k <= _count）の間{
整数j = 2 * k;
 if (j + 1 <= _count && [self heapCompareWithBarOne:_data[j + 1] andBarTwo:_data[j]] == NSOrderedDescending) j++; //左の子は右の子より小さい 
 if ([self heapCompareWithBarOne:_data[k] andBarTwo:_data[j]] == NSOrderedDescending) break ; //親ノードは子ノードより大きい 
        自己比較子(nil, nil);
        [_data mb_exchangeWithIndexA:k インデックスB:j];
        ｋ＝ｊ；
    }
 }

終わりと収穫

要約:

データ構造とアルゴリズムを再学習する過程で、私はこれらのいわゆる**基礎知識**を学ぶことの重要性を十分に認識し、iOS開発のレベルをさらに向上させるためには、基本的なリンクを無視することはできないことを理解しました。また、この研究では、グラフのディープトラバーサルを使用して、埋もれたポイントを研究する過程でバックトラックソースを見つける問題を解決しました。

利益:

> 1. 基本的なソートホワイトボードプログラミング

> 2. ランタイムにカテゴリを追加する

> 3. ランタイムの objc_msgSend()

> 4. ディープコピーとシャローコピー

> 5. GCDセマフォの使用

これを読んで何か得られたものがあれば、[Github](https://github.com/MisterBooo/Play-With-Sort-OC)** でスターを付けてください。

参考文献と参考文献

* [ソートアルゴリズムに関する GitBook オンライン ブック、「Top Ten Classic Sorting Algorithms」、JavaScript、Python、Go で実装](https://github.com/hustcc/JS-Sorting-Algorithm)

* [JavaScript でデータ構造とアルゴリズムを学ぶ](https://juejin.im/post/594dfe795188250d725a220a)

* [ソートアニメーション](https://github.com/JiongXing/JXSort)