『アルゴリズム導論』CLRSアルゴリズムC++実装(九)P 109選択配列におけるi番目に小さい(大きい)数順統計量
11316 ワード
第九章中位数と順序統計学
9.2所望の直線時間で選択
前回は最小値を見つけながら、最大値の最小値を見つけ、二次小値を見つける問題でした.配列内のi番目に小さい(大きい)要素を任意に選択することは、最小値を探す簡単な選択問題よりも複雑に見えます.しかし驚くべきことに,両問題の漸近運転時間は同じであり,いずれもO(n)であった.アルゴリズム導論では,選択問題を解決するための分治アルゴリズム,すなわちRANDOMizeD‐SELECTアルゴリズムを紹介した.本アルゴリズムは,高速ソートアルゴリズムの分割アルゴリズムに基づいて,高速ソートにおいても入力配列を再帰的に区分するという考え方である.しかし,クイックソートとは異なり,クイックソートは分割の両側を再帰的に処理し,RANDOMizeD−SELECTは分割のどちらか一方のみを処理する.この相違はアルゴリズムの解析において現れる:高速ソートの所望運転時間はO(nlgn)である.一方、RANDOMizeD-SELECTの所望運転時間はO(n)である.RANDOMISZED-SELECTアルゴリズムを次に示します.
RANDOMIZED-SELECT(A, p, r, i) P109
RANDOMizeD-SELECTはRANDOMizeD-PARTITIONプログラムを利用している.したがって,本アルゴリズムもランダムアルゴリズムであり,その挙動はランダム数生成器の出力によって部分的に決定されるからである.このアルゴリズムは、A[p..r]のi番目に小さい要素を返します.
アルゴリズムの3行目のRANDOMizeD-PARTITION実行後、配列A[p..r]は、A[p..q-1]とA[q+1..r]の2つのサブ配列に分割され、A[p..q-1]の各要素がA[q]以下、A[q+1..r]の各要素がA[q]より大きい.
4行目は、A[p..r]の要素個数k、すなわち、低分割された要素の個数に1つの主要素を加算することを計算する.次に、5行目でA[q]がi番目に小さい要素であるかどうかをチェックします.もしそうなら、A[q]を返します.そうでなければ、アルゴリズムは、i番目の小さな要素が2つのサブ配列A[p..q-1]とA[q+1..r]のどちらにあるかを決定する.ikのような低領域では、高領域である.次に、再帰的に選択します.
アルゴリズムの最悪の実行時間はO(n 2)であり,最小要素を選択してもよい.
「プログラミングの美しさ」の2.3は、「水王」を探して順番統計量で解くことができる.
C++コード
9.2所望の直線時間で選択
前回は最小値を見つけながら、最大値の最小値を見つけ、二次小値を見つける問題でした.配列内のi番目に小さい(大きい)要素を任意に選択することは、最小値を探す簡単な選択問題よりも複雑に見えます.しかし驚くべきことに,両問題の漸近運転時間は同じであり,いずれもO(n)であった.アルゴリズム導論では,選択問題を解決するための分治アルゴリズム,すなわちRANDOMizeD‐SELECTアルゴリズムを紹介した.本アルゴリズムは,高速ソートアルゴリズムの分割アルゴリズムに基づいて,高速ソートにおいても入力配列を再帰的に区分するという考え方である.しかし,クイックソートとは異なり,クイックソートは分割の両側を再帰的に処理し,RANDOMizeD−SELECTは分割のどちらか一方のみを処理する.この相違はアルゴリズムの解析において現れる:高速ソートの所望運転時間はO(nlgn)である.一方、RANDOMizeD-SELECTの所望運転時間はO(n)である.RANDOMISZED-SELECTアルゴリズムを次に示します.
RANDOMIZED-SELECT(A, p, r, i) P109
1 if p = r
2 then return A[p]
3 q ← RANDOMIZED-PARTITION(A, p, r)
4 k ← q - p + 1
5 if i = k
6 then return A[q]
7 elseif i < k
8 then return RANDOMIZED-SELECT(A, p, q - 1, i)
9 else return RANDOMIZED-SELECT(A, q + 1, r, i - k)RANDOMizeD-SELECTはRANDOMizeD-PARTITIONプログラムを利用している.したがって,本アルゴリズムもランダムアルゴリズムであり,その挙動はランダム数生成器の出力によって部分的に決定されるからである.このアルゴリズムは、A[p..r]のi番目に小さい要素を返します.
アルゴリズムの3行目のRANDOMizeD-PARTITION実行後、配列A[p..r]は、A[p..q-1]とA[q+1..r]の2つのサブ配列に分割され、A[p..q-1]の各要素がA[q]以下、A[q+1..r]の各要素がA[q]より大きい.
4行目は、A[p..r]の要素個数k、すなわち、低分割された要素の個数に1つの主要素を加算することを計算する.次に、5行目でA[q]がi番目に小さい要素であるかどうかをチェックします.もしそうなら、A[q]を返します.そうでなければ、アルゴリズムは、i番目の小さな要素が2つのサブ配列A[p..q-1]とA[q+1..r]のどちらにあるかを決定する.i
アルゴリズムの最悪の実行時間はO(n 2)であり,最小要素を選択してもよい.
「プログラミングの美しさ」の2.3は、「水王」を探して順番統計量で解くことができる.
C++コード
1 #include <iostream>
2 #include <ctime>
3 #include <cstdlib>
4
5 using namespace std;
6
7 void swap(int* x, int* y)
8 {
9 int temp;
10 temp = *x;
11 *x = *y;
12 *y = temp;
13 }
14
15 inline int random(int x, int y)
16 {
17 srand((unsigned)time(0));
18 int ran_num = rand() % (y - x) + x;
19 return ran_num;
20 }
21
22 int partition(int* arr, int p, int r)
23 {
24 int x = arr[r];
25 int i = p - 1;
26 for(int j = p; j < r; j++)
27 {
28 if (arr[j] <= x)
29 {
30 i++;
31 swap(arr[i], arr[j]);
32 }
33 }
34 swap(arr[i + 1], arr[r]);
35 return ++i;
36 }
37
38 int randomizedpartition(int* arr, int p, int r)
39 {
40 int i = random(p, r);
41 swap(arr[r], arr[i]);
42 return partition(arr, p, r);
43 }
44
45 int randomizedSelect(int* arr, int p, int r, int i)
46 {
47 if(p == r)
48 {
49 return arr[p];
50 }
51 int q = randomizedpartition(arr, p, r);
52 int k = q - p + 1;
53 if(i == k)
54 {
55 return arr[q];
56 }
57 else if(i < k)
58 {
59 return randomizedSelect(arr, p, q - 1, i);
60 }
61 else
62 return randomizedSelect(arr, q + 1, r, i - k);
63 }
64
65 int main()
66 {
67 int arr[] = {1, 3, 5, 23, 64, 7, 23, 6, 34, 98, 100, 9};
68 int i = randomizedSelect(arr, 0, 11, 4);
69 cout << i << endl;
70 return 0;
71 }