K smallest elements in same order using O(1) extra space

Software Development
#1

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