current position:Home>Divide and conquer strategy -- find the k-th smallest element in the array

Divide and conquer strategy -- find the k-th smallest element in the array

2022-04-29 04:47:06Goldinger

#include <stdio.h>

/* First, we give a partition function ( Quick sort Division )*/
int partition(int* ar, int left, int right)
{
    
	int i = left;
	int j = right;
	int tmp = ar[i];
	while (i < j)
	{
    
		while (i<j && ar[j] > tmp)
		{
    
			j--;
		}
		if (i < j) ar[i] = ar[j];
		while (i < j && ar[i] <= tmp)
		{
    
			i++;
		}
		if (i < j) ar[j] = ar[i];
	}
	ar[i] = tmp;
	return i;
}
// recursive 
int Selectk(int* ar, int left, int right, int k)
{
    
	if (left == right && k == 1)
	{
    
		return ar[left];
	}
	int index = partition(ar, left, right);//index Is the physical subscript 
	int pos = index - left + 1;//pos Is to combine the physical subscript with the k Element position correspondence 
	if (k <= pos) return Selectk(ar, left, index, k);
	else
	{
    
		return Selectk(ar, index + 1, right, k - pos);// When looking in the right part , Pay attention to the original article k The element will become k-pos
	}
}

int Select_k_Min(int* ar, int n, int k)
{
    
	if (ar == NULL || n < 1 || k<0 || k>n) return -1;
	return Selectk(ar, 0, n-1, k);
}


int main()
{
    
    int num,i,k;
    scanf("%d %d", &num,&k);
    int a[num];
    for(i=0;i<num;i++)
        scanf("%d",&a[i]);
    printf(" The first %d The small element is %d",k,Select_k_Min(a,num,k));
    return 0;
}
/********** End **********/

copyright notice
author[Goldinger],Please bring the original link to reprint, thank you.
https://en.qdmana.com/2022/117/202204270542483866.html

Random recommended