指定された配列からn個の最小要素を元の順序で出力します

たとえばk個の要素の配列が与えられた場合、プログラムはそれらの中から出現順にn個の最小要素を見つける必要があります。

Input : arr[] = {1, 2, 4, 3, 6, 7, 8}, k=3
Ouput : 1, 2, 3
Input k is 3 it means 3 shortest elements among the set needs to be displayed in original order like 1 than 2 and than 3

アルゴリズム

START
Step 1 -> start variables as int i, max, pos, j, k=4 and size for array size
Step 2 -> Loop For i=k and i<size and i++
   Set max = arr[k-1]
   pos = k-1
   Loop For j=k-2 and j>=0 and j--
      If arr[j]>max
         Set max = arr[j]
         Set pos = j
      End
   End
   IF max> arr[i]
      Set j = pos
      Loop While j < k-1
         Set arr[j] = arr[j+1]
         Set j++
      End
      Set arr[k-1] = arr[i]
   End IF
End
Step 3 -> Loop For i = 0 and i < k and i++
   Print arr[i]
STOP

例

#include <stdio.h>
int main() {
   int arr[] = {5,8,3,1,2,9};
   int i, max, pos, j, k=4;
   int size = sizeof(arr)/sizeof(arr[0]);
   //Using insertion sort, Starting from k.
   for(i=k;i<size;i++){
      max = arr[k-1];
      pos = k-1;
      for(j=k-2;j>=0;j--) {
         if(arr[j]>max) {
            max = arr[j];
            pos = j;
         }
      }
      if ( max> arr[i] ) {
         j = pos;
         while( j < k-1 ) {
            arr[j] = arr[j+1];
            j++;
         }
         arr[k-1] = arr[i];
      }
   }
   //Printing first k elements
   for (i = 0; i < k; i++) {
      printf("%d ", arr[i]);
   }
   return 0;
}

出力

上記のプログラムを実行すると、次の出力が生成されます。

5 3 1 2