Hello Everyone,
You are given an array of n-elements you have to find k smallest elements from the array but they must be in the same order as they are in given array and we are allowed to use only O(1) extra space.
Examples:
Input : arr[] = {4, 2, 6, 1, 5},
k = 3
Output : 4 2 1
Explanation : 1, 2 and 4 are three smallest
numbers and 4 2 1 is their order in given array
Input : arr[] = {4, 12, 16, 21, 25},
k = 3
Output : 4 12 16
Explanation : 4, 12 and 16 are 3 smallest numbers
and 4 12 16 is their order in given array
The idea is to move k minimum elements to beginning in same order. To do this, we start from (k+1)-th element and move till end. For every array element, we replace the largest element of first k elements with the current element if current element is smaller than the largest. To keep the order, we use insertion sort idea.
// CPP for printing smallest k numbers in order
#include <algorithm>
#include <iostream>
using
namespace
std;
// Function to print smallest k numbers
// in arr[0..n-1]
void
printSmall(
int
arr[],
int
n,
int
k)
{
// For each arr[i] find whether
// it is a part of n-smallest
// with insertion sort concept
for
(
int
i = k; i < n; ++i)
{
// find largest from first k-elements
int
max_var = arr[k-1];
int
pos = k-1;
for
(
int
j=k-2; j>=0; j--)
{
if
(arr[j] > max_var)
{
max_var = arr[j];
pos = j;
}
}
// if largest is greater than arr[i]
// shift all element one place left
if
(max_var > arr[i])
{
int
j = pos;
while
(j < k-1)
{
arr[j] = arr[j+1];
j++;
}
// make arr[k-1] = arr[i]
arr[k-1] = arr[i];
}
}
// print result
for
(
int
i=0; i<k; i++)
cout << arr[i] <<
" "
;
}
// Driver program
int
main()
{
int
arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
int
n =
sizeof
(arr) /
sizeof
(arr[0]);
int
k = 5;
printSmall(arr, n, k);
return
0;
}
Output :
1 3 4 2 0