forked from xtaci/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathrandom_select.h
More file actions
71 lines (60 loc) · 1.93 KB
/
random_select.h
File metadata and controls
71 lines (60 loc) · 1.93 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/*******************************************************************************
* DANIEL'S ALGORITHM IMPLEMENTAIONS
*
* /\ | _ _ ._ o _|_ |_ ._ _ _
* /--\ | (_| (_) | | |_ | | | | | _>
* _|
*
* Quickselect
* In computer science, a quickselect is a selection algorithm related to the
* quicksort sorting algorithm. Like quicksort, it was developed by Tony Hoare,
* and thus is also known as Hoare's selection algorithm. Like quicksort, it is
* efficient in practice and has good average-case performance, but has poor
* worst-case performance. Quickselect and variants is the selection algorithm
* most often used in efficient real-world implementations.
*
* http://en.wikipedia.org/wiki/Quickselect
*
******************************************************************************/
#ifndef __RANDOM_SELECT_H__
#define __RANDOM_SELECT_H__
#include <generic.h>
namespace alg {
/**
* the random_select partition routine
*/
template<typename T>
static int __partition(T list[],int begin, int end) {
int pivot_idx = RANDOM(begin,end);
T pivot = list[pivot_idx];
swap(list[begin],list[pivot_idx]);
int i = begin + 1;
int j = end;
while(i <= j) {
while((i <= end) && (list[i] <= pivot))
i++;
while((j >= begin) && (list[j] > pivot))
j--;
if(i < j)
swap(list[i],list[j]);
}
swap(list[begin],list[j]);
return j; // final pivot position
}
/**
* select the k-th smallest number in 'list' of range [begin, end]
*/
template<typename T>
static int random_select(T list[], int begin, int end, int k) {
if(begin == end)
return begin;
int pivot_idx = __partition<T>(list, begin, end);
int human_idx = pivot_idx - begin + 1;
if(k < human_idx)
return random_select(list, begin, pivot_idx - 1, k);
else if(k > human_idx)
return random_select(list, pivot_idx+1, end, k - human_idx);
return pivot_idx;
}
}
#endif //