How to find the kth largest element in an unsorted array of length n in O n

Question

I believe there s a way to find the kth largest element in an unsorted array of length n in O n    Or perhaps it s  expected  O n  or something   How can we do this

User · Answer

I implemented finding kth minimimum in n unsorted elements using dynamic programming, specifically tournament method. The execution time is O(n + klog(n)). The mechanism used is listed as one of methods on Wikipedia page about Selection Algorithm (as indicated in one of the posting above). You can read about the algorithm and also find code (java) on my blog page Finding Kth Minimum. In addition the logic can do partial ordering of the list - return first K min (or max) in O(klog(n)) time.

Though the code provided result kth minimum, similar logic can be employed to find kth maximum in O(klog(n)), ignoring the pre-work done to create tournament tree.

User · Answer

What I would do is this   initialize empty doubly linked list l for each element e in array     if e larger than head l          make e the new head of l         if size l   gt  k             remove last element from l  the last element of l should now be the kth largest element   You can simply store pointers to the first and last element in the linked list  They only change when updates to the list are made   Update   initialize empty sorted tree l for each element e in array     if e between head l  and tail l          insert e into l    O log k          if size l   gt  k             remove last element from l  the last element of l should now be the kth largest element

User · Answer

For very small values of k  i e  when k  lt  lt  n   we can get it done in  O n  time  Otherwise  if k is comparable to n  we get it in O nlogn

User · Answer

This is called finding the k-th order statistic  There s a very simple randomized algorithm  called quickselect  taking O n  average time  O n 2  worst case time  and a pretty complicated non-randomized algorithm  called introselect  taking O n  worst case time  There s some info on Wikipedia  but it s not very good   Everything you need is in these powerpoint slides  Just to extract the basic algorithm of the O n  worst-case algorithm  introselect    Select A n i       Divide input into  n 5  groups of size 5          Partition on median-of-medians        medians   array of each group   s median      pivot   Select medians   n 5    n 10       Left Array L and Right Array G   partition A  pivot          Find ith element in L  pivot  or G        k    L    1     If i   k  return pivot     If i  lt  k  return Select L  k-1  i      If i  gt  k  return Select G  n-k  i-k    It s also very nicely detailed in the Introduction to Algorithms book by Cormen et al

User · Answer

iterate through the list   if the current value is larger than the stored largest value  store it as the largest value and bump the 1-4 down and 5 drops off the list  If not compare it to number 2 and do the same thing   Repeat  checking it against all 5 stored values  this should do it in O n

User · Answer

Go to the End of this link                http   www geeksforgeeks org kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time

User · Answer

Although not very sure about O n  complexity  but it will be sure to be between O n  and nLog n   Also sure to be closer to O n  than nLog n   Function is written in Java  public int quickSelect ArrayList lt Integer gt list  int nthSmallest         Choose random number in range of 0 to array length     Random random    new Random          This will give random number which is not greater than length - 1     int pivotIndex   random nextInt list size   - 1         int pivot   list get pivotIndex        ArrayList lt Integer gt  smallerNumberList   new ArrayList lt Integer gt         ArrayList lt Integer gt  greaterNumberList   new ArrayList lt Integer gt            Split list into two         Value smaller than pivot should go to smallerNumberList       Value greater than pivot should go to greaterNumberList       Do nothing for value which is equal to pivot     for int i 0  i lt list size    i             if list get i  lt pivot               smallerNumberList add list get i                      else if list get i  gt pivot               greaterNumberList add list get i                      else                Do nothing                        If smallerNumberList size is greater than nthSmallest value  nthSmallest number must be in this list      if nthSmallest  lt  smallerNumberList size             return quickSelect smallerNumberList  nthSmallest               If nthSmallest is greater than   list size   - greaterNumberList size      nthSmallest number must be in this list       The step is bit tricky  If confusing  please see the above loop once again for clarification      else if nthSmallest  gt   list size   - greaterNumberList size                nthSmallest will have to be changed here    list size   - greaterNumberList size     elements are already in            smallerNumberList         nthSmallest   nthSmallest -  list size   - greaterNumberList size             return quickSelect greaterNumberList nthSmallest             else          return pivot

User · Answer

First we can build a BST from unsorted array which takes O n  time and from the BST we can find the kth smallest element in O log n   which over all counts to an order of O n

User · Answer

You can find the kth smallest element in O n  time and constant space  If we consider the array is only for integers   The approach is to do a binary search on the range of Array values  If we have a min value and a max value both in integer range  we can do a binary search on that range  We can write a comparator function which will tell us if any value is the kth-smallest or smaller than kth-smallest or bigger than kth-smallest  Do the binary search until you reach the kth-smallest number  Here is the code for that  class Solution   def  iskthsmallest self  A  val  k       less count  equal count   0  0     for i in range len A            if A i     val  equal count    1         if A i   lt  val  less count    1      if less count  gt   k  return 1     if less count   equal count  lt  k  return -1     return 0  def kthsmallest binary self  A  min val  max val  k       if min val    max val          return min val     mid    min val   max val  2     iskthsmallest   self  iskthsmallest A  mid  k      if iskthsmallest    0  return mid     if iskthsmallest  gt  0  return self kthsmallest binary A  min val  mid  k      return self kthsmallest binary A  mid 1  max val  k      param A   tuple of integers    param B   integer    return an integer def kthsmallest self  A  k       if not A  return 0     if k  gt  len A   return 0     min val  max val   min A   max A      return self kthsmallest binary A  min val  max val  k

User · Answer

it is similar to the quickSort strategy  where we pick an arbitrary pivot  and bring the smaller elements to its left  and the larger to the right      public static int kthElInUnsortedList List lt int gt  list  int k                if  list Count    1              return list 0            List lt int gt  left   new List lt int gt             List lt int gt  right   new List lt int gt              int pivotIndex   list Count   2          int pivot   list pivotIndex     arbitrary          for  int i   0  i  lt  list Count  amp  amp  i    pivotIndex  i                          int currentEl   list i               if  currentEl  lt  pivot                  left Add currentEl               else                 right Add currentEl                      if  k    left Count   1              return pivot           if  left Count  lt  k              return kthElInUnsortedList right  k - left Count - 1           else             return kthElInUnsortedList left  k

User · Answer

Have Priority queue created  Insert all the elements into heap  Call poll   k times   public static int getKthLargestElements int   arr        PriorityQueue lt Integer gt  pq    new PriorityQueue lt  gt   x   y  - gt   y-x          insert all the elements into heap     for int ele   arr         pq offer ele          call poll   k times     int i 0      while i amp lt k                int result   pq poll               return result

User · Answer

This is called finding the k-th order statistic  There s a very simple randomized algorithm  called quickselect  taking O n  average time  O n 2  worst case time  and a pretty complicated non-randomized algorithm  called introselect  taking O n  worst case time  There s some info on Wikipedia  but it s not very good   Everything you need is in these powerpoint slides  Just to extract the basic algorithm of the O n  worst-case algorithm  introselect    Select A n i       Divide input into  n 5  groups of size 5          Partition on median-of-medians        medians   array of each group   s median      pivot   Select medians   n 5    n 10       Left Array L and Right Array G   partition A  pivot          Find ith element in L  pivot  or G        k    L    1     If i   k  return pivot     If i  lt  k  return Select L  k-1  i      If i  gt  k  return Select G  n-k  i-k    It s also very nicely detailed in the Introduction to Algorithms book by Cormen et al

User · Answer

Here is a C   implementation of Randomized QuickSelect  The idea is to randomly pick a pivot element  To implement randomized partition  we use a random function  rand   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     include lt iostream gt   include lt climits gt   include lt cstdlib gt  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  ALL ELEMENTS IN ARR   ARE DISTINCT int kthSmallest int arr    int l  int r  int k           If k is smaller than number of elements in array     if  k  gt  0  amp  amp  k  lt   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  gt  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  lt   r - 1  j                  if  arr j   lt   x    arr i  is bigger than arr j  so swap them                       swap  amp arr i    amp arr j                i                        swap  amp arr i    amp arr r       swap the pivot     return i        Picks a random pivot element between l and r and partitions    arr l  r  around the randomly picked element using partition   int randomPartition int arr    int l  int r        int n   r-l 1      int pivot   rand     n      swap  amp arr l   pivot    amp arr r        return partition arr  l  r         Driver program to test above methods int main         int arr      12  3  5  7  4  19  26       int n   sizeof arr  sizeof arr 0    k   3      cout  lt  lt   K th smallest element is    lt  lt  kthSmallest arr  0  n-1  k       return 0      The worst case time complexity of the above solution is still O n2  In worst case  the randomized function may always pick a corner element  The expected time complexity of above randomized QuickSelect is T n

User · Answer

How about this kinda approach   Maintain a buffer of length k and a tmp max  getting tmp max is O k  and is done n times so something like O kn      Is it right or am i missing something    Although it doesn t beat average case of quickselect and worst case of median statistics method but its pretty easy to understand and implement

User · Answer

i would like to suggest one answer  if we take the first k elements and sort them into a linked list of k values  now for every other value even for the worst case if we do insertion sort for rest n-k values even in the worst case number of comparisons will be k  n-k  and for prev k values to be sorted let it be k  k-1  so it comes out to be  nk-k  which is o n   cheers

User · Answer

