CODEWITHSUNDEEP
arraysalgorithmselection
Jessica
Jessica

Reputation: 381

Algorithm to find k smallest numbers in array of n items

I'm trying to write an algorithm which can print the k smallest numbers in an n-size-array in O(n) time, but I cannot reduce the time complexity to n. How can I do this?

Upvotes: 38

Views: 86243

Answers (14)

nisetama
nisetama

Reputation: 8943

This is close to O(n) when the value of k is small relative to n, and this works when the array has duplicated elements:

a=[1,1,13,8,10,5,17,1,2,12,3,15,7,16,14,20,18,19,4,9,6,11]
k=5
n=a.length

outmax=NaN
out=[]

for(i=0;i<n;i++){
  if(i<k||a[i]<outmax){
    insertat=k-1
    for(j=0;j<k-1;j++)if(a[i]<out[j]||j==i){insertat=j;break}
    for(j=k-1;j>insertat;j--)out[j]=out[j-1]
    out[insertat]=a[i]
    outmax=out[k-1]
  }
}

console.log(out)

Upvotes: 0

Chet
Chet

Reputation: 22105

I've done this in an interview before, and one of the most elegant/efficient ways to do this is

O(n log k). 
with space: O(k) (thanks, @Nzbuu)

Basically you're going to use a max-heap of size limited to k. For each item in the array, check to see if it's smaller than the max (only O(1)). If it is, remove the max and put that in the heap (O(log k)). If its bigger, go to the next item.

Of course, the heap doesn't yield a sorted list of k items, but that can be done in O(k log k) which is easy.

Similarly, you can do the same for finding the largest k items, in which case you would use a min-heap.

Upvotes: 60

Sakib malik
Sakib malik

Reputation: 1

This is a slight variation in the recursion's base condition, in the selection algorithm ,to return pointer to the dynamic array containing all the first k smallest elements in random order , it is O(n).

void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int *A, int left, int right){
int pivot = A[right], i = left, x;

for (x = left; x < right; x++){
    if (A[x] < pivot){
        swap(&A[i], &A[x]);
        i++;
    }
}

swap(&A[i], &A[right]);
return i;
}


 int* quickselect(int *A, int left, int right, int k){

//p is position of pivot in the partitioned array
int p = partition(A, left, right);

//k equals pivot got lucky
if (p == k-1){
    int*temp = malloc((k)*sizeof(int));
    for(int i=left;i<=k-1;++i){
        temp[i]=A[i];
    }
    return temp;
}
//k less than pivot
else if (k - 1 < p){
    return quickselect(A, left, p - 1, k);
}
//k greater than pivot
else{
    return quickselect(A, p + 1, right, k);
}

}

Upvotes: 0

Aaron Parry
Aaron Parry

Reputation: 51

This can be done in O(n) time using O(n) space I believe. As was mentioned you can use Hoares algorithm, or a variation of quickselect.

Basically you run Quicksort on the array, but run only on the side of the partition needed to ensure that there are K or K-1 larger elements than the pivot (you can either include lr exclude the pivot). If the list does not need to be sorted, then, you can just print the remaineder of the array from the pivot. Since quicksort can be done in place, this takes O(n) space, and since you are halfing the portion of the array (on average) that you check each time is takes O(2n) == O(n) time

Upvotes: 1

paparazzo
paparazzo

Reputation: 45106

I know not exactly what you are looking for but pretty simple O(n * k) time and O(k) space. This is the biggest K so would need to flop it around.

For the brute for min of k (result) can substitute a heap

private int[] FindKBiggestNumbersM(int[] testArray, int k)
{
    int[] result = new int[k];
    int indexMin = 0;
    result[indexMin] = testArray[0];
    int min = result[indexMin];

    for (int i = 1; i < testArray.Length; i++)
    {
        if(i < k)
        {
            result[i] = testArray[i];
            if (result[i] < min)
            {
                min = result[i];
                indexMin = i;
            }
        }
        else if (testArray[i] > min)
        {
            result[indexMin] = testArray[i];
            min = result[indexMin];
            for (int r = 0; r < k; r++)
            {
                if (result[r] < min)
                {
                    min = result[r];
                    indexMin = r;
                }
            }
        }
    }
    return result;
}

Upvotes: 1

Neel Shah
Neel Shah

Reputation: 349

Another Technique- Use QuickSelect Algorithm and the result would be all the elements to the left of the returned result. The average time complexity would be O(n) and in worst case it would be O(n^2). The space complexity would be O(1).

Upvotes: 1

sapy
sapy

Reputation: 9602

Best possible solution to the problem is as follows.Use Quick sort to find pivots and discard the part where this kth element doesn't lie, and recursively find the next pivot. (It's kth Max finder , You need to change the if else condition to make it kth Min Finder) .Here is the JavaScript code- 

  // Complexity is O(n log(n))
  var source = [9, 2, 7, 11, 1, 3, 14, 22];

  var kthMax = function(minInd, MaxInd, kth) {
      // pivotInd stores the pivot position 
      // for current iteration
      var temp, pivotInd = minInd;
      if (minInd >= MaxInd) {
        return source[pivotInd];
      }

      for (var i = minInd; i < MaxInd; i++) {
        //If an element is greater than chosen pivot (i.e. last element)
        //Swap it with pivotPointer element. then increase ponter
        if (source[i] > source[MaxInd]) {
          temp = source[i];
          source[i] = source[pivotInd];
          source[pivotInd] = temp;
          pivotInd++;
        }
      }
      // we have found position for pivot elem. 
      // swap it to that position place .
      temp = source[pivotInd];
      source[pivotInd] = source[MaxInd];
      source[MaxInd] = temp;

      // Only try to sort the part in which kth index lies.
      if (kth > pivotInd) {
        return kthMax(pivotInd + 1, MaxInd, kth);
      } else if (kth < pivotInd) {
        return kthMax(minInd, pivotInd - 1, kth);
      } else {
        return source[pivotInd];
      }

    }
    // last argument is kth-1 , so if give 2 it will give you,
    // 3rd max which is 11

  console.log(kthMax(0, source.length - 1, 2));

