randomized select

general
, , ,
1

can anyone give me the iterative version of randomized select for finding the ith smallest number

1 Like
2

didnt quite understand u question… finding ith smallest number ??? in what complexity???

3

Is this what you are looking for?

void swap(int &x, int &y)
{
	int tmp = x;
	x = y;
	y = tmp;
}

int random_partition(int* arr, int start, int end)
{
	srand(time(NULL));
	int pivotIdx = start + rand() % (end-start+1);
	int pivot = arr[pivotIdx];
	swap(arr[pivotIdx], arr[end]); // move pivot element to the end
	pivotIdx = end;
	int i = start -1;
 
	for (int j = start; j <= end - 1; ++j)
		if (arr[j] <= pivot)
		{
			++i;
			swap(arr[i], arr[j]);
		}

	swap(arr[i+1], arr[pivotIdx]);
	return i+1;
}

int randomized_select(int* arr, int start, int end, int k)
{
	int mid, i;

	while (start <= end)
	{
		if (start == end)
			return arr[start];
		if (k == 0)
			return -1;

		mid = random_partition(arr, start, end);
		i = mid - start + 1;

		if (i == k)
			return arr[mid];
		else if (k < i)
			end = mid - 1;
		else
		{
			start = mid + 1;
			k -= i;
		}
	}
}

Disclaimer: I didn’t code this on my own. Just changed the recursive code from here into iterative code.

And, of course, the program returns kth smallest number. Not ith ;-).