As per this paper Finding the Kth largest item in a list of n items the following algorithm will take O n  time in worst case    Divide the array in to n 5 lists of 5 elements each  Find the median in each sub array of 5 elements  Recursively  nd the median of all the medians  lets call it M Partition the array in to two sub array 1st sub-array contains the elements larger than M   lets say this sub-array is a1   while other sub-array contains the elements smaller then M   lets call this sub-array a2  If k  lt    a1   return selection  a1 k   If k- 1    a1   return M  If k   a1    1  return selection a2 k -a1 - 1     Analysis  As suggested in the original paper      We use the median to partition the list into two halves the first half    if k  lt   n 2   and the second half otherwise   This algorithm takes   time cn at the first level of recursion for some constant c  cn 2 at   the next level  since we recurse in a list of size n 2   cn 4 at the   third level  and so on  The total time taken is cn   cn 2   cn 4            2cn   o n     Why partition size is taken 5 and not 3   As mentioned in original paper       Dividing the list by 5 assures a worst-case split of 70 - 30  Atleast   half of the medians greater than the median-of-medians  hence atleast   half of the n 5 blocks have atleast 3 elements and this gives a   3n 10 split  which means the other partition is 7n 10 in worst case    That gives T n    T n 5  T 7n 10  O n   Since n 5 7n 10  lt  1  the   worst-case running time isO n     Now I have tried to implement the above algorithm as   public static int findKthLargestUsingMedian Integer   array  int k               Step 1  Divide the list into n 5 lists of 5 element each          int noOfRequiredLists    int  Math ceil array length   5 0              Step 2  Find pivotal element aka median of medians          int medianOfMedian    findMedianOfMedians array  noOfRequiredLists             Now we need two lists split using medianOfMedian as pivot  All elements in list listOne will be grater than medianOfMedian and listTwo will have elements lesser than medianOfMedian          List lt Integer gt  listWithGreaterNumbers   new ArrayList lt  gt        elements greater than medianOfMedian         List lt Integer gt  listWithSmallerNumbers   new ArrayList lt  gt        elements less than medianOfMedian         for  Integer element   array                if  element  lt  medianOfMedian                    listWithSmallerNumbers add element                 else if  element  gt  medianOfMedian                    listWithGreaterNumbers add element                                      Next step          if  k  lt   listWithGreaterNumbers size    return findKthLargestUsingMedian  Integer    listWithGreaterNumbers toArray new Integer listWithGreaterNumbers size      k           else if   k - 1     listWithGreaterNumbers size    return medianOfMedian          else if  k  gt   listWithGreaterNumbers size     1   return findKthLargestUsingMedian  Integer    listWithSmallerNumbers toArray new Integer listWithSmallerNumbers size      k-listWithGreaterNumbers size  -1           return -1             public static int findMedianOfMedians Integer   mainList  int noOfRequiredLists            int   medians   new int noOfRequiredLists           for  int count   0  count  lt  noOfRequiredLists  count                  int startOfPartialArray   5   count              int endOfPartialArray   startOfPartialArray   5              Integer   partialArray   Arrays copyOfRange  Integer    mainList  startOfPartialArray  endOfPartialArray                  Step 2  Find median of each of these sublists              int medianIndex   partialArray length 2              medians count    partialArray medianIndex                        Step 3  Find median of the medians          return medians medians length   2           Just for sake of completion  another algorithm makes use of Priority Queue and takes time O nlogn    public static int findKthLargestUsingPriorityQueue Integer   nums  int k            int p   0          int numElements   nums length             create priority queue where all the elements of nums will be stored         PriorityQueue lt Integer gt  pq   new PriorityQueue lt Integer gt                 place all the elements of the array to this priority queue         for  int n   nums                pq add n                         extract the kth largest element         while  numElements - k   1  gt  0                p   pq poll                k                       return p          Both of these algorithms can be tested as   public static void main String   args  throws IOException           Integer   numbers   new Integer   2  3  5  4  1  12  11  13  16  7  8  6  10  9  17  15  19  20  18  23  21  22  25  24  14           System out println findKthLargestUsingMedian numbers  8            System out println findKthLargestUsingPriorityQueue numbers  8            As expected output is  18 18

User · Answer

If you want a true O n  algorithm  as opposed to O kn  or something like that  then you should use quickselect  it s basically quicksort where you throw out the partition that you re not interested in   My prof has a great writeup  with the runtime analysis   reference   The QuickSelect algorithm quickly finds the k-th smallest element of an unsorted array of n elements   It is a RandomizedAlgorithm  so we compute the worst-case expected running time   Here is the algorithm   QuickSelect A  k    let r be chosen uniformly at random in the range 1 to length A    let pivot   A r    let A1  A2 be new arrays     split into a pile A1 of small elements and A2 of big elements   for i   1 to n     if A i   lt  pivot then       append A i  to A1     else if A i   gt  pivot then       append A i  to A2     else         do nothing   end for   if k  lt   length A1         it s in the pile of small elements     return QuickSelect A1  k    else if k  gt  length A  - length A2        it s in the pile of big elements     return QuickSelect A2  k -  length A  - length A2     else       it s equal to the pivot     return pivot   What is the running time of this algorithm   If the adversary flips coins for us  we may find that the pivot is always the largest element and k is always 1  giving a running time of   T n    Theta n    T n-1    Theta n2   But if the choices are indeed random  the expected running time is given by  T n   lt   Theta n     1 n   i 1 to nT max i  n-i-1    where we are making the not entirely reasonable assumption that the recursion always lands in the larger of A1 or A2   Let s guess that T n   lt   an for some a   Then we get  T n     lt   cn    1 n   i 1 to nT max i-1  n-i      cn    1 n   i 1 to floor n 2  T n-i     1 n   i floor n 2  1 to n T i    lt   cn   2  1 n   i floor n 2  to n T i    lt   cn   2  1 n   i floor n 2  to n ai  and now somehow we have to get the horrendous sum on the right of the plus sign to absorb the cn on the left   If we just bound it as 2 1 n   i n 2 to n an  we get roughly 2 1 n  n 2 an   an   But this is too big - there s no room to squeeze in an extra cn   So let s expand the sum using the arithmetic series formula    i floor n 2  to n i       i 1 to n i -  i 1 to floor n 2  i      n n 1  2 - floor n 2  floor n 2  1  2     lt   n2 2 -  n 4 2 2       15 32 n2  where we take advantage of n being  sufficiently large  to replace the ugly floor n 2  factors with the much cleaner  and smaller  n 4   Now we can continue with  cn   2  1 n   i floor n 2  to n ai    lt   cn    2a n   15 32  n2    n  c    15 16 a    lt   an  provided a  gt  16c   This gives T n    O n    It s clearly Omega n   so we get T n    Theta n

User · Answer

Haskell Solution   kthElem index list   sort list    index  withShape                     withShape   x xs   y ys    x   withShape xs ys  sort             sort  x xs     sort ls  withShape  ls      x      sort rs  withShape  rs    where    ls   filter   lt   x     rs   filter   gt   x    This implements the median of median solutions by using the withShape method to discover the size of a partition without actually computing it

User · Answer

kth largest element means  we need to sort the array and then  count down from the end of array  For example  const array   2  32  12  3  78  99  898  8  1     we need to sort this  const sortedArray   1   2   3    8  12  32  78  99  898    5th largest element means from the end count down 5 elements which is 12  By default most languages implement quick sort or merge sort because they are the most optimized sorts  I solve this problem with the quick sort  Quick sort sorts the array in place  it does not give us back a new array and like merge sort it is recursive  Downside of quick sort  in worst case scenario  its time complexity is O n  2   quot n square quot   Quick sort is divide-and-conquer algorithm which is a problem is solved by solving all of its smaller components  We choose the last element as the pivot element  Some algorithms choose the first item as pivot  some choose the last item when it starts   Pivot element is the partitioning element  this is our array  2  32  12  3  78  99  898  8  1  we use 2 pointers  i j starts from the first element   quot i quot  keeps track of where is the final place of pivot  i j 2   starting point   quot j quot  is going to scan the array  and compare each element to the pivot  If  quot j quot  is smaller than pivot  we will swap  quot i quot  and  quot j quot  and move  quot i quot  and  quot j quot  forward  When  quot j quot  reaches pivot  we swap  quot i quot  with pivot  In our example pivot is 1  1 is the smaller number   quot j quot  will reach the pivot 1 without swapping  quot i quot   quot j quot   Remember  quot i quot  is the placeholder for the pivot  So when  quot j quot  reaches pivot  1 and 2 will be swapped  The purpose of this operation to find all of elements that smaller than pivot to its left  Note that all the elements that are on the left of pivot is smaller than pivot  but left side is not sorted  Then we divide the array from the pivot into 2 sub arrays and recursively apply the quick sort  const quickSort   function  array  left  right         if left right  it means we have only one item  it is already sorted   if  left  lt  right        const partitionIndex   partition array  left  right       quickSort array  left  partitionIndex - 1        quickSort array  partitionIndex   1  right           With using  quot i quot  and  quot j quot  pointers  this is how we find the partitioning index const partition   function  array  left  right      const pivotElement   array right     let partitionIndex   left    for  let j   left  j  lt  right  j          if  array j   lt  pivotElement          swap array  partitionIndex  j         partitionIndex                   if none of the  quot j quot  values is smaller than pivot  when  quot j quot  reaches the pivot  we swap  quot i th quot  element with pivot   swap array  partitionIndex  right     return partitionIndex      this is a simple implementation of swap function  const swap   function  array  i  j      const temp   array i     array i    array j     array j    temp

User · Answer

