{"id":25284,"date":"2017-10-15T16:38:36","date_gmt":"2017-10-15T11:08:36","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25284"},"modified":"2017-10-15T16:38:36","modified_gmt":"2017-10-15T11:08:36","slug":"c-programming-kth-smallestlargest-element-unsorted-array-set-2-expected-linear-time","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-kth-smallestlargest-element-unsorted-array-set-2-expected-linear-time\/","title":{"rendered":"C++ programming – K\u2019th Smallest\/Largest Element in Unsorted Array Set 2 Expected Linear Time"},"content":{"rendered":"

We recommend to read following post as a prerequisite of this post.<\/p>\n

K\u2019th Smallest\/Largest Element in Unsorted Array Set 1<\/span><\/p>\n

Given an array and a number k where k is smaller than size of array, we need to find the k\u2019th smallest element in the given array. It is given that ll array elements are distinct.<\/p>\n

Examples:<\/p>\n

Input: arr[] = {7, 10, 4, 3, 20, 15}\r\n       k = 3\r\nOutput: 7\r\n\r\nInput: arr[] = {7, 10, 4, 3, 20, 15}\r\n       k = 4\r\nOutput: 10<\/pre>\n
We have discussed three different solutions here<\/a>.<\/p>\n
\n
Recommended: Please solve it on “PRACTICE<\/u><\/b>” first, before moving on to the solution.<\/p>\n<\/div>\n
In this post method 4 is discussed which is mainly an extension of method 3 (QuickSelect) discussed in the previous <\/a>post. The idea is to randomly pick a pivot element. To implement randomized partition, we use a random function, rand()<\/a> to generate index between l and r, swap the element at randomly generated index with the last element, and finally call the standard partition process which uses last element as pivot.<\/p>\n[ad type=”banner”]\n
Following is implementation of above Randomized QuickSelect.<\/p>\n
C++ programming<\/strong><\/p>\n
 
 c++<\/span> <\/div> 
\/\/ C++ implementation of randomized quickSelect#include<iostream>#include<climits>#include<cstdlib>using namespace std; int randomPartition(int arr[], int l, int r); \/\/ This function returns k'th smallest element in arr[l..r] using\/\/ QuickSort based method. ASSUMPTION: ELEMENTS IN ARR[] ARE DISTINCTint kthSmallest(int arr[], int l, int r, int k){    \/\/ If k is smaller than number of elements in array    if (k > 0 && k <= r - l + 1)    {        \/\/ Partition the array around a random element and        \/\/ get position of pivot element in sorted array        int pos = randomPartition(arr, l, r);         \/\/ If position is same as k        if (pos-l == k-1)            return arr[pos];        if (pos-l > k-1)  \/\/ If position is more, recur for left subarray            return kthSmallest(arr, l, pos-1, k);         \/\/ Else recur for right subarray        return kthSmallest(arr, pos+1, r, k-pos+l-1);    }     \/\/ If k is more than number of elements in array    return INT_MAX;} void swap(int *a, int *b){    int temp = *a;    *a = *b;    *b = temp;} \/\/ Standard partition process of QuickSort().  It considers the last\/\/ element as pivot and moves all smaller element to left of it and\/\/ greater elements to right. This function is used by randomPartition()int partition(int arr[], int l, int r){    int x = arr[r], i = l;    for (int j = l; j <= r - 1; j++)    {        if (arr[j] <= x)        {            swap(&arr[i], &arr[j]);            i++;        }    }    swap(&arr[i], &arr[r]);    return i;} \/\/ Picks a random pivot element between l and r and partitions\/\/ arr[l..r] arount the randomly picked element using partition()int randomPartition(int arr[], int l, int r){    int n = r-l+1;    int pivot = rand() % n;    swap(&arr[l + pivot], &arr[r]);    return partition(arr, l, r);} \/\/ Driver program to test above methodsint main(){    int arr[] = {12, 3, 5, 7, 4, 19, 26};    int n = sizeof(arr)\/sizeof(arr[0]), k = 3;    cout << "K'th smallest element is " << kthSmallest(arr, 0, n-1, k);    return 0;}<\/code><\/pre> <\/div>\n
Output:<\/strong><\/p>\n
K'th smallest element is 5<\/pre>\n
Time Complexity: <\/strong>
\nThe worst case time complexity of the above solution is still O(n2<\/sup>). In worst case, the randomized function may always pick a corner element. The expected time complexity of above randomized QuickSelect is \u0398(n), see CLRS book<\/a> or MIT video lecture<\/a> for proof. The assumption in the analysis is, random number generator is equally likely to generate any number in the input range.<\/p>\n[ad type=”banner”]\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
C++ programming K\u2019th Smallest\/Largest Element in Unsorted Array | Set 2 (Expected Linear Time) – Searching and Sorting – Given an array and a number k where k is smaller than size of array, we need to find the k\u2019th smallest element in the given array. It is given that ll array elements are distinct.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,83515,71670],"tags":[72902,70235,72892,72869,72900,72899,72887,72903,72696,72877,72908,72819,72890,72891,72911,72907,72870,72876,72879,72918,72895,72874,72883,72894,72916,72915,72917,70891,72906,72898,72909,72886,72888,72896,72913,72872,72897,72905,72871,72880,72875,72901,72893,72904,72889,72910,72878,72884,72882,72873,72881,72914,72912,72885],"class_list":["post-25284","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming-3","category-searching-and-sorting","tag-99-problem","tag-algorithm-examples","tag-algorithm-to-find-largest-of-n-numbers","tag-c-programming-kth-smallestlargest-element-in-unsorted-array","tag-cluster-random-sampling","tag-element-n","tag-find-kth-smallest-element-in-array-java","tag-find-kth-smallest-element-in-two-sorted-arrays","tag-find-largest-number-in-array-java","tag-find-max-value-in-array-java","tag-find-median","tag-find-minimum-value-in-array-java","tag-find-smallest-number-in-array","tag-find-smallest-number-in-array-java","tag-find-the-mean","tag-find-the-median","tag-k-element","tag-k-sel","tag-kth-element","tag-kth-number","tag-kth-smallest-element-in-array","tag-largest-element","tag-largest-element-in-an-array","tag-least-element","tag-max-value-in-array-java","tag-median-of-two-sorted-arrays","tag-methods-of-sampling-in-statistics","tag-min-heap","tag-n-element","tag-population-vs-sample","tag-quick-select","tag-sample-in-statistics","tag-sample-statistic","tag-sample-statistics","tag-sample-vs-population","tag-sampling-techniques-in-statistics","tag-sampling-types","tag-select-max","tag-smallest-element","tag-statistical-sampling","tag-statistics-examples","tag-systematic-random-sampling","tag-systematic-sampling","tag-systematic-sampling-definition","tag-th-element","tag-the-smallest-element","tag-tj-maxx","tag-types-of-sampling","tag-types-of-sampling-methods","tag-types-of-sampling-techniques","tag-types-of-statistics","tag-unsorted","tag-what-is-a-stratified-sample","tag-what-is-systematic-sampling"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25284","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25284"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25284\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25284"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25284"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25284"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}