Objective-C 実装と主要なソートアルゴリズムのグラフィカルなデモンストレーション比較

[[176714]]

Objective-C を使用していくつかの基本的なソートアルゴリズムを実装し、ソートプロセスをグラフィカルに表示します。実はこのアルゴリズムはかなり面白いんです^ ^。

選択ソート
バブルソート
挿入ソート
クイックソート

選択ソート

昇順を例に挙げます。

選択ソートは比較的理解しやすいです。一言で言えば、この位置を埋めるために、その位置に適した要素を選択することです。

最初の要素を一時的に最小の要素として決定し、逆方向に走査して、それらを 1 つずつ最小の要素と比較します。より小さい要素が見つかった場合は、その位置を前の「最小の要素」と入れ替えます。最小要素を更新するという目的を達成します。
トラバーサルが完了したら、完了したトラバーサル内の最小の要素が先頭に配置されていることが保証されます。次に、ソート範囲が絞り込まれ、配列の 2 番目の要素から新しいソートが開始されます。
範囲を絞り込めなくなり、ソートが完了するまで、新しいソートラウンドで手順 1 と 2 を繰り返します。

選択ソート

次のメソッドはNSMutableArray+JXSort.mに実装されています

- (void)jx_selectionSortUsingComparator:(JXSortComparator)コンパレータdidExchange:(JXSortExchangeCallback)exchangeCallback {  
 （自己カウント== 0）の場合{  
戻る;  
 }  
 (NSInteger i = 0; i < self.count - 1; i++)の場合{
 (NSInteger j = i + 1; j < self.count ; j++)の場合{  
比較演算子(self[i], self[j]) == NSOrderedDescending) {  
 [自己 jx_exchangeWithIndexA:i indexB:j didExchange:exchangeCallback];  
 }  
 }  
 }  
 }

バブルソート

トラバーサルでは、隣接する 2 つの要素が連続的にソートされ、小さい方の要素が前に、大きい方の要素が後ろに配置されます。これにより、大きい方の値が下に移動します。トラバーサルが完了すると、最小の要素が後ろの正しい位置に配置されます。

次に、ソート範囲を狭めます。つまり、最初の側の正しい位置にある要素を削除し、フロント配列で新しいトラバーサルラウンドを実行して、手順 1 を繰り返します。範囲を縮小できなくなるまでソートは完了します。

バブルソート

- (void)jx_bubbleSortUsingComparator:(JXSortComparator)コンパレータ didExchange:(JXSortExchangeCallback)exchangeCallback {  
 （自己カウント== 0）の場合{  
戻る;  
 }  
 (NSInteger i = self.count - 1; i > 0; i --)の場合{    
 (NSInteger j = 0; j < i; j++)の場合{  
比較演算子(self[j], self[j + 1]) == NSOrderedDescending) {  
 [自己 jx_exchangeWithIndexA:j indexB:j + 1 didExchange:exchangeCallback];  
 }  
 }  
 }  
 }

挿入ソート

挿入ソートは、ランダムな配列から順番に値を取得し、すでにソートされた配列に挿入します。

これを実現するには 2 つの配列が必要であるように思われるかもしれませんが、同じ配列内で並べ替えるだけであれば問題ありません。この時点で、前方の整然とした領域と後方の無秩序な領域の 2 つの領域を想像する必要があります。

1. パーティション。最初は、先頭の順序付けられた領域に要素が 1 つだけあり、これが配列の最初の要素になります。次に、配列の 2 番目の要素から最後までをランダム順序領域として取得します。

2. 順序が乱れた領域から最初の要素を取得し、それを前の順序どおりの領域に正しく挿入します。それを前の順序付けされていない領域の最後の要素、つまりその前の要素と比較します。

前の要素より大きい場合は、交換する必要はありません。このとき、整列領域は 1 グリッド拡張され、無秩序領域は 1 グリッド縮小されます。これは、整列領域の末尾に直接接合することと同等です。
前の要素と等しい場合は、前の 2 つの要素と比較を続け、次に前の 3 つの要素と比較します...最後までトラバースして、前のすべての要素の値が同じ (囧) であることがわかった場合は、問題ありません。交換する必要はありません。その後、順序付き領域が 1 グリッド拡張され、ランダム領域が 1 グリッド縮小されます。これは、順序付き領域の末尾で直接スプライスすることと同じです。前の要素よりも大きい場合はどうなりますか? 申し訳ありませんが、順序付けられた領域ではこれは不可能です。前の要素より小さい場合は、次のポイントを参照してください。
前の要素より小さい場合は、位置が入れ替わります。スワップ後、抽出された要素をこの時点での前の要素と比較し続けます。小さい場合はスワップします。等しい場合は、トラバーサルが完了するまで前の要素と比較します。この時点で、順序がずれた領域の最初の要素が、先頭の順序付けられた領域に正しく挿入されます。