Find the median of the array in linear time  then use partition procedure exactly as in quicksort to divide the array in two parts  values to the left of the median lesser   lt    than than median and to the right greater than       median  that too can be done in lineat time  now  go to that part of the array where kth element lies   Now recurrence becomes  T n    T n 2    cn  which gives me O  n  overal

User · Answer

Here is the implementation of the algorithm eladv suggested I also put here the implementation with random pivot    public class Median        public static void main String   s             int   test    4 18 20 3 7 13 5 8 2 1 15 17 25 30 16           System out println selectK test 8                        int n   100000000          int   test   new int n           for int i 0  i lt test length  i                test i     int  Math random   test length            long start   System currentTimeMillis            random selectK test  test length 2           long end   System currentTimeMillis            System out println end - start                         public static int random selectK int   a  int k            if a length  lt   1              return a 0            int r    int  Math random     a length           int p   a r            int small   0  equal   0  big   0          for int i 0  i lt a length  i                  if a i   lt  p  small                else if a i     p  equal                else if a i   gt  p  big                       if k  lt   small                int   temp   new int small               for int i 0  j 0  i lt a length  i                    if a i   lt  p                      temp j      a i               return random selectK temp  k                      else if  k  lt   small equal              return p           else               int   temp   new int big               for int i 0  j 0  i lt a length  i                    if a i   gt  p                      temp j      a i               return random selectK temp k-small-equal                        public static int selectK int   a  int k            if a length  lt   5                Arrays sort a               return a k-1                      int p   median of medians a            int small   0  equal   0  big   0          for int i 0  i lt a length  i                  if a i   lt  p  small                else if a i     p  equal                else if a i   gt  p  big                       if k  lt   small                int   temp   new int small               for int i 0  j 0  i lt a length  i                    if a i   lt  p                      temp j      a i               return selectK temp  k                      else if  k  lt   small equal              return p           else               int   temp   new int big               for int i 0  j 0  i lt a length  i                    if a i   gt  p                      temp j      a i               return selectK temp k-small-equal                        private static int median of medians int   a            int   b   new int a length 5           int   temp   new int 5           for int i 0  i lt b length  i                  for int j 0  j lt 5  j                    temp j    a 5 i   j               Arrays sort temp               b i    temp 2                      return selectK b  b length 2   1

User · Answer

The C   standard library has almost exactly that function call nth element  although it does modify your data   It has expected linear run-time  O N   and it also does a partial sort   const int N        double a N           const int m           m  lt  N nth element  a  a   m  a   N      a m  contains the mth element in a

User · Answer

This is called finding the k-th order statistic  There s a very simple randomized algorithm  called quickselect  taking O n  average time  O n 2  worst case time  and a pretty complicated non-randomized algorithm  called introselect  taking O n  worst case time  There s some info on Wikipedia  but it s not very good   Everything you need is in these powerpoint slides  Just to extract the basic algorithm of the O n  worst-case algorithm  introselect    Select A n i       Divide input into  n 5  groups of size 5          Partition on median-of-medians        medians   array of each group   s median      pivot   Select medians   n 5    n 10       Left Array L and Right Array G   partition A  pivot          Find ith element in L  pivot  or G        k    L    1     If i   k  return pivot     If i  lt  k  return Select L  k-1  i      If i  gt  k  return Select G  n-k  i-k    It s also very nicely detailed in the Introduction to Algorithms book by Cormen et al

User · Answer

A quick Google on that   kth largest element array   returned this  http   discuss joelonsoftware com default asp interview 11 509587 17   Make one pass through tracking the three largest values so far       it was specifically for 3d largest   and this answer   Build a heap priority queue   O n  Pop top element   O log n  Pop top element   O log n  Pop top element   O log n   Total   O n    3 O log n    O n

User · Answer

A Programmer s Companion to Algorithm Analysis gives a version that is O n   although the author states that the constant factor is so high  you d probably prefer the naive sort-the-list-then-select method   I answered the letter of your question

User · Answer

Go to the End of this link                http   www geeksforgeeks org kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time

User · Answer

As per this paper Finding the Kth largest item in a list of n items the following algorithm will take O n  time in worst case    Divide the array in to n 5 lists of 5 elements each  Find the median in each sub array of 5 elements  Recursively  nd the median of all the medians  lets call it M Partition the array in to two sub array 1st sub-array contains the elements larger than M   lets say this sub-array is a1   while other sub-array contains the elements smaller then M   lets call this sub-array a2  If k  lt    a1   return selection  a1 k   If k- 1    a1   return M  If k   a1    1  return selection a2 k -a1 - 1     Analysis  As suggested in the original paper      We use the median to partition the list into two halves the first half    if k  lt   n 2   and the second half otherwise   This algorithm takes   time cn at the first level of recursion for some constant c  cn 2 at   the next level  since we recurse in a list of size n 2   cn 4 at the   third level  and so on  The total time taken is cn   cn 2   cn 4            2cn   o n     Why partition size is taken 5 and not 3   As mentioned in original paper       Dividing the list by 5 assures a worst-case split of 70 - 30  Atleast   half of the medians greater than the median-of-medians  hence atleast   half of the n 5 blocks have atleast 3 elements and this gives a   3n 10 split  which means the other partition is 7n 10 in worst case    That gives T n    T n 5  T 7n 10  O n   Since n 5 7n 10  lt  1  the   worst-case running time isO n     Now I have tried to implement the above algorithm as   public static int findKthLargestUsingMedian Integer   array  int k               Step 1  Divide the list into n 5 lists of 5 element each          int noOfRequiredLists    int  Math ceil array length   5 0              Step 2  Find pivotal element aka median of medians          int medianOfMedian    findMedianOfMedians array  noOfRequiredLists             Now we need two lists split using medianOfMedian as pivot  All elements in list listOne will be grater than medianOfMedian and listTwo will have elements lesser than medianOfMedian          List lt Integer gt  listWithGreaterNumbers   new ArrayList lt  gt        elements greater than medianOfMedian         List lt Integer gt  listWithSmallerNumbers   new ArrayList lt  gt        elements less than medianOfMedian         for  Integer element   array                if  element  lt  medianOfMedian                    listWithSmallerNumbers add element                 else if  element  gt  medianOfMedian                    listWithGreaterNumbers add element                                      Next step          if  k  lt   listWithGreaterNumbers size    return findKthLargestUsingMedian  Integer    listWithGreaterNumbers toArray new Integer listWithGreaterNumbers size      k           else if   k - 1     listWithGreaterNumbers size    return medianOfMedian          else if  k  gt   listWithGreaterNumbers size     1   return findKthLargestUsingMedian  Integer    listWithSmallerNumbers toArray new Integer listWithSmallerNumbers size      k-listWithGreaterNumbers size  -1           return -1             public static int findMedianOfMedians Integer   mainList  int noOfRequiredLists            int   medians   new int noOfRequiredLists           for  int count   0  count  lt  noOfRequiredLists  count                  int startOfPartialArray   5   count              int endOfPartialArray   startOfPartialArray   5              Integer   partialArray   Arrays copyOfRange  Integer    mainList  startOfPartialArray  endOfPartialArray                  Step 2  Find median of each of these sublists              int medianIndex   partialArray length 2              medians count    partialArray medianIndex                        Step 3  Find median of the medians          return medians medians length   2           Just for sake of completion  another algorithm makes use of Priority Queue and takes time O nlogn    public static int findKthLargestUsingPriorityQueue Integer   nums  int k            int p   0          int numElements   nums length             create priority queue where all the elements of nums will be stored         PriorityQueue lt Integer gt  pq   new PriorityQueue lt Integer gt                 place all the elements of the array to this priority queue         for  int n   nums                pq add n                         extract the kth largest element         while  numElements - k   1  gt  0                p   pq poll                k                       return p          Both of these algorithms can be tested as   public static void main String   args  throws IOException           Integer   numbers   new Integer   2  3  5  4  1  12  11  13  16  7  8  6  10  9  17  15  19  20  18  23  21  22  25  24  14           System out println findKthLargestUsingMedian numbers  8            System out println findKthLargestUsingPriorityQueue numbers  8            As expected output is  18 18

User · Answer

i would like to suggest one answer  if we take the first k elements and sort them into a linked list of k values  now for every other value even for the worst case if we do insertion sort for rest n-k values even in the worst case number of comparisons will be k  n-k  and for prev k values to be sorted let it be k  k-1  so it comes out to be  nk-k  which is o n   cheers

User · Answer

First we can build a BST from unsorted array which takes O n  time and from the BST we can find the kth smallest element in O log n   which over all counts to an order of O n

User · Answer

For very small values of k  i e  when k  lt  lt  n   we can get it done in  O n  time  Otherwise  if k is comparable to n  we get it in O nlogn

User · Answer

You can find the kth smallest element in O n  time and constant space  If we consider the array is only for integers   The approach is to do a binary search on the range of Array values  If we have a min value and a max value both in integer range  we can do a binary search on that range  We can write a comparator function which will tell us if any value is the kth-smallest or smaller than kth-smallest or bigger than kth-smallest  Do the binary search until you reach the kth-smallest number  Here is the code for that  class Solution   def  iskthsmallest self  A  val  k       less count  equal count   0  0     for i in range len A            if A i     val  equal count    1         if A i   lt  val  less count    1      if less count  gt   k  return 1     if less count   equal count  lt  k  return -1     return 0  def kthsmallest binary self  A  min val  max val  k       if min val    max val          return min val     mid    min val   max val  2     iskthsmallest   self  iskthsmallest A  mid  k      if iskthsmallest    0  return mid     if iskthsmallest  gt  0  return self kthsmallest binary A  min val  mid  k      return self kthsmallest binary A  mid 1  max val  k      param A   tuple of integers    param B   integer    return an integer def kthsmallest self  A  k       if not A  return 0     if k  gt  len A   return 0     min val  max val   min A   max A      return self kthsmallest binary A  min val  max val  k

