algorithm - Using Insertion Sort return in sorted order the k smallest elements of an array -

i'm prepping software developer job interviews , reviewing algorithm questions. can't figure out how modify insertion sort algorithm returns in sorted order k smallest elements of array of size n.

insertion sort algorithm

for = 1 n   j =   while j > 0 , a[j-1] > a[j]     swap a[j] , a[j-1]     j = j - 1 

adding loop end of algorithm first k elements doesn't count.

with normal insertion sort, loop start end, , each item moved until it's in place. insertion sort, still loop start end, if item you're on >= kth item, leave it; if less, move position k, move until it's in place.

for = 1 k   j =   while j > 1 , a[j-1] > a[j]     swap a[j] , a[j-1]     j = j - 1 

first k items sorted.

for = k + 1 n   if a[i] < a[k]     swap a[i] , a[k]     j = k     while j > 1 , a[j-1] > a[j]       swap a[j] , a[j-1]       j = j - 1