CODEWITHSUNDEEP
carraysalgorithmdata-structures
user3600483
user3600483

Reputation: 147

Kth Ranked Element Among 2 Unsorted Arrays

Let us suppose we have two arrays A[] and B[]. Each array contains n distinct integers which are not sorted. We need to find kth ranked element in the union of the 2 arrays in the most efficient way possible. (Please dont post answers about merging the arrays and then sorting them to return kth index in the merged array)

Upvotes: 2

Views: 399

Answers (2)

Sumit Trehan
Sumit Trehan

Reputation: 4035

Union of arrays can be done in linear time. I am skipping that part.

You can use the partition() algorithm which is used in the quick sort. In quick sort, the function will have to recurse two branches. However here we will just conditionally invoke the recursive call and thus only 1-branched recursion.

Main concept: partition() will place the chosen PIVOT element at its appropriate sorted position. Hence we can use this property to select that half of the array in which we are interested and just recurse on that half. This will prevent us from sorting the entire array.

I have written the below code based on the above concept. Assumption rank = 0 implies the smallest element in the array.

void swap (int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int partition (int a[], int start, int end)
{
    /* choose a fixed pivot for now */
    int pivot = a[end];
    int i = start, j;

    for (j = start; j <= end-1; j++) {
        if (a[j] < pivot) {
            swap (&a[i], &a[j]);
            i++;
        }
    } 
    /* Now swap the ith element with the pivot */
    swap (&a[i], &a[end]);
    return i;
}

int find_k_rank (int a[], int start, int end, int k)
{
    int x = partition (a, start, end);
    if (x == k) {
        return a[x];
    } else if (k < x) {
        return  find_k_rank (a, start, x-1, k);
    } else {
        return find_k_rank (a, x+1, end, k);
    }
}

int main()
{
    int a[] = {10,2,7,4,8,3,1,5,9,6};
    int N = 10;
    int rank = 3;
    printf ("%d\n", find_k_rank (a, 0, N-1, rank));
}

Upvotes: 2

gen-y-s
gen-y-s

Reputation: 881

You can use the selection algorithm to find the Kth item, in O(N) time, where N is the sum of the sizes of the arrays. Obviously, you treat the two arrays as a single large array.

Upvotes: 2

Related Questions