User · Answer

There is also Wirth s selection algorithm  which has a simpler implementation than QuickSelect  Wirth s selection algorithm is slower than QuickSelect  but with some improvements it becomes faster    In more detail  Using Vladimir Zabrodsky s MODIFIND optimization and the median-of-3 pivot selection and paying some attention to the final steps of the partitioning part of the algorithm  i ve came up with the following algorithm  imaginably named  LefSelect      define F SWAP a b    float temp  a   a   b   b  temp       Note  The code needs more than 2 elements to work float lefselect float a    const int n  const int k        int l 0  m   n-1  i l  j m      float x       while  l lt m            if  a k   lt  a i    F SWAP a i  a k            if  a j   lt  a i    F SWAP a i  a j            if  a j   lt  a k    F SWAP a k  a j             x a k           while  j gt k  amp  i lt k                do i    while  a i  lt x               do j--  while  a j  gt x                F SWAP a i  a j                      i    j--           if  j lt k                while  a i  lt x  i                l i  j m                    if  k lt i                while  x lt a j   j--              m j  i l                      return a k       In benchmarks that i did here  LefSelect is 20-30  faster than QuickSelect

User · Answer

There is also one algorithm  that outperforms quickselect algorithm  It s called Floyd-Rivets  FR  algorithm   Original article  https   doi org 10 1145 360680 360694  Downloadable version  http   citeseerx ist psu edu viewdoc download doi 10 1 1 309 7108 amp rep rep1 amp type pdf  Wikipedia article https   en wikipedia org wiki Floyd E2 80 93Rivest algorithm   I tried to implement quickselect and FR algorithm in C    Also I compared them to the standard C   library implementations std  nth element  which is basically introselect hybrid of quickselect and heapselect   The result was  quickselect and nth element ran comparably on average  but FR algorithm ran approx  twice as fast compared to them    Sample code that I used for FR algorithm   template  lt typename T gt  T FRselect std  vector lt T gt  amp  data  const size t amp  n        if  n    0          return   std  min element data begin    data end          else if  n    data size   - 1          return   std  max element data begin    data end          else         return  FRselect data  0  data size   - 1  n      template  lt typename T gt  T  FRselect std  vector lt T gt  amp  data  const size t amp  left  const size t amp  right  const size t amp  n        size t leftIdx   left      size t rightIdx   right       while  rightIdx  gt  leftIdx                if  rightIdx - leftIdx  gt  600                        size t range   rightIdx - leftIdx   1              long long i   n -  long long leftIdx   1              long long z   log range               long long s   0 5   exp 2   z   3               long long sd   0 5   sqrt z   s    range - s    range    sgn i -  long long range   2                size t newLeft   fmax leftIdx  n - i   s   range   sd               size t newRight   fmin rightIdx  n    range - i    s   range   sd                 FRselect data  newLeft  newRight  n                     T t   data n           size t i   leftIdx          size t j   rightIdx             arrange pivot and right index         std  swap data leftIdx   data n            if  data rightIdx   gt  t              std  swap data rightIdx   data leftIdx             while  i  lt  j                        std  swap data i   data j                  i  --j              while  data i   lt  t    i              while  data j   gt  t  --j                     if  data leftIdx     t              std  swap data leftIdx   data j            else                         j              std  swap data j   data rightIdx                         adjust left and right towards the boundaries of the subset            containing the  k - left   1 th smallest element         if  j  lt   n              leftIdx   j   1          if  n  lt   j              rightIdx   j - 1             return data leftIdx      template  lt typename T gt  int sgn T val        return  T 0   lt  val  -  val  lt  T 0

User · Answer

What I would do is this   initialize empty doubly linked list l for each element e in array     if e larger than head l          make e the new head of l         if size l   gt  k             remove last element from l  the last element of l should now be the kth largest element   You can simply store pointers to the first and last element in the linked list  They only change when updates to the list are made   Update   initialize empty sorted tree l for each element e in array     if e between head l  and tail l          insert e into l    O log k          if size l   gt  k             remove last element from l  the last element of l should now be the kth largest element

User · Answer

You can do it in O n   kn    O n   for constant k  for time and O k  for space  by keeping track of the k largest elements you ve seen     For each element in the array you can scan the list of k largest and replace the smallest element with the new one if it is bigger   Warren s priority heap solution is neater though

User · Answer

Below is the link to full implementation with quite an extensive explanation how the algorithm for finding Kth element in an unsorted algorithm works  Basic idea is to partition the array like in QuickSort  But in order to avoid extreme cases  e g  when smallest element is chosen as pivot in every step  so that algorithm degenerates into O n 2  running time   special pivot selection is applied  called median-of-medians algorithm  The whole solution runs in O n  time in worst and in average case   Here is link to the full article  it is about finding Kth smallest element  but the principle is the same for finding Kth largest    Finding Kth Smallest Element in an Unsorted Array

User · Answer

A quick Google on that   kth largest element array   returned this  http   discuss joelonsoftware com default asp interview 11 509587 17   Make one pass through tracking the three largest values so far       it was specifically for 3d largest   and this answer   Build a heap priority queue   O n  Pop top element   O log n  Pop top element   O log n  Pop top element   O log n   Total   O n    3 O log n    O n

User · Answer

it is similar to the quickSort strategy  where we pick an arbitrary pivot  and bring the smaller elements to its left  and the larger to the right      public static int kthElInUnsortedList List lt int gt  list  int k                if  list Count    1              return list 0            List lt int gt  left   new List lt int gt             List lt int gt  right   new List lt int gt              int pivotIndex   list Count   2          int pivot   list pivotIndex     arbitrary          for  int i   0  i  lt  list Count  amp  amp  i    pivotIndex  i                          int currentEl   list i               if  currentEl  lt  pivot                  left Add currentEl               else                 right Add currentEl                      if  k    left Count   1              return pivot           if  left Count  lt  k              return kthElInUnsortedList right  k - left Count - 1           else             return kthElInUnsortedList left  k

User · Answer

I came up with this algorithm and seems to be O n    Let s say k 3 and we want to find the 3rd largest item in the array  I would create three variables and compare each item of the array with the minimum of these three variables  If array item is greater than our minimum  we would replace the min variable with the item value  We continue the same thing until end of the array  The minimum of our three variables is the 3rd largest item in the array   define variables a 0  b 0  c 0 iterate through the array items     find minimum a b c     if item  gt  min then replace the min variable with item value     continue until end of array the minimum of a b c is our answer   And  to find Kth largest item we need K variables   Example   k 3    1 2 4 1 7 3 9 5 6 2 9 8   Final variable values   a 7  answer  b 8 c 9   Can someone please review this and let me know what I am missing

User · Answer

Here is the implementation of the algorithm eladv suggested I also put here the implementation with random pivot    public class Median        public static void main String   s             int   test    4 18 20 3 7 13 5 8 2 1 15 17 25 30 16           System out println selectK test 8                        int n   100000000          int   test   new int n           for int i 0  i lt test length  i                test i     int  Math random   test length            long start   System currentTimeMillis            random selectK test  test length 2           long end   System currentTimeMillis            System out println end - start                         public static int random selectK int   a  int k            if a length  lt   1              return a 0            int r    int  Math random     a length           int p   a r            int small   0  equal   0  big   0          for int i 0  i lt a length  i                  if a i   lt  p  small                else if a i     p  equal                else if a i   gt  p  big                       if k  lt   small                int   temp   new int small               for int i 0  j 0  i lt a length  i                    if a i   lt  p                      temp j      a i               return random selectK temp  k                      else if  k  lt   small equal              return p           else               int   temp   new int big               for int i 0  j 0  i lt a length  i                    if a i   gt  p                      temp j      a i               return random selectK temp k-small-equal                        public static int selectK int   a  int k            if a length  lt   5                Arrays sort a               return a k-1                      int p   median of medians a            int small   0  equal   0  big   0          for int i 0  i lt a length  i                  if a i   lt  p  small                else if a i     p  equal                else if a i   gt  p  big                       if k  lt   small                int   temp   new int small               for int i 0  j 0  i lt a length  i                    if a i   lt  p                      temp j      a i               return selectK temp  k                      else if  k  lt   small equal              return p           else               int   temp   new int big               for int i 0  j 0  i lt a length  i                    if a i   gt  p                      temp j      a i               return selectK temp k-small-equal                        private static int median of medians int   a            int   b   new int a length 5           int   temp   new int 5           for int i 0  i lt b length  i                  for int j 0  j lt 5  j                    temp j    a 5 i   j               Arrays sort temp               b i    temp 2                      return selectK b  b length 2   1

User · Answer

A Programmer s Companion to Algorithm Analysis gives a version that is O n   although the author states that the constant factor is so high  you d probably prefer the naive sort-the-list-then-select method   I answered the letter of your question

User · Answer

Have Priority queue created  Insert all the elements into heap  Call poll   k times   public static int getKthLargestElements int   arr        PriorityQueue lt Integer gt  pq    new PriorityQueue lt  gt   x   y  - gt   y-x          insert all the elements into heap     for int ele   arr         pq offer ele          call poll   k times     int i 0      while i amp lt k                int result   pq poll               return result

User · Answer