3. 乱雑な領域の範囲を縮小し、縮小した範囲の後の最初の要素を引き続き取得し、手順 2 を繰り返します。範囲を縮小できなくなるまでソートは完了します。

挿入ソート

- (void)jx_insertionSortUsingComparator:(JXSortComparator)コンパレータ didExchange:(JXSortExchangeCallback)exchangeCallback {  
 （自己カウント== 0）の場合{  
戻る;  
 }  
 (NSInteger i = 1; i < self.count ; i++)の場合{  
 ( NSInteger j = i; j > 0 && 比較演算子(self[j], self[j - 1]) == NSOrderedAscending; j --) {    
 [自己 jx_exchangeWithIndexA:j indexB:j - 1 didExchange:exchangeCallback];  
 }  
 }  
 }

クイックソート

クイックソートにはいくつかのバージョンがあり、大まかに次のように分けられます。

オリジナルのクイックソート。
配列の順序を事前にシャッフルして、効率的なソート環境を作成するクイックソート。
多数の繰り返し値を持つ配列に最適化された 3 方向分割クイックソート。

ここでは、オリジナルのクイックソートについてのみ説明します。

クイックソート中にいつ誰を交換するかに関して、2 つの異なる考え方があります。

左カーソルと右カーソルの両方が停止したら、2 つのカーソルが指す要素を入れ替えます。ピボットの位置は、2 つのカーソルが出会って重なるまでは一時的に変更されません。その後、ピボットの位置が更新され、ピボットとカーソルが指す要素が交換されます。
右カーソルがピボットよりも小さい要素を見つけると、ピボットはすぐにカーソルの位置に交換され、カーソルの位置にある要素がピボットに移動されます。ピボット更新を完了します。次に、左カーソルはピボットよりも大きい要素を検索します。

最初のアイデアは、カーソルが出会った後にピボットを配置することで、交換の頻度を効果的に減らすことができますが、比較の数はわずかに増加します。

2 番目のアイデアでは、より頻繁なスワップ操作が行われますが、スワップ処理中もピボットの位置が継続的に更新されます。カーソルが出会うと、ピボットの配置も完了します。

両方のアイデアを実装してみましたが、やはり 2 番目のアイデアの方が好みです。スワップ操作は多くありますが、実際のスワップは配列内の特定の位置に値を割り当てるだけなので、かなり高速です。

パーティションの参照境界としてソートする配列から値を選択します。通常は最初の要素で十分です。この選択された値はピボットと呼ばれ、ソート中に配列全体の正しい位置に配置されるまで継続的に移動されます。
ソートの目的は、ピボットよりも小さい要素を前に、ピボットよりも大きい要素を後ろに、ピボットを中央に配置することです。ソートが実際に行うのは、配列を分割することのようです。次に、パーティションを完了する方法を検討します。
カーソル i はソートする配列の最初の位置を指しており、後方に移動し続けます。
ソートする配列の末尾を指す別のカーソル j を覚えておいてください。カーソル j は前方に移動し続けます。
i と j は最終的に出会うことが予測でき、出会うとソートが完了します。
次に、カーソル j を後ろから前へスキャンして、ピボットよりも小さい要素 x を探します。見つかったら停止し、この要素を最前面に投げる準備をします。
同じ配列内でソートしても配列の容量は増えないので、どうやって捨てればいいのでしょうか？
最初の要素がピボットとして選択されたため、それらの現在の位置関係は pivot ... x になります。
ソートの目標は昇順ですが、x は小さい値ですが、ピボットの後に配置されており、これは適切ではありません。それらの位置を交換する必要があります。
交換後、それらの位置関係は x ... pivot になります。このとき、j はピボットを指し、i は x を指します。
ここで、カーソル i を後方にスキャンして、ピボットよりも大きい要素 y を探し、見つかったら停止して、それをピボットと交換します。
完成した位置関係は pivot ... y です。このとき、i は pivot を指し、つまり pivot は i の位置に移動します。
ここでは小さな最適化が行われています。i が後方にスキャンを開始すると、i は x を指します。j カーソルの前のスキャンでは、x がピボットよりも小さいことがすでにわかっています。そのため、i は x をスキップできます。x をピボットと再度比較する必要はありません。
結論としては、j カーソルの交換が完了すると、i は 1 つ前の位置、i++ に戻ります。
同様に、カーソル i の交換が完了すると、j は 1 つ前方に移動し、j -- になります。
スキャン中にピボットに等しい要素が見つかった場合はどうなりますか?
3 方向パーティショニングのクイックソート最適化アルゴリズムについては説明していないため、ここでの答えは「無視する」です。
要素が 1 つずつ並べ替えられると、小さな要素によってゆっくりと押し戻され、大きな要素によって前に押し出されます。最終的には、すべての要素がピボットとともに中央の位置に移動します。
i と j が出会うと、i と j の両方がピボットを指します。パーティションメソッドでは、パーティション分割が完了した後のピボット位置である i を返します。
次に、上記の手順に従って 2 つの配列を個別に分割します。これは再帰的なプロセスです。配列をこれ以上分割できなくなると、ソートが完了します。

