アルゴリズム導論学習ノート(7)-高速ソート
1340 ワード
1クイックソートの概要
高速ソートは分治思想を用いたソートアルゴリズムであり、以下の利点がある:1.アルゴリズムの所望運転時間はθ(nlgn)であり、その中に含まれる定数因子が小さいため、高速ソートアルゴリズムは通常、実際の応用において最良の選択である. 2. アドレスソートでは、ソート中に限られた補助空間しか必要ありません.
2アルゴリズムの説明
高速ソートは,分治のアルゴリズム設計思想により,キーサブプロセスpartitionを用いて入力(ここではアルゴリズムの入力が互いに異なるキーワードkeyからなる整数配列と仮定する)をメタよりも小さいと大きい2つの部分に分割し,メタはランダムに選択したり,特定のindex位置のkeyを選択したりすることができる.その中で,分治の考え方は以下の通りである:(1)分解:partitionサブプロセスを用いて入力配列を主元よりも小さいと大きい2つの部分に分解する.(2)解決:この2つの部分の再帰的な呼び出しを迅速にソートして秩序化する.(3)マージ:アドレスソートであるため、マージ手順は省略することができる.
アルゴリズムの疑似コードは次のとおりです.
3クイックソートのパフォーマンス
クイックソートの所望の実行時間はθ(nlgn)、最悪運転時間はθ(n 2)実際の使用中に迅速に並べ替えられた平均運転時間は、最悪運転時間ではなく最良の場合に近い.高速ソートの実行時間は,PARTITION関数による配列の分割が平衡しているかどうかに依存し,最も平衡している分割では,原問題は[n/2]規模のサブ問題に分解され,その実行時間は[n/2]である.θ(nlgn).一方,最もアンバランスな区分では,原問題は0とn−1の2つのサブ問題に分解され,アルゴリズムは最悪の場合の実行時間を取得する.θ(n 2)また,入力が完全に秩序化されている場合,アルゴリズムも最悪の場合の実行時間を取得する.
高速ソートは分治思想を用いたソートアルゴリズムであり、以下の利点がある:1.アルゴリズムの所望運転時間はθ(nlgn)であり、その中に含まれる定数因子が小さいため、高速ソートアルゴリズムは通常、実際の応用において最良の選択である. 2. アドレスソートでは、ソート中に限られた補助空間しか必要ありません.
2アルゴリズムの説明
高速ソートは,分治のアルゴリズム設計思想により,キーサブプロセスpartitionを用いて入力(ここではアルゴリズムの入力が互いに異なるキーワードkeyからなる整数配列と仮定する)をメタよりも小さいと大きい2つの部分に分割し,メタはランダムに選択したり,特定のindex位置のkeyを選択したりすることができる.その中で,分治の考え方は以下の通りである:(1)分解:partitionサブプロセスを用いて入力配列を主元よりも小さいと大きい2つの部分に分解する.(2)解決:この2つの部分の再帰的な呼び出しを迅速にソートして秩序化する.(3)マージ:アドレスソートであるため、マージ手順は省略することができる.
アルゴリズムの疑似コードは次のとおりです.
QUICKSORT（A, p ,r）
//
if(p < r)
// ， PARTITION
q=PARTITION(A,p,r)
//
QUICKSORT(A,p,q-1)
//
QUICKSORT(A,q+1,r)
PARTITION（A,p,r）
//
pivot = A[p]
// pivot ，
j = p;
// p + 1 r pivot
for( i = p + 1 to r)
// ， +1 A[i]
if(A[i] < pivot)
j++
swap(A[j],A[i])
//
swap(A[j+1],A[p])
3クイックソートのパフォーマンス
クイックソートの所望の実行時間はθ(nlgn)、最悪運転時間はθ(n 2)実際の使用中に迅速に並べ替えられた平均運転時間は、最悪運転時間ではなく最良の場合に近い.高速ソートの実行時間は,PARTITION関数による配列の分割が平衡しているかどうかに依存し,最も平衡している分割では,原問題は[n/2]規模のサブ問題に分解され,その実行時間は[n/2]である.θ(nlgn).一方,最もアンバランスな区分では,原問題は0とn−1の2つのサブ問題に分解され,アルゴリズムは最悪の場合の実行時間を取得する.θ(n 2)また,入力が完全に秩序化されている場合,アルゴリズムも最悪の場合の実行時間を取得する.