クイックソート

定義＃テイギ＃

個の問題を分割し、分割後の問題を統合(分割征服)する

.

クイックソート:ジョブを先に行い、小さな問題を再帰的に解決し、すぐに終了します.
:リストを不均一に分割します.
[連結ソート:小問題を再帰的に解決し、その後の処理を行います.
:リストを半分に分割します.]

プロセス

ピボット

を選択

軸心を基準として、両側に軸心より大きい値、小さい値を探します.左は軸心より大きい甲、右は軸心より小さい値を探します

双方向交換で見つかった2つの要素

2番を返し、

を繰り返し、左側のナビゲーションの位置と右側のナビゲーションの位置が交差しないまで繰り返します.

のずれた始点を基準として、2つの部分リストに分けて、その部分リストの長さが1でないまで、第1のプロセス

を繰り返す第1の部分リストに戻る.

隣接部分リストマージ

コード#コード#

左ピボット選択

private static void left_pivotSort(int[] a, int low, int high) {
	if( low >= high) 
    	return;
    int pivot = partition(a, low, high);
    left_pivotSort(a, low, pivot - 1);
    left_pivotSort(a, pivot + 1, high);
}
private static int partition(int[] a, int left, int right) {
	int low = left;
    int high = right;
    int pivot = a[left]; //부분리스트의 왼쪽 요소를 피벗으로 설정
    
    while(low < high) {
    
    	while(a[high] > pivot && low < high) {
        	high--; //high의 요소가 pivot보다 작거나 같은 원소를 찾을때까지 high 감소시킴
        }
        
        while(a[low] <= pivot && low < high) {
        	low++; //low의 요소가 pivot보다 큰 원소를 찾을때 까지 low를 증가시킴
        }
        
        swap(a, low, high);
    }
    swap(a, left, low);//pivot으로 설정했던 위치의 원소와 low가 가르키는 원소를 바꾼다.
    return low;

}
private static void swap(int[] a, int i, int j) {
	int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
    

右軸の選択

private static void right_pivotSort(int[] a, int low, int high) {
	if( low >= high) 
    	return;
    int pivot = partition(a, low, high);
    right_pivotSort(a, low, pivot - 1);
    right_pivotSort(a, pivot + 1, high);
}
private static int partition(int[] a, int left, int right) {
	int low = left;
    int high = right;
    int pivot = a[right]; //부분리스트의 오른쪽 요소를 피벗으로 설정
    
    while(low < high) {
    
    	while(a[low] < pivot && low < high) {
        	low++; //high가 low보다크면서 low의 요소가 pivot보다 큰 원소를 찾을 때까지 low를 증가시킨다
        }
        
        while(a[high] >= pivot && low < high) {
        	high--; //high가 low보다 크면서, high의 요소가 pivot보다 작거나 같은 원소를 찾을 때까지 high를 감소시킨다
        }
        
        swap(a, low, high);
    }
    swap(a, right, high);//마지막으로 맨처음 pivot으로 설정했던 위치(a[right]) 의 원소와 high가 가리키는 원소를 바꾼다.
    
    return high;
}
private static void swap(int[] a, int i, int j) {
	int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
    

長所と短所

**メリット**

平均時間複雑度はNlogNであり,他のNlogNアルゴリズムに比べて非常に速い.
merge sortより2~3倍早い

は、追加のメモリを必要とせず、再帰呼び出しスタックフレームの空間的複雑さはlognであるため、メモリ消費量は少ない.

短所

特定の条件下で性能が急激に低下

.

再帰が使用するため、再帰が使用できない環境では、実装が複雑になる

.

時間の複雑さ

-平均比較演算:O(2^i)× N/2^i) = O ( N )
-平均時間複雑度:ツリーに対してlogN-1回比較を行う
: O(N) X O(logN) = O(NlogN)
-最も理想的な分割時間:マージソートと同じシェイプ
T(N) = 2T(N/2) + O(N)
-平均実行時間
T(N) = T(i - 1) + T(N - i) + O(N)
-最悪の時間複雑度:ソートされた配列をソートする場合
:分割を片側に傾ける
:再帰レベル毎にN個の比較タスク=O(N^2)をN回呼び出す
T(N) = T(N-1) + O(N)
Q.Quicksortの実行時間が最悪の場合について説明し、それを回避する方法を説明します.
−常に片側を0個に分割し、他方をn−1個に分割する.
T(n) = T(0) + T(n-1) + O(n)
= T(n-1) + O(n)
= T(n-2) + T(n-1) + O(n-1) + O(n)
O(1) + O(2) + ... + O(n-1) + O(n)
=O(n^2)
-ソートされた入力データ(最後の要素をピボットとして選択した場合)
回避方法:dual-pointの使用
しきい値を設定して一定のサイズ以下に下げると、並べ替えられた配列でパフォーマンスの良い挿入並べ替え(挿入並べ替え)を実行するように変更して、ほぼ整列した場合のパフォーマンスの低下を防ぐことができます.