The C   standard library has almost exactly that function call nth element  although it does modify your data   It has expected linear run-time  O N   and it also does a partial sort   const int N        double a N           const int m           m  lt  N nth element  a  a   m  a   N      a m  contains the mth element in a

User · Answer

Below is the link to full implementation with quite an extensive explanation how the algorithm for finding Kth element in an unsorted algorithm works  Basic idea is to partition the array like in QuickSort  But in order to avoid extreme cases  e g  when smallest element is chosen as pivot in every step  so that algorithm degenerates into O n 2  running time   special pivot selection is applied  called median-of-medians algorithm  The whole solution runs in O n  time in worst and in average case   Here is link to the full article  it is about finding Kth smallest element  but the principle is the same for finding Kth largest    Finding Kth Smallest Element in an Unsorted Array

User · Answer

The C   standard library has almost exactly that function call nth element  although it does modify your data   It has expected linear run-time  O N   and it also does a partial sort   const int N        double a N           const int m           m  lt  N nth element  a  a   m  a   N      a m  contains the mth element in a

User · Answer

You do like quicksort   Pick an element at random and shove everything either higher or lower   At this point you ll know which element you actually picked  and if it is the kth element you re done  otherwise you repeat with the bin  higher or lower   that the kth element would fall in  Statistically speaking  the time it takes to find the kth element grows with n  O n

User · Answer

If you want a true O n  algorithm  as opposed to O kn  or something like that  then you should use quickselect  it s basically quicksort where you throw out the partition that you re not interested in   My prof has a great writeup  with the runtime analysis   reference   The QuickSelect algorithm quickly finds the k-th smallest element of an unsorted array of n elements   It is a RandomizedAlgorithm  so we compute the worst-case expected running time   Here is the algorithm   QuickSelect A  k    let r be chosen uniformly at random in the range 1 to length A    let pivot   A r    let A1  A2 be new arrays     split into a pile A1 of small elements and A2 of big elements   for i   1 to n     if A i   lt  pivot then       append A i  to A1     else if A i   gt  pivot then       append A i  to A2     else         do nothing   end for   if k  lt   length A1         it s in the pile of small elements     return QuickSelect A1  k    else if k  gt  length A  - length A2        it s in the pile of big elements     return QuickSelect A2  k -  length A  - length A2     else       it s equal to the pivot     return pivot   What is the running time of this algorithm   If the adversary flips coins for us  we may find that the pivot is always the largest element and k is always 1  giving a running time of   T n    Theta n    T n-1    Theta n2   But if the choices are indeed random  the expected running time is given by  T n   lt   Theta n     1 n   i 1 to nT max i  n-i-1    where we are making the not entirely reasonable assumption that the recursion always lands in the larger of A1 or A2   Let s guess that T n   lt   an for some a   Then we get  T n     lt   cn    1 n   i 1 to nT max i-1  n-i      cn    1 n   i 1 to floor n 2  T n-i     1 n   i floor n 2  1 to n T i    lt   cn   2  1 n   i floor n 2  to n T i    lt   cn   2  1 n   i floor n 2  to n ai  and now somehow we have to get the horrendous sum on the right of the plus sign to absorb the cn on the left   If we just bound it as 2 1 n   i n 2 to n an  we get roughly 2 1 n  n 2 an   an   But this is too big - there s no room to squeeze in an extra cn   So let s expand the sum using the arithmetic series formula    i floor n 2  to n i       i 1 to n i -  i 1 to floor n 2  i      n n 1  2 - floor n 2  floor n 2  1  2     lt   n2 2 -  n 4 2 2       15 32 n2  where we take advantage of n being  sufficiently large  to replace the ugly floor n 2  factors with the much cleaner  and smaller  n 4   Now we can continue with  cn   2  1 n   i floor n 2  to n ai    lt   cn    2a n   15 32  n2    n  c    15 16 a    lt   an  provided a  gt  16c   This gives T n    O n    It s clearly Omega n   so we get T n    Theta n

User · Answer

If you want a true O n  algorithm  as opposed to O kn  or something like that  then you should use quickselect  it s basically quicksort where you throw out the partition that you re not interested in   My prof has a great writeup  with the runtime analysis   reference   The QuickSelect algorithm quickly finds the k-th smallest element of an unsorted array of n elements   It is a RandomizedAlgorithm  so we compute the worst-case expected running time   Here is the algorithm   QuickSelect A  k    let r be chosen uniformly at random in the range 1 to length A    let pivot   A r    let A1  A2 be new arrays     split into a pile A1 of small elements and A2 of big elements   for i   1 to n     if A i   lt  pivot then       append A i  to A1     else if A i   gt  pivot then       append A i  to A2     else         do nothing   end for   if k  lt   length A1         it s in the pile of small elements     return QuickSelect A1  k    else if k  gt  length A  - length A2        it s in the pile of big elements     return QuickSelect A2  k -  length A  - length A2     else       it s equal to the pivot     return pivot   What is the running time of this algorithm   If the adversary flips coins for us  we may find that the pivot is always the largest element and k is always 1  giving a running time of   T n    Theta n    T n-1    Theta n2   But if the choices are indeed random  the expected running time is given by  T n   lt   Theta n     1 n   i 1 to nT max i  n-i-1    where we are making the not entirely reasonable assumption that the recursion always lands in the larger of A1 or A2   Let s guess that T n   lt   an for some a   Then we get  T n     lt   cn    1 n   i 1 to nT max i-1  n-i      cn    1 n   i 1 to floor n 2  T n-i     1 n   i floor n 2  1 to n T i    lt   cn   2  1 n   i floor n 2  to n T i    lt   cn   2  1 n   i floor n 2  to n ai  and now somehow we have to get the horrendous sum on the right of the plus sign to absorb the cn on the left   If we just bound it as 2 1 n   i n 2 to n an  we get roughly 2 1 n  n 2 an   an   But this is too big - there s no room to squeeze in an extra cn   So let s expand the sum using the arithmetic series formula    i floor n 2  to n i       i 1 to n i -  i 1 to floor n 2  i      n n 1  2 - floor n 2  floor n 2  1  2     lt   n2 2 -  n 4 2 2       15 32 n2  where we take advantage of n being  sufficiently large  to replace the ugly floor n 2  factors with the much cleaner  and smaller  n 4   Now we can continue with  cn   2  1 n   i floor n 2  to n ai    lt   cn    2a n   15 32  n2    n  c    15 16 a    lt   an  provided a  gt  16c   This gives T n    O n    It s clearly Omega n   so we get T n    Theta n

User · Answer

I implemented finding kth minimimum in n unsorted elements using dynamic programming, specifically tournament method. The execution time is O(n + klog(n)). The mechanism used is listed as one of methods on Wikipedia page about Selection Algorithm (as indicated in one of the posting above). You can read about the algorithm and also find code (java) on my blog page Finding Kth Minimum. In addition the logic can do partial ordering of the list - return first K min (or max) in O(klog(n)) time.

Though the code provided result kth minimum, similar logic can be employed to find kth maximum in O(klog(n)), ignoring the pre-work done to create tournament tree.

User · Answer

A quick Google on that   kth largest element array   returned this  http   discuss joelonsoftware com default asp interview 11 509587 17   Make one pass through tracking the three largest values so far       it was specifically for 3d largest   and this answer   Build a heap priority queue   O n  Pop top element   O log n  Pop top element   O log n  Pop top element   O log n   Total   O n    3 O log n    O n

User · Answer

Although not very sure about O n  complexity  but it will be sure to be between O n  and nLog n   Also sure to be closer to O n  than nLog n   Function is written in Java  public int quickSelect ArrayList lt Integer gt list  int nthSmallest         Choose random number in range of 0 to array length     Random random    new Random          This will give random number which is not greater than length - 1     int pivotIndex   random nextInt list size   - 1         int pivot   list get pivotIndex        ArrayList lt Integer gt  smallerNumberList   new ArrayList lt Integer gt         ArrayList lt Integer gt  greaterNumberList   new ArrayList lt Integer gt            Split list into two         Value smaller than pivot should go to smallerNumberList       Value greater than pivot should go to greaterNumberList       Do nothing for value which is equal to pivot     for int i 0  i lt list size    i             if list get i  lt pivot               smallerNumberList add list get i                      else if list get i  gt pivot               greaterNumberList add list get i                      else                Do nothing                        If smallerNumberList size is greater than nthSmallest value  nthSmallest number must be in this list      if nthSmallest  lt  smallerNumberList size             return quickSelect smallerNumberList  nthSmallest               If nthSmallest is greater than   list size   - greaterNumberList size      nthSmallest number must be in this list       The step is bit tricky  If confusing  please see the above loop once again for clarification      else if nthSmallest  gt   list size   - greaterNumberList size                nthSmallest will have to be changed here    list size   - greaterNumberList size     elements are already in            smallerNumberList         nthSmallest   nthSmallest -  list size   - greaterNumberList size             return quickSelect greaterNumberList nthSmallest             else          return pivot

User · Answer