Upvotes: 1

David K
David K

Reputation: 3132

It is possible to find the k smallest of n elements in O(n) time (by which I mean true O(n) time, not O(n + some function of k)). Refer to the Wikipedia article "Selection algorithm", especially the subsections on "unordered partial sorting" and "median selection as pivot strategy", and also to the article "Median of medians" for the essential piece that makes this O(n).

Upvotes: 2

Mirac Suzgun
Mirac Suzgun

Reputation: 155

As mentioned, there are two ways to accomplish such task:

1) You can sort the whole array of n elements with quicksort, heapsort or any O (n log n) sorting algorithm you want, and then pick the m smallest values in your array. This method will work in O(n log n).

2) You can use selection algorithm to fink m smallest elements in your array. It will take O(n) time to find the kth smallest value, since you will iterate this algorithm m times, the overall time will be m x O(n) = O(n) .

Upvotes: 1

sudeepdino008
sudeepdino008

Reputation: 3364

This can be done in expected linear time(O(n)). First find the kth smallest element of the array (using pivot partition method for finding kth order statistic) and then simply iterate through the loop to check which elements are less than the kth smallest element. Note that this works correctly only for distinct element.

Here is the code in c:

    /*find the k smallest elements of an array in O(n) time. Using the Kth order 
statistic-random pivoting algorithm to find the kth smallest element and then looping 
through the array to find the elements smaller than kth smallest element.Assuming 
distinct elements*/


    #include <stdio.h>
    #include <math.h>
    #include <time.h>
    #define SIZE 10
    #define swap(X,Y) {int temp=X; X=Y; Y=temp;}


    int partition(int array[], int start, int end)
    {
        if(start==end)
            return start;
        if(start>end)
            return -1;
        int pos=end+1,j;
        for(j=start+1;j<=end;j++)
        {       
            if(array[j]<=array[start] && pos!=end+1)
            {
                swap(array[j],array[pos]);
                pos++;
            }
            else if(pos==end+1 && array[j]>array[start])
                pos=j;
        }
        pos--;
        swap(array[start], array[pos]);
        return pos;
    }

    int order_statistic(int array[], int start, int end, int k)
    {
        if(start>end || (end-start+1)<k)
            return -1;                   //return -1 
        int pivot=rand()%(end-start+1)+start, position, p;
        swap(array[pivot], array[start]);
        position=partition(array, start, end);
        p=position;
        position=position-start+1;                  //size of left partition
        if(k==position)
            return array[p];
        else if(k<position)
            return order_statistic(array, start,p-1,k);
        else
            return order_statistic(array,p+1,end,k-position);
    }


    void main()
    {
        srand((unsigned int)time(NULL));
        int i, array[SIZE],k;
        printf("Printing the array...\n");
        for(i=0;i<SIZE;i++)
            array[i]=abs(rand()%100), printf("%d ",array[i]);
        printf("\n\nk=");
        scanf("%d",&k);
        int k_small=order_statistic(array,0,SIZE-1,k);
        printf("\n\n");
        if(k_small==-1)
        {
            printf("Not possible\n");
            return ;
        }
        printf("\nk smallest elements...\n");
        for(i=0;i<SIZE;i++)
        {
            if(array[i]<=k_small)
                printf("%d ",array[i]);
        }
    }

Upvotes: 2

Matthew
Matthew

Reputation: 2135

How about using a Heap to store the values. This cost is n when you go through each value in the array.

Then go through the Heap to get the smallest k values.

Runtime is O(n) + O(k) = O(n)

Of course, memory space is now O(n + n)

Upvotes: 0

amit
amit

Reputation: 178531

you will need to find the k'th smallest element using 'selection algorithm', which is O(n), and then iterate the array again and return each element which is smaller/equals it.
selection algorithm: http://en.wikipedia.org/wiki/Selection_algorithm
you will have to pay attention if you have repeats: you will need to make sure you are not returning more then k elements (it is possible if for instance you have 1,2,...,k,k,k,...)

EDIT :
the full algorithm, and returning a list, as requested: let the array be A

 1. find the k'th element in A using 'selection algorithm', let it be 'z'
 2. initialize an empty list 'L'
 3. initialize counter<-0
 4. for each element in A: 
 4.1. if element < z: 
   4.1.1. counter<-counter + 1 ; L.add(element)
 5. for each element in A:
 5.1. if element == z AND count < k:
   5.1.1. counter<-counter + 1 ; L.add(element)
 6. return L

note here that a 3rd iteration is required if your list might have duplicates. if it can't - it is needless, just change the condition in 4.1 to <=.
also note: L.add is inserting an element to a linked list and thus is O(1).

Upvotes: 27

Jerry Coffin
Jerry Coffin

Reputation: 490788

Assuming you're trying to show the K smallest numbers, you can use Hoare's Select algorithm to find the kth smallest number. That partitions the array into the smaller numbers, the kth number, and the larger numbers.

Upvotes: 5

Tamer Shlash
Tamer Shlash

Reputation: 9523

Just sort the array with Merge Sort and then print the first k number, it will take n*log2(n) in the worst case.

Upvotes: 0

Related Questions