kth Order Statistic (Iterative)138 views

Nitin Nizhawan 
 function kThOrderStatistic(list,k){
    function partition(lst,p,r){
        var t;
        while(p<r){
            while(p<r&&lst[p]<=lst[r]){
                p++;
            }
            t=lst[p];lst[p]=lst[r];lst[r]=t;
            while(p<r&&lst[p]<=lst[r]){
                r--;
            }
            t=lst[p];lst[p]=lst[r];lst[r]=t;
        }
        return p;
    }
    k = k-1; // starting from zero
    var q,start = 0, end = list.length-1;
    while(q!=k){
        q = partition(list,start,end);
        start = (k>q)?q+1:start;
        end = (k<q)?q-1:end;
    }
    return list[q];
}

Problem Statement: Given a list of numbers and a number ‘k’, find kth smallest element in the list

Solution: kth order statistic problem is also known as selection algorithm. we can use quickselect algorithm for it. This algorithm is also known as Hoare’s selection algorithm. The critical step in this algorithm is to partition the list using a pivot element such that all elements to the left of pivot are smaller than or equal to pivot and all elements to the right are larger or equal to it. Once the list has been partitioned using such a pivot. The position of pivot ‘i’ is the i-th order in the list.  The logic for partitioning is same as that used in quick sort. This algorithm is also divide and conquer algorithm. We pick a random element and partition the array using it. If the final position of pivot is equal to the k then pivot is the k-th smallest element, if k is less than the position of pivot then we discard the right sub array and again partition the left sub-array. On the other hand if k is larger that position of pivot then we discard left sub-array and partition the right subarray. we repeat this procedure until we find a pivot such that position of pivot is equal to k. This algorithm as expected (average) running time of O(n) and worst case running time of O(n²).

Post a Comment

You must be logged in to post a comment.