クイックソートは非常に優れた設計です。実装は複雑ではありませんが、重要なのは非常に高速であることです。

クイックソート.gif

 - (void)jx_quickSortUsingComparator:(JXSortComparator)コンパレータ didExchange:(JXSortExchangeCallback)exchangeCallback {  
 （自己カウント== 0）の場合{  
戻る;  
 }  
 [self jx_quickSortWithLowIndex:0 highIndex: self.count - 1 usingComparator:comparator didExchange:exchangeCallback];  
 }  
 - (void)jx_quickSortWithLowIndex:(NSInteger)low highIndex:(NSInteger)high usingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback {
 （低 >= 高）の場合 {  
戻る;  
 }  
 NSInteger pivotIndex = [self jx_quickPartitionWithLowIndex:low highIndex:high usingComparator:comparator didExchange:exchangeCallback];
 [self jx_quickSortWithLowIndex:low highIndex:pivotIndex - 1 usingComparator:comparator didExchange:exchangeCallback];
 [self jx_quickSortWithLowIndex:pivotIndex + 1 highIndex:high usingComparator:comparator didExchange:exchangeCallback];  
 }  
 - (NSInteger)jx_quickPartitionWithLowIndex:(NSInteger)low highIndex:(NSInteger)high usingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback {
 id ピボット = self[low];  
 NSInteger i = 低い;
 NSInteger j = 高さ;  
 i < j である間 {  
 // ピボット以上の要素をスキップする 
 i < j && 比較子(self[j], pivot) != NSOrderedAscending である間 {  
 j --;    
 }  
もし（i < j）{  
 // i と j が一致しないため、ピボットより小さい要素が見つかったことを示します。交換。  
 [自己 jx_exchangeWithIndexA:i indexB:j didExchange:exchangeCallback];  
私は++;  
 }  
 /// ピボット以下の要素をスキップする 
 i < j && 比較演算子(self[i], pivot) != NSOrderedDescending である間 {  
私は++;  
 }  
もし（i < j）{  
 // i と j が一致しないため、ピボットより大きい要素が見つかったことを示します。交換。  
 [自己 jx_exchangeWithIndexA:i indexB:j didExchange:exchangeCallback];  
 j --;    
 }  
 }  
 iを返します。  
 }

UI実装

それでは、UI の実装のアイデアについてお話ししましょう。

 NSMutableArray+JXSort.h

先ほどのソートコードからわかるように、NSMutableArray のカテゴリを記述し、ソートロジックはカテゴリ内に記述されており、ビューとは関係ありません。

 typedef NSComparisonResult(^JXSortComparator)(id obj1, id obj2);  
 typedef void(^JXSortExchangeCallback)(id obj1, id obj2);  
 @interface NSMutableArray (JXSort)  
 //並べ替えを選択 
 - (void)jx_selectionSortUsingComparator:(JXSortComparator)コンパレータ didExchange:(JXSortExchangeCallback)exchangeCallback;  
 // バブルソート 
 - (void)jx_bubbleSortUsingComparator:(JXSortComparator)コンパレータ didExchange:(JXSortExchangeCallback)exchangeCallback;  
 // 挿入ソート 
 - (void)jx_insertionSortUsingComparator:(JXSortComparator)コンパレータ didExchange:(JXSortExchangeCallback)exchangeCallback;  
 // クイックソート 
 - (void)jx_quickSortUsingComparator:(JXSortComparator)コンパレータ didExchange:(JXSortExchangeCallback)exchangeCallback;  
 @終わり

