「データ構造とアルゴリズム分析(c説明」-高速ソート
1.クイックソート
高速ソートは最も速い既知のソートアルゴリズムであり,平均運転時間はO(Nlogn),最悪の場合の性能はO(N^2)である.
配列Sのクイックソートは、以下の簡単な4つのステップから構成されます. S中の元素個素が0または1である場合、 を返す.は、Sのいずれかの要素をピボット要素 として取る.は、S-{v}(Sの残りの要素)を2つの交差しない集合に分割する.S 1の要素はvより小さく、S 2の要素はv より大きい.は、S 1、S 2に対して を再帰的に呼び出す.
cコードは以下のように実現される.
2.クイック選択
高速ソートの典型的な変形アプリケーションは、選択問題(select problem)、すなわち配列からk番目の要素を選択するために使用される.
高速アルゴリズムの選択手順は次のとおりです. S中の元素個素が0または1である場合、 を返す.は、Sのいずれかの要素をピボット要素 として取る.は、S-{v}(Sの残りの要素)を2つの交差しない集合に分割する.S 1の要素はvより小さく、S 2の要素はv より大きい.|S 1|の値をcurとする、 を再帰的に呼び出す.そうでなければ再帰呼び出し cコード実装:void qSelect(int a[],int k,int low,int high){if(low>=high)return;int first=low;int first=low;int last=high;int last=high;int key=a[low];while(first=key)last–;a[first]=a[last];while(first first) qSelect(a, k - first, first + 1, high); }
int main() { int a[10] = {9, 2, 8, 3, 4, 1, 5, 18, 11, 14}; qSelect(a, N, 0, 9); printf(“qselect : %d”, a[N - 1]); for (int i = 0; i < 10 ; i++) printf(“%d#”, a[i]); printf(“”); return 0; }
高速ソートは最も速い既知のソートアルゴリズムであり,平均運転時間はO(Nlogn),最悪の場合の性能はO(N^2)である.
配列Sのクイックソートは、以下の簡単な4つのステップから構成されます.
cコードは以下のように実現される.
void Qsort(int a[], int low, int high)
{
if(low >= high)
{
return;
}
int first = low;
int last = high;
int key = a[first];/* */
while(first < last)
{
while(first < last && a[last] >= key)
{
--last;
}
a[first] = a[last];/* */
while(first < last && a[first] <= key)
{
++first;
}
a[last] = a[first];
/* */
}
a[first] = key;/* */
Qsort(a, low, first-1);
Qsort(a, first+1, high);
}2.クイック選択
高速ソートの典型的な変形アプリケーションは、選択問題(select problem)、すなわち配列からk番目の要素を選択するために使用される.
高速アルゴリズムの選択手順は次のとおりです.
k <= curであれば、qSelect(a, cur - k, low, k - 1) qSelect(a, k - cur, k + 1, high) int main() { int a[10] = {9, 2, 8, 3, 4, 1, 5, 18, 11, 14}; qSelect(a, N, 0, 9); printf(“qselect : %d”, a[N - 1]); for (int i = 0; i < 10 ; i++) printf(“%d#”, a[i]); printf(“”); return 0; }