In n phần tử nhỏ nhất từ mảng theo thứ tự ban đầu

Cho mảng k phần tử, chương trình phải tìm n phần tử nhỏ nhất trong số chúng theo thứ tự xuất hiện.

Input : arr[] = {1, 2, 4, 3, 6, 7, 8}, k=3
Ouput : 1, 2, 3
Input k là 3 nghĩa là 3 phần tử nhỏ nhất trong tập hợp cần được hiển thị theo thứ tự ban đầu như 1 rồi 2 rồi 3

Thuật toán

START
Step 1 -> Khai báo biến int i, max, pos, j, k=4 và size cho kích thước mảng
Step 2 -> Vòng lặp For i=k và i<size và i++
  Set max = arr[k-1]
  pos = k-1
  Vòng lặp For j=k-2 và j>=0 và j--
    If arr[j]>max
      Set max = arr[j]
      Set pos = j
    End
  End
  IF max> arr[i]
    Set j = pos
    Vòng lặp While j < k-1
      Set arr[j] = arr[j+1]
      Set j++
    End
    Set arr[k-1] = arr[i]
  End IF
End
Step 3 -> Vòng lặp For i = 0 và i < k và i++
  Print arr[i]
STOP

Ví dụ

#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]);
  //Sử dụng insertion sort, bắt đầu từ 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];
    }
  }
  //In k phần tử đầu tiên
  for (i = 0; i < k; i++) {
    printf("%d ", arr[i]);
  }
  return 0;
}

Kết quả

Nếu chúng ta chạy chương trình trên thì nó sẽ tạo ra đầu ra sau.

5 3 1 2