外部の呼び出し元は、次の 2 つのパラメータを渡すだけで済みます。

コンパレータコードブロック。これは、Apple のオリジナル API のスタイルに従って設計されています。配列内の 2 つの要素を比較する必要がある場合、ソートメソッドはこのコードブロックを呼び出し、比較する必要がある 2 つの要素を外部呼び出し元に返します。外部呼び出し元は比較ロジックを実装し、比較結果をソートメソッドに返します。
exchangeCallback コードブロック。このパラメータは、ビューの変更を実現するための鍵となります。 sort メソッドは、2 つの要素の交換が完了するたびにこのコードブロックを呼び出します。 ViewController などの外部呼び出し元は、ソート要素の位置の各変更のタイミングを把握できるため、ビューの変更を同期できます。

 - (void)jx_exchangeWithIndexA:(NSInteger)indexA indexB:(NSInteger)indexB didExchange:(JXSortExchangeCallback)exchangeCallback {  
 id temp = self[indexA];  
自己[インデックスA] = 自己[インデックスB];  
自己[インデックスB] = temp ;  
 if (exchangeCallback) {  
 exchangeCallback( temp , self[indexA]);  
 }  
 }  
ビューコントローラ.m

ビューコントローラは、ソートする配列 (ランダムな長さの 100 個の細い長方形) を保持します。

 @property (非アトミック、強力) NSMutableArray *barArray;

NSMutableArray が強化されたため、複数の指定されたソートタイプをサポートできるようになり、ソートプロセスをフィードバックできるようになりました。barArray をソートする必要がある場合は、次のように呼び出すだけです。

 - (void)クイックソート{  
 [self.barArray jx_quickSortUsingComparator:^NSComparisonResult(id obj1, id obj2) {  
 [self compareWithBarOne:obj1 andBarTwo:obj2] を返します。  
 } 交換:^(id obj1、id obj2) {  
 [自己 exchangePositionWithBarOne:obj1 および BarTwo:obj2];  
 }];  
 }

didExchange がコールバックされるたびに、ViewController は 2 つのビューの位置を交換します。これにより、連続ソートの視覚効果が生まれます。

ソート速度の制御

選別プロセスを肉眼で認識できるようにするには、選別プロセスを遅くする必要があります。

ここでの私のアプローチは、2 つの要素を比較するのにかかる時間を約 0.002 秒に延長することです。結果は明らかです。アルゴリズムが実行する必要がある比較操作が少ないほど、ソートは高速になります (上記の 4 つの図を比較すると、クイックソートが最も少ない比較操作を実行することは間違いありません)。

では、時間のかかる比較操作をどのようにシミュレートするのでしょうか?

ここでの私のアプローチは、セマフォを使用して 2 つのスレッド間で通信することです。

1. ソートは子スレッドで行います。比較操作が必要な場合は、スレッドをブロックして信号が到着するまで待ちます。ここでの考え方は、比較を行う前に信号を取得することです。

 - (NSComparisonResult) を比較します。BarOne:(UIView *)barOne と BarTwo:(UIView *)barTwo {  
 //比較に必要な時間をシミュレートする 
ディスパッチセマフォを待機します(self.sema、DISPATCH_TIME_FOREVER);  
 CGFloat 高さ1 = CGRectGetHeight(barOne.frame);  
 CGFloat 高さ2 = CGRectGetHeight(barTwo.frame);  
高さ1 == 高さ2の場合{  
 NSOrderedSameを返します。  
 }  
 height1 < height2を返します。NSOrderedAscending:NSOrderedDescending;  
 }

2. メインスレッドはタイマーを有効にし、0.002 秒ごとに信号を送信してソートスレッドを起動します。

ディスパッチセマフォを作成します。  
 NSTimeInterval nowTime = [[NSDate date ] timeIntervalSince1970];  
 // タイマー信号 
 __weak typeof(self) 弱い自己 = 自己;  
 self.timer = [NSTimer スケジュールされたタイムスタンプ付き時間間隔:0.002 繰り返し:YES ブロック:^(NSTimer * _Nonnull タイマー) {  
 //セマフォを送信してソートスレッドを起動する 
セマフォシグナルをディスパッチします。  
 // 更新タイミング 
 NSTimeInterval 間隔 = [[NSDate date ] timeIntervalSince1970] - nowTime;  
 weaknessSelf.timeLabel.text = [NSString stringWithFormat:@ "消費時間 (秒):%2.3f" , interval];  
 }];