There is also one algorithm  that outperforms quickselect algorithm  It s called Floyd-Rivets  FR  algorithm   Original article  https   doi org 10 1145 360680 360694  Downloadable version  http   citeseerx ist psu edu viewdoc download doi 10 1 1 309 7108 amp rep rep1 amp type pdf  Wikipedia article https   en wikipedia org wiki Floyd E2 80 93Rivest algorithm   I tried to implement quickselect and FR algorithm in C    Also I compared them to the standard C   library implementations std  nth element  which is basically introselect hybrid of quickselect and heapselect   The result was  quickselect and nth element ran comparably on average  but FR algorithm ran approx  twice as fast compared to them    Sample code that I used for FR algorithm   template  lt typename T gt  T FRselect std  vector lt T gt  amp  data  const size t amp  n        if  n    0          return   std  min element data begin    data end          else if  n    data size   - 1          return   std  max element data begin    data end          else         return  FRselect data  0  data size   - 1  n      template  lt typename T gt  T  FRselect std  vector lt T gt  amp  data  const size t amp  left  const size t amp  right  const size t amp  n        size t leftIdx   left      size t rightIdx   right       while  rightIdx  gt  leftIdx                if  rightIdx - leftIdx  gt  600                        size t range   rightIdx - leftIdx   1              long long i   n -  long long leftIdx   1              long long z   log range               long long s   0 5   exp 2   z   3               long long sd   0 5   sqrt z   s    range - s    range    sgn i -  long long range   2                size t newLeft   fmax leftIdx  n - i   s   range   sd               size t newRight   fmin rightIdx  n    range - i    s   range   sd                 FRselect data  newLeft  newRight  n                     T t   data n           size t i   leftIdx          size t j   rightIdx             arrange pivot and right index         std  swap data leftIdx   data n            if  data rightIdx   gt  t              std  swap data rightIdx   data leftIdx             while  i  lt  j                        std  swap data i   data j                  i  --j              while  data i   lt  t    i              while  data j   gt  t  --j                     if  data leftIdx     t              std  swap data leftIdx   data j            else                         j              std  swap data j   data rightIdx                         adjust left and right towards the boundaries of the subset            containing the  k - left   1 th smallest element         if  j  lt   n              leftIdx   j   1          if  n  lt   j              rightIdx   j - 1             return data leftIdx      template  lt typename T gt  int sgn T val        return  T 0   lt  val  -  val  lt  T 0

User · Answer

A Programmer s Companion to Algorithm Analysis gives a version that is O n   although the author states that the constant factor is so high  you d probably prefer the naive sort-the-list-then-select method   I answered the letter of your question

User · Answer

How about this kinda approach   Maintain a buffer of length k and a tmp max  getting tmp max is O k  and is done n times so something like O kn      Is it right or am i missing something    Although it doesn t beat average case of quickselect and worst case of median statistics method but its pretty easy to understand and implement

User · Answer

kth largest element means  we need to sort the array and then  count down from the end of array  For example  const array   2  32  12  3  78  99  898  8  1     we need to sort this  const sortedArray   1   2   3    8  12  32  78  99  898    5th largest element means from the end count down 5 elements which is 12  By default most languages implement quick sort or merge sort because they are the most optimized sorts  I solve this problem with the quick sort  Quick sort sorts the array in place  it does not give us back a new array and like merge sort it is recursive  Downside of quick sort  in worst case scenario  its time complexity is O n  2   quot n square quot   Quick sort is divide-and-conquer algorithm which is a problem is solved by solving all of its smaller components  We choose the last element as the pivot element  Some algorithms choose the first item as pivot  some choose the last item when it starts   Pivot element is the partitioning element  this is our array  2  32  12  3  78  99  898  8  1  we use 2 pointers  i j starts from the first element   quot i quot  keeps track of where is the final place of pivot  i j 2   starting point   quot j quot  is going to scan the array  and compare each element to the pivot  If  quot j quot  is smaller than pivot  we will swap  quot i quot  and  quot j quot  and move  quot i quot  and  quot j quot  forward  When  quot j quot  reaches pivot  we swap  quot i quot  with pivot  In our example pivot is 1  1 is the smaller number   quot j quot  will reach the pivot 1 without swapping  quot i quot   quot j quot   Remember  quot i quot  is the placeholder for the pivot  So when  quot j quot  reaches pivot  1 and 2 will be swapped  The purpose of this operation to find all of elements that smaller than pivot to its left  Note that all the elements that are on the left of pivot is smaller than pivot  but left side is not sorted  Then we divide the array from the pivot into 2 sub arrays and recursively apply the quick sort  const quickSort   function  array  left  right         if left right  it means we have only one item  it is already sorted   if  left  lt  right        const partitionIndex   partition array  left  right       quickSort array  left  partitionIndex - 1        quickSort array  partitionIndex   1  right           With using  quot i quot  and  quot j quot  pointers  this is how we find the partitioning index const partition   function  array  left  right      const pivotElement   array right     let partitionIndex   left    for  let j   left  j  lt  right  j          if  array j   lt  pivotElement          swap array  partitionIndex  j         partitionIndex                   if none of the  quot j quot  values is smaller than pivot  when  quot j quot  reaches the pivot  we swap  quot i th quot  element with pivot   swap array  partitionIndex  right     return partitionIndex      this is a simple implementation of swap function  const swap   function  array  i  j      const temp   array i     array i    array j     array j    temp

User · Answer

If you want a true O n  algorithm  as opposed to O kn  or something like that  then you should use quickselect  it s basically quicksort where you throw out the partition that you re not interested in   My prof has a great writeup  with the runtime analysis   reference   The QuickSelect algorithm quickly finds the k-th smallest element of an unsorted array of n elements   It is a RandomizedAlgorithm  so we compute the worst-case expected running time   Here is the algorithm   QuickSelect A  k    let r be chosen uniformly at random in the range 1 to length A    let pivot   A r    let A1  A2 be new arrays     split into a pile A1 of small elements and A2 of big elements   for i   1 to n     if A i   lt  pivot then       append A i  to A1     else if A i   gt  pivot then       append A i  to A2     else         do nothing   end for   if k  lt   length A1         it s in the pile of small elements     return QuickSelect A1  k    else if k  gt  length A  - length A2        it s in the pile of big elements     return QuickSelect A2  k -  length A  - length A2     else       it s equal to the pivot     return pivot   What is the running time of this algorithm   If the adversary flips coins for us  we may find that the pivot is always the largest element and k is always 1  giving a running time of   T n    Theta n    T n-1    Theta n2   But if the choices are indeed random  the expected running time is given by  T n   lt   Theta n     1 n   i 1 to nT max i  n-i-1    where we are making the not entirely reasonable assumption that the recursion always lands in the larger of A1 or A2   Let s guess that T n   lt   an for some a   Then we get  T n     lt   cn    1 n   i 1 to nT max i-1  n-i      cn    1 n   i 1 to floor n 2  T n-i     1 n   i floor n 2  1 to n T i    lt   cn   2  1 n   i floor n 2  to n T i    lt   cn   2  1 n   i floor n 2  to n ai  and now somehow we have to get the horrendous sum on the right of the plus sign to absorb the cn on the left   If we just bound it as 2 1 n   i n 2 to n an  we get roughly 2 1 n  n 2 an   an   But this is too big - there s no room to squeeze in an extra cn   So let s expand the sum using the arithmetic series formula    i floor n 2  to n i       i 1 to n i -  i 1 to floor n 2  i      n n 1  2 - floor n 2  floor n 2  1  2     lt   n2 2 -  n 4 2 2       15 32 n2  where we take advantage of n being  sufficiently large  to replace the ugly floor n 2  factors with the much cleaner  and smaller  n 4   Now we can continue with  cn   2  1 n   i floor n 2  to n ai    lt   cn    2a n   15 32  n2    n  c    15 16 a    lt   an  provided a  gt  16c   This gives T n    O n    It s clearly Omega n   so we get T n    Theta n

User · Answer

You can do it in O n   kn    O n   for constant k  for time and O k  for space  by keeping track of the k largest elements you ve seen     For each element in the array you can scan the list of k largest and replace the smallest element with the new one if it is bigger   Warren s priority heap solution is neater though

User · Answer

Explanation of the median - of - medians algorithm to find the k-th largest integer out of n can be found here  http   cs indstate edu  spitla presentation pdf  Implementation in c   is below    include  lt iostream gt   include  lt vector gt   include  lt algorithm gt  using namespace std   int findMedian vector lt int gt  vec         Find median of a vector     int median      size t size   vec size        median   vec  size 2        return median     int findMedianOfMedians vector lt vector lt int gt   gt  values       vector lt int gt  medians       for  int i   0  i  lt  values size    i              int m   findMedian values i            medians push back m              return findMedian medians      void selectionByMedianOfMedians const vector lt int gt  values  int k         Divide the list into n 5 lists of 5 elements each     vector lt vector lt int gt   gt  vec2D       int count   0      while  count    values size              int countRow   0          vector lt int gt  row           while   countRow  lt  5   amp  amp   count  lt  values size                   row push back values count                count                countRow                      vec2D push back row              cout lt  lt endl lt  lt endl lt  lt  Printing 2D vector     lt  lt endl      for  int i   0  i  lt  vec2D size    i              for  int j   0  j  lt  vec2D i  size    j                  cout lt  lt vec2D i  j  lt  lt                        cout lt  lt endl            cout lt  lt endl         Calculating a new pivot for making splits     int m   findMedianOfMedians vec2D       cout lt  lt  Median of medians is     lt  lt m lt  lt endl         Partition the list into unique elements larger than  m   call this sublist L1  and       those smaller them  m   call this sublist L2      vector lt int gt  L1  L2       for  int i   0  i  lt  vec2D size    i              for  int j   0  j  lt  vec2D i  size    j                  if  vec2D i  j   gt  m                    L1 push back vec2D i  j                 else if  vec2D i  j   lt  m                   L2 push back vec2D i  j                                         Checking the splits as per the new pivot  m      cout lt  lt endl lt  lt  Printing L1     lt  lt endl      for  int i   0  i  lt  L1 size    i              cout lt  lt L1 i  lt  lt                 cout lt  lt endl lt  lt endl lt  lt  Printing L2     lt  lt endl      for  int i   0  i  lt  L2 size    i              cout lt  lt L2 i  lt  lt                   Recursive calls     if   k - 1     L1 size              cout lt  lt endl lt  lt endl lt  lt  Answer    lt  lt m       else if  k  lt   L1 size              return selectionByMedianOfMedians L1  k        else if  k  gt   L1 size     1            return selectionByMedianOfMedians L2  k-  int L1 size   -1             int main         int values      2  3  5  4  1  12  11  13  16  7  8  6  10  9  17  15  19  20  18  23  21  22  25  24  14        vector lt int gt  vec values  values   25        cout lt  lt  The given array is     lt  lt endl      for  int i   0  i  lt  vec size    i              cout lt  lt vec i  lt  lt                 selectionByMedianOfMedians vec  8        return 0

