Algorithm to find k smallest numbers in an array in same order using O(1) auxiliary space

Question

For example if the array is arr[] = {4, 2, 6, 1, 5}, and k = 3, then the output should be 4 2 1.

Answer 1

It can be done in O(nk) steps and O(1) space.

Firstly, find the kth smallest number in kn steps: find the minimum; store it in a local variable min; then find the second smallest number, i.e. the smallest number that is greater than min; store it in min; and so on... repeat the process from i = 1 to k (each time it's a linear search through the array).

Having this value, browse through the array and print all elements that are smaller or equal to min. This final step is linear.

Care has to be taken if there are duplicate values in the array. In such a case we have to increment i several times if duplicate min values are found in one pass. Additionally, besides min variable we have to have a count variable, which is reset to zero with each iteration of the main loop, and is incremented each time a duplicate min number is found.

In the final scan through the array, we print all values smaller than min, and up to count values exactly min.

The algorithm in C would like this:

int min = MIN_VALUE, local_min;
int count;
int i, j;

i = 0;
while (i < k) {
  local_min = MAX_VALUE;
  count = 0;
  for (j = 0; j < n; j++) {
    if ((arr[j] > min || min == MIN_VALUE) && arr[j] < local_min) {
      local_min = arr[j];
      count = 1;
    }
    else if ((arr[j] > min || min == MIN_VALUE) && arr[j] == local_min) {
      count++;
    }
  }
  min = local_min;
  i += count;
}

if (i > k) {
  count = count - (i - k);
}

for (i = 0, j = 0; i < n; i++) {
  if (arr[i] < min) {
    print arr[i];
  }
  else if (arr[i] == min && j < count) {
    print arr[i];
    j++;
  }
}

where MIN_VALUE and MAX_VALUE can be some arbitrary values such as -infinity and +infinity, or MIN_VALUE = arr[0] and MAX_VALUE is set to be maximal value in arr (the max can be found in an additional initial loop).