实施quickselect [英] Implementing quickselect
问题描述
我想实现quickselect算法。虽然，我已经明白它背后的理论非常好;我发现很难将其转换成一个运作良好的方案。
下面是如何我要一步一步来实现它，我在哪里面临的问题：
问题：找到一个第四最小的元素[] = {2,1,3,7,5,4,6}
K = 4 。
指数： 0 | 1 | 2 | 3 | 4 | 5 | 6
相应的值： 2 | 1 | 3 | 7 | 5 | 4 | 6
开始， L = 0 和 R = 6
第1步）以支点为最左边的元素（支点总是会在这个问题最左边） -
pivot_index = 0
pivot_value = 2
步骤2）应用分区算法中;把支点在正确的地方（ [＆LT; P] [P] [指p] ） -
我们得到下面的数组： 1 | 2 | 3 | 7 | 5 | 4 | 6
其中， pivot_index = I-1 = 1
因此， pivot_value = 2
第3步）比较 pivot_index 与 K -
K = 3 ， pivot_index = 1 ; K > pivot_index
因此，我们的第k个最小的数在于所述阵列的右侧部分
右键阵列= 我于r ，我们不与左边打扰（ l至I-1 ）了。
第4步）我们修改 K 为的k值 - （pivot_index） => 4-1 = 2; K = 3 。
这里的问题是：不应该 K 的值是2？因为我们有两个值对数组的左侧部分： 1 | 2 ？我们应该计算 K 为 K - （pivot_index + 1）？
假设 K = 3 是正确的。
第五步）新建阵列工作在： 3 | 7 | 5 | 4 | 6 相应指标： 2 | 3 | 4 | 5 | 6
现在， pivot_index = 2 和 pivot_index = 3
第六步）上面的阵列上应用分区算法中 -
3 | 7 | 5 | 4 | 6 （阵列保持不变为支点本身的最低值）。
I = 3
pivot_index = I-1 = 2
pivot_value = 3
第7步）比较 pivot_index 与 K
K = 3 和 pivot_index = 2
K＆GT; pivot_index
等等....
是这种做法是否正确？
下面是我的code这是不可以工作。我已经使用一个随机数发生器来选择一个随机枢轴，枢轴然后交换与阵列中的第一个元素。
＃包括＆LT; stdio.h中＆GT;
＃包括＆LT; stdlib.h中＆GT;
无效print_array（INT改编[]，INT array_length）{
INT I;
对于（i = 0; I＆LT; array_length ++我）{
的printf（％D，编曲[I]）;
}
}
INT random_no（最小，最大）{
INT差异=最大值 - 最小值;
返程（INT）（（（双）（差异+ 1）/ RAND_MAX）* RAND（）+分）;
}
无效掉期（INT *一，为int * B）{
INT温度;
TEMP = * A;
* A = * B;
* B =温度;
}
INT get_kth_small（INT改编[]，INT K，INT L，INT读）{
如果（（R-L）＆GT; = 1）{
K = K +（L-1）;
INT pivot_index = random_no（L，R）;
INT I，J;
掉期（安培;常用3 [pivot_index]，和放大器;常用3 [L]）; //切换枢轴与阵列中的第一个元素。现在，pivit是在改编[升]
其中i = 1 + 1;
为（J = L + 1; J＆LT; = R; ++ j）条{
如果（ARR [J]其中，常用3 [L]）{
掉期（安培;常用3 [J]，和放大器;常用3 [I]）;
++我;
}
}
交换（安培;常用3 [升]，＆安培;常用3 [I-1]）; //切换支点的正确位置; ＆所述;对，对，指p
的printf（值I-1：％D \ N，I-1）;
的printf（K值数：％d \ N，K）;
如果（K ==第（i-1））{
的printf（找到数：％d \ N，编曲[I]）;
返回0;
}
如果（K＆GT;第（i-1））{
K = K-第（i-1）;
get_kth_small（ARR，K，I，R）;
} 其他 {
get_kth_small（ARR，K，L，R-1）;
}
// get_kth_small（ARR，K，I，R）;
// get_kth_small（ARR，K，L，I-1）;
}
}
无效的主要（）{
函数srand（时间（NULL））;
INT ARR [] = {2,1,3,7,5,4,6};
INT arr_size = sizeof的（ARR）/ sizeof的（ARR [0]）;
时int k = 3，L = 0;
INT R = arr_size - 1;
//输出（输入k的值：）;
// scanf函数（％D，与功放; K）;
get_kth_small（ARR，K，L，R）;
print_array（ARR，arr_size）;
的printf（\ N）;
}
第2步：把支点在正确的地方：不这样做。事实上，你不能把支点在正确的地方，因为你不知道它是什么。该分区规则是把所有的元素比支点小于或等于以前的那些更大。刚刚离开的支点在哪里啊！
快速选择去如下：找到 K 日之间的 N 元素，1）选择一个支点值，2）将所有的元素小于或等于给了别人之前支点，形成长度为两个区域非编和 NGT 3）递归与相关区（ K ，非编）或（ K-非编， NGT ），直到 N = 1 。
实际上，任何数值可采取的枢轴时，即使不present阵列中;但分区必须是这样的：非编和 NGT 是非零。
I'm trying to implement the quickselect algorithm. Though, I have understood the theory behind it very well; I'm finding it difficult to convert it into a well functioning program.
Here is how I'm going step by step to implement it and where I am facing problem:
Problem: Find the 4th smallest element in A[] = {2,1,3,7,5,4,6}
k = 4.
index:0|1|2|3|4|5|6
Corresponding values: 2|1|3|7|5|4|6
initially, l = 0 and r = 6
Step 1) Taking pivot as the leftmost element (pivot will always be the leftmost in this problem)-
pivot_index = 0
pivot_value = 2
Step 2) Applying the partition algo; putting the pivot at the right place ([<p][p][>p])-
We get the following array: 1|2|3|7|5|4|6
where, pivot_index = i-1 = 1
and therefore, pivot_value = 2
Step 3) Compare pivot_index with k-
k=3, pivot_index = 1; k>pivot_index
Hence, Our k-th smallest number lies in the right part of the array.
Right array = i to r and we do not bother with the left part (l to i-1) anymore.
Step 4) We modify the value of k as k - (pivot_index) => 4-1 = 2; k = 3.
Here is the problem: Should not the value of k be 2? Because we have two values on the left part of the array: 1|2? Should we calculate k as k - (pivot_index+1)?
Let's assume k = 3 is correct.
Step 5) "New" array to work on: 3|7|5|4|6 with corresponding indexes: 2|3|4|5|6
Now, pivot_index = 2 and pivot_index = 3
Step 6) Applying partition algo on the above array-
3|7|5|4|6 (array remains unchanged as pivot itself is the lowest value).
i = 3
pivot_index = i-1 = 2
pivot_value = 3
Step 7) Compare pivot_index with k
k=3 and pivot_index=2
k > pivot_index
and so on....
Is this approach correct?
Here is my code which is not working. I have used a random number generator to select a random pivot, the pivot is then swapped with the first element in the array.
#include<stdio.h>
#include<stdlib.h>
void print_array(int arr[], int array_length){
int i;
for(i=0; i<array_length; ++i) {
printf("%d ", arr[i]);
}
}
int random_no(min, max){
int diff = max-min;
return (int) (((double)(diff+1)/RAND_MAX) * rand() + min);
}
void swap(int *a, int *b){
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int get_kth_small(int arr[], int k, int l, int r){
if((r-l) >= 1){
k = k + (l-1);
int pivot_index = random_no(l, r);
int i, j;
swap(&arr[pivot_index], &arr[l]); //Switch the pivot with the first element in the array. Now, the pivit is in arr[l]
i=l+1;
for(j=l+1; j<=r; ++j){
if(arr[j]<arr[l]){
swap(&arr[j], &arr[i]);
++i;
}
}
swap(&arr[l], &arr[i-1]); //Switch the pivot to the correct place; <p, p, >p
printf("value of i-1: %d\n", i-1);
printf("Value of k: %d\n", k);
if(k == (i-1)){
printf("Found: %d\n", arr[i]);
return 0;
}
if(k>(i-1)){
k=k-(i-1);
get_kth_small(arr, k, i, r);
} else {
get_kth_small(arr, k, l, r-1);
}
//get_kth_small(arr, k, i, r);
//get_kth_small(arr, k, l, i-1);
}
}
void main(){
srand(time(NULL));
int arr[] = {2,1,3,7,5,4,6};
int arr_size = sizeof(arr)/sizeof(arr[0]);
int k = 3, l = 0;
int r = arr_size - 1;
//printf("Enter the value of k: ");
//scanf("%d", &k);
get_kth_small(arr, k, l, r);
print_array(arr, arr_size);
printf("\n");
}
"Step 2: putting the pivot at the right place": don't do that. In fact you can't put the pivot at the right place, as you don't know what it is. The partitioning rule is to put all elements smaller or equal than the pivot before those larger. Just leave the pivot where it is!
Quick select goes as follows: to find the Kth among N elements, 1) choose a pivot value, 2) move all elements smaller or equal to the pivot before the others, forming two zones of length Nle and Ngt, 3) recurse on the relevant zone with (K, Nle) or (K-Nle, Ngt), until N=1.
Actually, any value can be taken for the pivot, even one not present in the array; but the partition must be such that Nle and Ngt are nonzero.
这篇关于实施quickselect的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