User · Answer

A Programmer s Companion to Algorithm Analysis gives a version that is O n   although the author states that the constant factor is so high  you d probably prefer the naive sort-the-list-then-select method   I answered the letter of your question

User · Answer

A quick Google on that   kth largest element array   returned this  http   discuss joelonsoftware com default asp interview 11 509587 17   Make one pass through tracking the three largest values so far       it was specifically for 3d largest   and this answer   Build a heap priority queue   O n  Pop top element   O log n  Pop top element   O log n  Pop top element   O log n   Total   O n    3 O log n    O n

User · Answer

This is an implementation in Javascript   If you release the constraint that you cannot modify the array  you can prevent the use of extra memory using two indexes to identify the  current partition   in classic quicksort style - http   www nczonline net blog 2012 11 27 computer-science-in-javascript-quicksort     function kthMax a  k       var size   a length       var pivot   a  parseInt Math random   size       Another choice could have been  size   2          Create an array with all element lower than the pivot and an array with all element higher than the pivot     var i  lowerArray       upperArray           for  i   0  i   lt  size  i             var current   a i            if  current  lt  pivot                lowerArray push current             else if  current  gt  pivot                upperArray push current                          Which one should I continue with      if k  lt   upperArray length              Upper         return kthMax upperArray  k         else           var newK   k -  size - lowerArray length            if  newK  gt  0                   Lower             return kthMax lowerArray  newK             else                 None     it s the current pivot              return pivot                           If you want to test how it perform  you can use this variation       function kthMax  a  k  logging             var comparisonCount   0    Number of comparison that the algorithm uses          var memoryCount   0        Number of integers in memory that the algorithm uses          var  log   logging            if k  lt  0    k  gt   a length                if   log  console log   k is out of range                 return false                             function  kthmax a  k                var size   a length               var pivot   a parseInt Math random   size                 if  log  console log  Inputs    a    size   size   k   k   pivot   pivot                    This should never happen  Just a nice check in this exercise                 if you are playing with the code to avoid never ending recursion                          if typeof pivot      undefined                      if   log  console log   Ops                         return false                               var i  lowerArray       upperArray                    for  i   0  i   lt  size  i                      var current   a i                    if  current  lt  pivot                         comparisonCount    1                       memoryCount                         lowerArray push current                      else if  current  gt  pivot                         comparisonCount    2                       memoryCount                         upperArray push current                                                  if  log  console log  Pivoting   lowerArray      pivot      upperArray                 if k  lt   upperArray length                     comparisonCount    1                   return  kthmax upperArray  k                  else if  k  gt  size - lowerArray length                     comparisonCount    2                   return  kthmax lowerArray  k -  size - lowerArray length                   else                    comparisonCount    2                   return pivot                                  BTW  this is the logic for kthMin if we want to implement that     -                         if k  lt   lowerArray length                     return kthMin lowerArray  k                  else if  k  gt  size - upperArray length                     return kthMin upperArray  k -  size - upperArray length                   else                   return pivot                                           var result    kthmax a  k            return  result  result  iterations  comparisonCount  memory  memoryCount            The rest of the code is just to create some playground         function getRandomArray  n           var ar               for  var i   0  l   n  i  lt  l  i                  ar push Math round Math random     l                      return ar               Create a random array of 50 numbers     var ar   getRandomArray  50        Now  run you tests a few time  Because of the Math random   it will produce every time different results       kthMax ar  2  true       kthMax ar  2       kthMax ar  2       kthMax ar  2       kthMax ar  2       kthMax ar  2       kthMax ar  34  true       kthMax ar  34       kthMax ar  34       kthMax ar  34       kthMax ar  34       kthMax ar  34     If you test it a few times you can see even empirically that the number of iterations is  on average  O n     constant   n and the value of k does not affect the algorithm

User · Answer

This is called finding the k-th order statistic  There s a very simple randomized algorithm  called quickselect  taking O n  average time  O n 2  worst case time  and a pretty complicated non-randomized algorithm  called introselect  taking O n  worst case time  There s some info on Wikipedia  but it s not very good   Everything you need is in these powerpoint slides  Just to extract the basic algorithm of the O n  worst-case algorithm  introselect    Select A n i       Divide input into  n 5  groups of size 5          Partition on median-of-medians        medians   array of each group   s median      pivot   Select medians   n 5    n 10       Left Array L and Right Array G   partition A  pivot          Find ith element in L  pivot  or G        k    L    1     If i   k  return pivot     If i  lt  k  return Select L  k-1  i      If i  gt  k  return Select G  n-k  i-k    It s also very nicely detailed in the Introduction to Algorithms book by Cormen et al

User · Answer

iterate through the list   if the current value is larger than the stored largest value  store it as the largest value and bump the 1-4 down and 5 drops off the list  If not compare it to number 2 and do the same thing   Repeat  checking it against all 5 stored values  this should do it in O n

User · Answer

Haskell Solution   kthElem index list   sort list    index  withShape                     withShape   x xs   y ys    x   withShape xs ys  sort             sort  x xs     sort ls  withShape  ls      x      sort rs  withShape  rs    where    ls   filter   lt   x     rs   filter   gt   x    This implements the median of median solutions by using the withShape method to discover the size of a partition without actually computing it

User · Answer

You do like quicksort   Pick an element at random and shove everything either higher or lower   At this point you ll know which element you actually picked  and if it is the kth element you re done  otherwise you repeat with the bin  higher or lower   that the kth element would fall in  Statistically speaking  the time it takes to find the kth element grows with n  O n

User · Answer

There is also Wirth s selection algorithm  which has a simpler implementation than QuickSelect  Wirth s selection algorithm is slower than QuickSelect  but with some improvements it becomes faster    In more detail  Using Vladimir Zabrodsky s MODIFIND optimization and the median-of-3 pivot selection and paying some attention to the final steps of the partitioning part of the algorithm  i ve came up with the following algorithm  imaginably named  LefSelect      define F SWAP a b    float temp  a   a   b   b  temp       Note  The code needs more than 2 elements to work float lefselect float a    const int n  const int k        int l 0  m   n-1  i l  j m      float x       while  l lt m            if  a k   lt  a i    F SWAP a i  a k            if  a j   lt  a i    F SWAP a i  a j            if  a j   lt  a k    F SWAP a k  a j             x a k           while  j gt k  amp  i lt k                do i    while  a i  lt x               do j--  while  a j  gt x                F SWAP a i  a j                      i    j--           if  j lt k                while  a i  lt x  i                l i  j m                    if  k lt i                while  x lt a j   j--              m j  i l                      return a k       In benchmarks that i did here  LefSelect is 20-30  faster than QuickSelect

User · Answer

Find the median of the array in linear time  then use partition procedure exactly as in quicksort to divide the array in two parts  values to the left of the median lesser   lt    than than median and to the right greater than       median  that too can be done in lineat time  now  go to that part of the array where kth element lies   Now recurrence becomes  T n    T n 2    cn  which gives me O  n  overal

User · Answer

Here is a C   implementation of Randomized QuickSelect  The idea is to randomly pick a pivot element  To implement randomized partition  we use a random function  rand   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     include lt iostream gt   include lt climits gt   include lt cstdlib gt  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  ALL ELEMENTS IN ARR   ARE DISTINCT int kthSmallest int arr    int l  int r  int k           If k is smaller than number of elements in array     if  k  gt  0  amp  amp  k  lt   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  gt  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  lt   r - 1  j                  if  arr j   lt   x    arr i  is bigger than arr j  so swap them                       swap  amp arr i    amp arr j                i                        swap  amp arr i    amp arr r       swap the pivot     return i        Picks a random pivot element between l and r and partitions    arr l  r  around the randomly picked element using partition   int randomPartition int arr    int l  int r        int n   r-l 1      int pivot   rand     n      swap  amp arr l   pivot    amp arr r        return partition arr  l  r         Driver program to test above methods int main         int arr      12  3  5  7  4  19  26       int n   sizeof arr  sizeof arr 0    k   3      cout  lt  lt   K th smallest element is    lt  lt  kthSmallest arr  0  n-1  k       return 0      The worst case time complexity of the above solution is still O n2  In worst case  the randomized function may always pick a corner element  The expected time complexity of above randomized QuickSelect is T n

User · Answer

You can do it in O n   kn    O n   for constant k  for time and O k  for space  by keeping track of the k largest elements you ve seen     For each element in the array you can scan the list of k largest and replace the smallest element with the new one if it is bigger   Warren s priority heap solution is neater though

User · Answer

