Sắp xếp chèn trong C #

Insertion Sort là một thuật toán sắp xếp lấy một phần tử tại một thời điểm và chèn nó vào đúng vị trí của nó trong mảng. Quá trình này được tiếp tục cho đến khi mảng được sắp xếp.

Một chương trình thể hiện sắp xếp chèn trong C # được đưa ra như sau.

Ví dụ

using System;
namespace InsertionSortDemo {
   class Example {
      static void Main(string[] args) {
         int[] arr = new int[10] { 23, 9, 85, 12, 99, 34, 60, 15, 100, 1 };
         int n = 10, i, j, val, flag;
         Console.WriteLine("Insertion Sort");
         Console.Write("Initial array is: ");
         for (i = 0; i < n; i++) {
            Console.Write(arr[i] + " ");
         }
         for (i = 1; i < n; i++) {
            val = arr[i];
            flag = 0;
            for (j = i - 1; j >= 0 && flag != 1; ) {
               if (val < arr[j]) {
                  arr[j + 1] = arr[j];
                  j--;
                  arr[j + 1] = val;
               }
               else flag = 1;
            }
         }
         Console.Write("\nSorted Array is: ");
         for (i = 0; i < n; i++) {
            Console.Write(arr[i] + " ");
         }
      }
   }
}

Đầu ra

Kết quả của chương trình trên như sau.

Insertion Sort
Initial array is: 23 9 85 12 99 34 60 15 100 1
Sorted Array is: 1 9 12 15 23 34 60 85 99 100

Bây giờ, chúng ta hãy hiểu chương trình trên.

Đầu tiên mảng được khởi tạo và giá trị của nó được in bằng vòng lặp for. Bạn có thể thấy điều này trong đoạn mã sau -

int[] arr = new int[10] { 23, 9, 85, 12, 99, 34, 60, 15, 100, 1 };
int n = 10, i, j, val, flag;
Console.WriteLine("Insertion Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
   Console.Write(arr[i] + " ");
}

Vòng lặp for lồng nhau được sử dụng cho quá trình sắp xếp thực tế. Trong mỗi lần vượt qua vòng lặp for bên ngoài, phần tử hiện tại được chèn vào đúng vị trí của nó trong mảng. Quá trình này tiếp tục cho đến khi mảng được sắp xếp. Điều này có thể được nhìn thấy trong đoạn mã sau.

for (i = 1; i < n; i++) {
   val = arr[i];
   flag = 0;
   for (j = i - 1; j >= 0 && flag != 1; ) {
      if (val < arr[j]) {
         arr[j + 1] = arr[j];
         j--;
         arr[j + 1] = val;
      } else flag = 1;
   }
}

Cuối cùng, mảng đã sắp xếp được hiển thị. Điều này có thể được nhìn thấy trong đoạn mã sau.

Console.Write("\nSorted Array is: ");
for (i = 0; i < n; i++) {
   Console.Write(arr[i] + " ");
}