You are not logged in. Please login at www.codechef.com to post your questions!

×

# randomized select

 1 can anyone give me the iterative version of randomized select for finding the ith smallest number This question is marked "community wiki". asked 06 Jul '13, 06:47 26●6●8●9 accept rate: 0%

 0 didnt quite understand u question..... finding ith smallest number ??? in what complexity???? answered 06 Jul '13, 21:25 0●1●4 accept rate: 0%
 0 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 ;-). answered 07 Jul '13, 08:57 4.2k●5●23●64 accept rate: 15%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,919
×1,664
×966
×255

question asked: 06 Jul '13, 06:47

question was seen: 17,698 times

last updated: 07 Jul '13, 08:57