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

×

randomized select

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

whiteknight321's gravatar image

0★whiteknight321
26689
accept rate: 0%


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

link

answered 06 Jul '13, 21:25

sex_man19's gravatar image

0★sex_man19
014
accept rate: 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 ;-).

link

answered 07 Jul '13, 08:57

tijoforyou's gravatar image

2★tijoforyou
4.2k52364
accept rate: 15%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,819
×1,620
×905
×242

question asked: 06 Jul '13, 06:47

question was seen: 17,397 times

last updated: 07 Jul '13, 08:57