Find K Biggest
#include <stdio.h>
 
void k_biggest(int *list, int *new, int n, int k)
{
    int i, j, min;
    for (i = 0; i < k; i++)    // put first k item into new array
        new[i] = list[i];
 
    for (j = i; j < n; j++) {
        for (min = 0, i = 1; i < k; i++) {  // search the min value in new array
            if (new[i] < new[min])
                min = i;
        }
        if (list[j] > new[min])    // if new item larger than min item, replace min by it
            new[min] = list[j];
    }
}
 
int main()
{
    int list[15] = {30,1,4,5,2,5,8,0,13,25,6,26,88,3,97};
    int new[7];
    k_biggest(list, new, 15, 7);
    int i;
    for (i = 0; i < 7; i++)
        printf("%d ", new[i]);
}

Note:
1) It has time complexity O(k + (n-k)*k) = O((n-k)*k) in worst case, and O(k + k + (n-k)) = O(n) (need to do a little optimization).
2) A possible optimization is to use a Min Heap to maintain the new array. First, construct a min heap with the first k item, then do removemin() when min value is smaller for n-k time. Therefore, the time complexity is O(k + (n-k)*logk)
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License