Is it possible to sort only the first k elements from an array using insertion sort principles?
Because as the algorithm runs over the array, it will sort accordingly.
Since it is needed to check all the elements (to find out who is the smallest), it will eventually sort the whole thing.
Example:
Original array: {5, 3, 8, 1, 6, 2, 8, 3, 10}
Expected output for k = 3: {1, 2, 3, 5, 8, 6, 8, 3, 10} (Only the first k elements were sorted, the rest of the elements are not)
Such partial sorting is possible while resulting method looks like hybrid of selection sort - in the part of search of the smallest element in the tail of array, and insertion sort - in the part of shifting elements (but without comparisons). Sorting preserves order of tail elements (though it was not asked explicitly)
void ksort(int a[], int n, int k)
{ int i, j, t;
for (i = 0; i < k; i++)
{ int min = i;
for (j = i+1; j < n; j++)
if (a[j] < a[min]) min = j;
t = a[min];
for (j = min; j > i; j--)
a[j] = a[j-1];
a[i] = t;
}
}