[C/C++][做] Selection algorithm＠Morris' Blog

2013-10-04 18:31:09| 人70,127| 回2 | 上一篇 | 下一篇

[C/C++][做] Selection algorithm

推 0 收藏 0 0 站台

Selection Algorithm

算法描述：

：定序列中的找到第 k 小字。
一般使用 sorting algorithm 在 O(n logn) 排序後找到 k-th 小字。
又或者使用一 heap ，在效率 O(n logk) 找到，但一算法可以在 O(n) 完成。

算法步：

步&明考：
http://www.cnblogs.com/hibernate6/archive/2011/04/28/2522298.html

稍微描述一下核心，通常使用 RANDOM-SELECT 也可以到平均度 O(n)，但要找到最情下可以在 O(n) 的算法，RANDOM-SELECT 似於 quick sort 的一部分，只要能保 pivot 可能是中位的，效率就能在最到 O(n)。

於是一的操作：
首先，定函：
(1) selectionAlgorithm() 回指定序列中的第 k 小的索引值
(2) medianOfMedians() 回序列的 "近似中位" 的索引值

由於 selectionAlgorithm() 法 RANDOM-SELECT 的做法一，著重於找到近似中位。

medianOfMedians()：
1. 列 5 字分一堆，最後一堆少於 5 ，每找到中位。
2. 於 5 字使用 "插入排序" 得到中位，假操作 O(1)。
3. 得到所有中位後，用 selectionAlgorithm 切找到中位的中位。

selectionAlgoithm()：
1. 增加修改的地方 pivot 用 medianOfMedians() 得到。

由於 "近似中位" 的效用，保分的位置可以在 [3/10 * n, 7/10 * n] 之。

而言之，如果 medianOfMedians() 放回 selectionAlgorithm()：

得到 T(n) = T(n/5) + T(7n/10+6) + O(n)
其中 T(n/5) 是 medianOfMedians() 用 selectionAlgorithm()
T(7n/10) 是在最的情下，在 7n/10 字下。

明：O(n)，使用法明。
假 T(n) <= cn, c > 0 是常
定 T(n) = O(1), when n < 140
T(n) <= T(n/5) + T(7n/10+6) + O(n)
=> T(n) <= c(n/5+1) + c(7n/10+6) + an
=> T(n) <= 9cn/10 + 7c + an
=> T(n) <= cn + (-cn/10 + 7c + an)

解 (-cn/10 + 7c + an) <= 0，
=> c >= 10a(n / (n-70) )
=> for n >= 140, n/(n-70) >= 2, c >= 20a 即可。
因此得到最情 O(n)。

例入：

10 0
14 11 25 17 17 14 14 3 19 12
10 8
4 1 4 9 22 25 10 19 6 23
10 9
16 6 9 20 15 21 5 21 6 26

例出：

3
23
26

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <time.h>
#define debug 0
using namespace std;
int selectionAlgorithm(int[], int, int, int);
int medianOfMedians(int[], int, int);
int selectionAlgorithm(int a[], int l, int r, int k) {
/**
* k = 0, 1, 2, ...
* return k-th smallest value.
*/
   if(r-l+1 <= 5) {// insert sort.
       int i, j, v;
       for(i = l+1; i <= r; i++) {
           v = a[i], j = i;
           while(j-1 >= l && a[j-1] > v)
               a[j] = a[j-1], j--;
           a[j] = v;
       }
       return l+k;
   }
   //printf("%d %d\n", l, r);
   int pivot = medianOfMedians(a, l, r);
   // partition begin.
   swap(a[l], a[pivot]);
   int i, j, t = a[l];
   for(i = l, j = l+1; j <= r; j++) {
       if(a[j] <= t)
           i++, swap(a[i], a[j]);
   }
   swap(a[l], a[i]);
   // partition end.
   int position = i;
#if debug == 1
   printf("pivot = %d ", t);
   printf("[");
   for(i = l; i <= position; i++)
       printf("%d ", a[i]);
   printf("]");
   printf("[");
   for(i = position+1; i <= r; i++)
       printf("%d ", a[i]);
   printf("]\n");
#endif
   if(position-l == k)   return position;
   if(position-l < k)
       return selectionAlgorithm(a, position+1, r, k-(position-l+1));
   else
       return selectionAlgorithm(a, l, position, k);
}
int medianOfMedians(int a[], int l, int r) {
   int numMedians = (r-l+4)/5;
   int i, subl, subr;
   int medianIdx;
   for(i = 0; i < numMedians; i++) {
       subl = l + i*5;
       subr = sul + 4;
       if(subr > r)   subr = r;
       medianIdx = selectionAlgorithm(a, subl, subr, (subr-subl)/2);
       swap(a[l+i], a[medianIdx]);
   }
   //printf("median %d %d\n", l, r);
   return selectionAlgorithm(a, l, l+numMedians, numMedians/2);
}
int a[1000005];
int main() {
    clock_t st, ed;
    st = clock();
   //srand(time(NULL));
   freopen("in.txt","r+t",stdin);
    freopen("out.txt","w+t",stdout);
   int n, m;
   int i;
   while(scanf("%d %d", &n, &m) == 2) {
       for(i = 0; i < n; i++)
           scanf("%d", &a[i]);
       int idx = selectionAlgorithm(a, 0, n-1, m);
       printf("%d\n", a[idx]);
   }
    ed = clock();
    printf("%f\n", (float)(ed - st )/CLOCKS_PER_SEC);
   return 0;
}

我要

#selection algorithm#做

台： Morris

您可能以下文章有趣

[*] Suffix Array [SA算法]

CountSort + SA

-Size Balanced Tree(SBT)(1)

人(70,127) | 回(2)| 推 (0)| 收藏 (0)| 寄
全站分: 教育(修、留、研究、教育概) | 人分: 演算法 |
此分上一篇:CountSort + SA

回(2)

推(0)

我要回

路人

你好，不好意思我想一下
在medianOfMedians function中
int numMedians = (r-l)/5;
什不是ceil((double)(r-l)/5)) ??

那假如我size10大小的列去
那median的不是要有5??
可是如果入(r-l)/5
算出只有1median

我此有疑
能麻回gmail信我 ??

2014-04-12 13:50:33

版主回

你的有，是我了，修正 int numMedians = (r-l+4)/5;

2014-04-12 14:47:51

路上

我的信箱 he01350446@gmail.com

2014-04-12 13:51:14

* 回人：

E-mail：

悄悄：

否是 (若未登入"人新台"看不到回覆唷!)

回容：

* 入：

入片中算式的果(可能0)

(有*必填)