クイックソート（Quick Sort）はバブルソートの改良版です。

クイックソートはC. A. R. ホーアによって1962年に提案されました。基本的な考え方は以下の通りです：一度の処理でソート対象のデータを二つの独立した部分に分割し、一方のすべての要素がもう一方のすべての要素より小さくなるようにします。その後、この方法をそれぞれの部分に対して再帰的に適用することで、全体を整列させます。

クイックソートのアルゴリズム手法

ソート対象の配列をmutableArrayオブジェクトとします。まず適当なデータ（通常は配列の最初の要素）を基準値として選択し、それより小さい値を前方に、大きい値を後方に配置します。この処理を一回のクイックソートと呼びます。

処理手順

1）変数indexA、indexBを設定し、初期状態ではindexA = 0、indexB = mutableArray.count - 1
2）配列の最初の値を比較基準とするpivotValue、pivotValue = [mutableArray[0] integerValue]
3）pivotValueを配列の最初の値としたため、右端から左に向かってpivotValueより小さな値を探します。見つからない場合はindexBをデクリメントして探索を継続、見つかったらmutableArray[indexA]にその値を設定し、探索を停止してステップ4へ進みます
4）indexAの位置から右方向に基準値より大きな値を探します。見つからない場合はindexAをインクリメントして探索を継続、見つかったらmutableArray[indexB]にその値を設定し、探索を停止します
5）indexA == indexBになるまでステップ3と4を繰り返し、一致した時点でソートを終了
6）mutableArray[indexA]に基準値を設定

ソートの例示

mutableArray = {@(4),@(3),@(7),@(1),@(5),@(8)}と仮定します

ステップ1：indexA = 0; indexB = 5; pivotValue = 4;

ステップ2：pivotValueより小さな値を右から左へ探します。indexBを減少させながら最初に見つかった値をmutableArray[indexA]に設定

indexA = 0; indexB = 3; pivotValue = 4;

ステップ3：pivotValueより大きな値を左から右へ探します。indexAを増加させながら最初に見つかった値をmutableArray[indexB]に設定

indexA = 2; indexB = 3; pivotValue = 4;

次にindexBをデクリメントすると、indexA == indexBになります

これで一回のループが完了します。その後、基準値の左右それぞれを新しい配列として上記手順を繰り返します。

Objective-Cコード実装

- (void)loadView {
    [super loadView];
    
    NSMutableArray *dataList = [[NSMutableArray alloc] initWithObjects:@(6), @(1),@(2),@(5),@(9),@(4),@(3),@(7),nil];
    
    [self executeQuickSort:dataList withStartIndex:0 andEndIndex:dataList.count - 1];
    
    NSLog(@"%@",dataList);
}

- (void)executeQuickSort:(NSMutableArray *)targetArray withStartIndex:(NSInteger)startIndex andEndIndex:(NSInteger)endIndex
{
    if (startIndex >= endIndex) {
        return;
    }
    
    NSInteger leftPointer = startIndex;
    NSInteger rightPointer = endIndex;
    NSInteger baseValue = [targetArray[leftPointer] integerValue];
    
    while (leftPointer < rightPointer) {
        
        while (leftPointer < rightPointer && [targetArray[rightPointer] integerValue] >= baseValue) {
            rightPointer--;
        }
        targetArray[leftPointer] = targetArray[rightPointer];
        
        while (leftPointer < rightPointer && [targetArray[leftPointer] integerValue] <= baseValue) {
            leftPointer++;
        }
        targetArray[rightPointer] = targetArray[leftPointer];
    }
    
    targetArray[leftPointer] = @(baseValue);
    
    [self executeQuickSort:targetArray withStartIndex:startIndex andEndIndex:leftPointer - 1];
    [self executeQuickSort:targetArray withStartIndex:leftPointer + 1 andEndIndex:endIndex];
}

時間計算量：
クイックソートにおいて理想的なのは、各パーティション操作で要素がサブシーケンスの中央に位置することです。この場合の最良効率はN*logNです。最悪の場合、極端な位置に挿入されるケースでO(N²)となります。