What I would do is this   initialize empty doubly linked list l for each element e in array     if e larger than head l          make e the new head of l         if size l   gt  k             remove last element from l  the last element of l should now be the kth largest element   You can simply store pointers to the first and last element in the linked list  They only change when updates to the list are made   Update   initialize empty sorted tree l for each element e in array     if e between head l  and tail l          insert e into l    O log k          if size l   gt  k             remove last element from l  the last element of l should now be the kth largest element

User · Answer

Explanation of the median - of - medians algorithm to find the k-th largest integer out of n can be found here  http   cs indstate edu  spitla presentation pdf  Implementation in c   is below    include  lt iostream gt   include  lt vector gt   include  lt algorithm gt  using namespace std   int findMedian vector lt int gt  vec         Find median of a vector     int median      size t size   vec size        median   vec  size 2        return median     int findMedianOfMedians vector lt vector lt int gt   gt  values       vector lt int gt  medians       for  int i   0  i  lt  values size    i              int m   findMedian values i            medians push back m              return findMedian medians      void selectionByMedianOfMedians const vector lt int gt  values  int k         Divide the list into n 5 lists of 5 elements each     vector lt vector lt int gt   gt  vec2D       int count   0      while  count    values size              int countRow   0          vector lt int gt  row           while   countRow  lt  5   amp  amp   count  lt  values size                   row push back values count                count                countRow                      vec2D push back row              cout lt  lt endl lt  lt endl lt  lt  Printing 2D vector     lt  lt endl      for  int i   0  i  lt  vec2D size    i              for  int j   0  j  lt  vec2D i  size    j                  cout lt  lt vec2D i  j  lt  lt                        cout lt  lt endl            cout lt  lt endl         Calculating a new pivot for making splits     int m   findMedianOfMedians vec2D       cout lt  lt  Median of medians is     lt  lt m lt  lt endl         Partition the list into unique elements larger than  m   call this sublist L1  and       those smaller them  m   call this sublist L2      vector lt int gt  L1  L2       for  int i   0  i  lt  vec2D size    i              for  int j   0  j  lt  vec2D i  size    j                  if  vec2D i  j   gt  m                    L1 push back vec2D i  j                 else if  vec2D i  j   lt  m                   L2 push back vec2D i  j                                         Checking the splits as per the new pivot  m      cout lt  lt endl lt  lt  Printing L1     lt  lt endl      for  int i   0  i  lt  L1 size    i              cout lt  lt L1 i  lt  lt                 cout lt  lt endl lt  lt endl lt  lt  Printing L2     lt  lt endl      for  int i   0  i  lt  L2 size    i              cout lt  lt L2 i  lt  lt                   Recursive calls     if   k - 1     L1 size              cout lt  lt endl lt  lt endl lt  lt  Answer    lt  lt m       else if  k  lt   L1 size              return selectionByMedianOfMedians L1  k        else if  k  gt   L1 size     1            return selectionByMedianOfMedians L2  k-  int L1 size   -1             int main         int values      2  3  5  4  1  12  11  13  16  7  8  6  10  9  17  15  19  20  18  23  21  22  25  24  14        vector lt int gt  vec values  values   25        cout lt  lt  The given array is     lt  lt endl      for  int i   0  i  lt  vec size    i              cout lt  lt vec i  lt  lt                 selectionByMedianOfMedians vec  8        return 0

User · Answer

I came up with this algorithm and seems to be O n    Let s say k 3 and we want to find the 3rd largest item in the array  I would create three variables and compare each item of the array with the minimum of these three variables  If array item is greater than our minimum  we would replace the min variable with the item value  We continue the same thing until end of the array  The minimum of our three variables is the 3rd largest item in the array   define variables a 0  b 0  c 0 iterate through the array items     find minimum a b c     if item  gt  min then replace the min variable with item value     continue until end of array the minimum of a b c is our answer   And  to find Kth largest item we need K variables   Example   k 3    1 2 4 1 7 3 9 5 6 2 9 8   Final variable values   a 7  answer  b 8 c 9   Can someone please review this and let me know what I am missing

User · Answer

iterate through the list   if the current value is larger than the stored largest value  store it as the largest value and bump the 1-4 down and 5 drops off the list  If not compare it to number 2 and do the same thing   Repeat  checking it against all 5 stored values  this should do it in O n

User · Answer

Sexy quickselect in Python  def quickselect arr  k                k   1 returns first element in ascending order       can be easily modified to return first element in descending order              r   random randrange 0  len arr        a1    i for i in arr if i  lt  arr r      partition        a2    i for i in arr if i  gt  arr r        if k  lt   len a1           return quickselect a1  k      elif k  gt  len arr -len a2           return quickselect a2  k -  len arr  - len a2        else          return arr r

User · Answer

iterate through the list   if the current value is larger than the stored largest value  store it as the largest value and bump the 1-4 down and 5 drops off the list  If not compare it to number 2 and do the same thing   Repeat  checking it against all 5 stored values  this should do it in O n

User · Answer

Sexy quickselect in Python  def quickselect arr  k                k   1 returns first element in ascending order       can be easily modified to return first element in descending order              r   random randrange 0  len arr        a1    i for i in arr if i  lt  arr r      partition        a2    i for i in arr if i  gt  arr r        if k  lt   len a1           return quickselect a1  k      elif k  gt  len arr -len a2           return quickselect a2  k -  len arr  - len a2        else          return arr r

User · Answer

What I would do is this   initialize empty doubly linked list l for each element e in array     if e larger than head l          make e the new head of l         if size l   gt  k             remove last element from l  the last element of l should now be the kth largest element   You can simply store pointers to the first and last element in the linked list  They only change when updates to the list are made   Update   initialize empty sorted tree l for each element e in array     if e between head l  and tail l          insert e into l    O log k          if size l   gt  k             remove last element from l  the last element of l should now be the kth largest element

User · Answer

The C   standard library has almost exactly that function call nth element  although it does modify your data   It has expected linear run-time  O N   and it also does a partial sort   const int N        double a N           const int m           m  lt  N nth element  a  a   m  a   N      a m  contains the mth element in a

User · Answer

You can do it in O n   kn    O n   for constant k  for time and O k  for space  by keeping track of the k largest elements you ve seen     For each element in the array you can scan the list of k largest and replace the smallest element with the new one if it is bigger   Warren s priority heap solution is neater though

User · Answer

This is an implementation in Javascript   If you release the constraint that you cannot modify the array  you can prevent the use of extra memory using two indexes to identify the  current partition   in classic quicksort style - http   www nczonline net blog 2012 11 27 computer-science-in-javascript-quicksort     function kthMax a  k       var size   a length       var pivot   a  parseInt Math random   size       Another choice could have been  size   2          Create an array with all element lower than the pivot and an array with all element higher than the pivot     var i  lowerArray       upperArray           for  i   0  i   lt  size  i             var current   a i            if  current  lt  pivot                lowerArray push current             else if  current  gt  pivot                upperArray push current                          Which one should I continue with      if k  lt   upperArray length              Upper         return kthMax upperArray  k         else           var newK   k -  size - lowerArray length            if  newK  gt  0                   Lower             return kthMax lowerArray  newK             else                 None     it s the current pivot              return pivot                           If you want to test how it perform  you can use this variation       function kthMax  a  k  logging             var comparisonCount   0    Number of comparison that the algorithm uses          var memoryCount   0        Number of integers in memory that the algorithm uses          var  log   logging            if k  lt  0    k  gt   a length                if   log  console log   k is out of range                 return false                             function  kthmax a  k                var size   a length               var pivot   a parseInt Math random   size                 if  log  console log  Inputs    a    size   size   k   k   pivot   pivot                    This should never happen  Just a nice check in this exercise                 if you are playing with the code to avoid never ending recursion                          if typeof pivot      undefined                      if   log  console log   Ops                         return false                               var i  lowerArray       upperArray                    for  i   0  i   lt  size  i                      var current   a i                    if  current  lt  pivot                         comparisonCount    1                       memoryCount                         lowerArray push current                      else if  current  gt  pivot                         comparisonCount    2                       memoryCount                         upperArray push current                                                  if  log  console log  Pivoting   lowerArray      pivot      upperArray                 if k  lt   upperArray length                     comparisonCount    1                   return  kthmax upperArray  k                  else if  k  gt  size - lowerArray length                     comparisonCount    2                   return  kthmax lowerArray  k -  size - lowerArray length                   else                    comparisonCount    2                   return pivot                                  BTW  this is the logic for kthMin if we want to implement that     -                         if k  lt   lowerArray length                     return kthMin lowerArray  k                  else if  k  gt  size - upperArray length                     return kthMin upperArray  k -  size - upperArray length                   else                   return pivot                                           var result    kthmax a  k            return  result  result  iterations  comparisonCount  memory  memoryCount            The rest of the code is just to create some playground         function getRandomArray  n           var ar               for  var i   0  l   n  i  lt  l  i                  ar push Math round Math random     l                      return ar               Create a random array of 50 numbers     var ar   getRandomArray  50        Now  run you tests a few time  Because of the Math random   it will produce every time different results       kthMax ar  2  true       kthMax ar  2       kthMax ar  2       kthMax ar  2       kthMax ar  2       kthMax ar  2       kthMax ar  34  true       kthMax ar  34       kthMax ar  34       kthMax ar  34       kthMax ar  34       kthMax ar  34     If you test it a few times you can see even empirically that the number of iterations is  on average  O n     constant   n and the value of k does not affect the algorithm

[performance] How to find the kth largest element in an unsorted array of length n in O(n)?

Examples related to performance

Examples related to algorithm

Examples related to big-o