{"id":25276,"date":"2017-10-15T16:59:28","date_gmt":"2017-10-15T11:29:28","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25276"},"modified":"2017-10-15T16:59:28","modified_gmt":"2017-10-15T11:29:28","slug":"kth-smallestlargest-element-unsorted-array-set-2-expected-linear-time","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/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<\/a><\/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 \u201cPRACTICE<\/u><\/b>\u201d first, before moving on to the solution.<\/p>\n[ad type=\u201dbanner\u201d]\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
Following is implementation of above Randomized QuickSelect.<\/p>\n
C Programing<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20implementation%20of%20randomized%20quickSelect%0A%23include%3Ciostream%3E%0A%23include%3Cclimits%3E%0A%23include%3Ccstdlib%3E%0Ausing%20namespace%20std%3B%0A%20%0Aint%20randomPartition(int%20arr%5B%5D%2C%20int%20l%2C%20int%20r)%3B%0A%20%0A%2F%2F%20This%20function%20returns%20k\u2019th%20smallest%20element%20in%20arr%5Bl..r%5D%20using%0A%2F%2F%20QuickSort%20based%20method.%20ASSUMPTION%3A%20ELEMENTS%20IN%20ARR%5B%5D%20ARE%20DISTINCT%0Aint%20kthSmallest(int%20arr%5B%5D%2C%20int%20l%2C%20int%20r%2C%20int%20k)%0A%7B%0A%20%20%20%20%2F%2F%20If%20k%20is%20smaller%20than%20number%20of%20elements%20in%20array%0A%20%20%20%20if%20(k%20%3E%200%20%26%26%20k%20%3C%3D%20r%20-%20l%20%2B%201)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Partition%20the%20array%20around%20a%20random%20element%20and%0A%20%20%20%20%20%20%20%20%2F%2F%20get%20position%20of%20pivot%20element%20in%20sorted%20array%0A%20%20%20%20%20%20%20%20int%20pos%20%3D%20randomPartition(arr%2C%20l%2C%20r)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20position%20is%20same%20as%20k%0A%20%20%20%20%20%20%20%20if%20(pos-l%20%3D%3D%20k-1)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20arr%5Bpos%5D%3B%0A%20%20%20%20%20%20%20%20if%20(pos-l%20%3E%20k-1)%20%20%2F%2F%20If%20position%20is%20more%2C%20recur%20for%20left%20subarray%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20kthSmallest(arr%2C%20l%2C%20pos-1%2C%20k)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Else%20recur%20for%20right%20subarray%0A%20%20%20%20%20%20%20%20return%20kthSmallest(arr%2C%20pos%2B1%2C%20r%2C%20k-pos%2Bl-1)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20If%20k%20is%20more%20than%20number%20of%20elements%20in%20array%0A%20%20%20%20return%20INT_MAX%3B%0A%7D%0A%20%0Avoid%20swap(int%20*a%2C%20int%20*b)%0A%7B%0A%20%20%20%20int%20temp%20%3D%20*a%3B%0A%20%20%20%20*a%20%3D%20*b%3B%0A%20%20%20%20*b%20%3D%20temp%3B%0A%7D%0A%20%0A%2F%2F%20Standard%20partition%20process%20of%20QuickSort().%20%20It%20considers%20the%20last%0A%2F%2F%20element%20as%20pivot%20and%20moves%20all%20smaller%20element%20to%20left%20of%20it%20and%0A%2F%2F%20greater%20elements%20to%20right.%20This%20function%20is%20used%20by%20randomPartition()%0Aint%20partition(int%20arr%5B%5D%2C%20int%20l%2C%20int%20r)%0A%7B%0A%20%20%20%20int%20x%20%3D%20arr%5Br%5D%2C%20i%20%3D%20l%3B%0A%20%20%20%20for%20(int%20j%20%3D%20l%3B%20j%20%3C%3D%20r%20-%201%3B%20j%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(arr%5Bj%5D%20%3C%3D%20x)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20swap(%26arr%5Bi%5D%2C%20%26arr%5Bj%5D)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20i%2B%2B%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20swap(%26arr%5Bi%5D%2C%20%26arr%5Br%5D)%3B%0A%20%20%20%20return%20i%3B%0A%7D%0A%20%0A%2F%2F%20Picks%20a%20random%20pivot%20element%20between%20l%20and%20r%20and%20partitions%0A%2F%2F%20arr%5Bl..r%5D%20arount%20the%20randomly%20picked%20element%20using%20partition()%0Aint%20randomPartition(int%20arr%5B%5D%2C%20int%20l%2C%20int%20r)%0A%7B%0A%20%20%20%20int%20n%20%3D%20r-l%2B1%3B%0A%20%20%20%20int%20pivot%20%3D%20rand()%20%25%20n%3B%0A%20%20%20%20swap(%26arr%5Bl%20%2B%20pivot%5D%2C%20%26arr%5Br%5D)%3B%0A%20%20%20%20return%20partition(arr%2C%20l%2C%20r)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20methods%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr%5B%5D%20%3D%20%7B12%2C%203%2C%205%2C%207%2C%204%2C%2019%2C%2026%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%2C%20k%20%3D%203%3B%0A%20%20%20%20cout%20%3C%3C%20%22K\u2019th%20smallest%20element%20is%20%22%20%3C%3C%20kthSmallest(arr%2C%200%2C%20n-1%2C%20k)%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\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 or MIT video lecture 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=\u201dbanner\u201d]\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":[82927,1,71670,83514],"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-25276","post","type-post","status-publish","format-standard","hentry","category-c-programming-2","category-coding","category-searching-and-sorting","category-unsorted-array","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\/25276","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=25276"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25276\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25276"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25276"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25276"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}