Chương trình C # để thực hiện sắp xếp nhanh bằng cách sử dụng Đệ quy

Quick Sort là một thuật toán sắp xếp sử dụng phương pháp chia để trị. Nó có một phần tử xoay và đặt nó vào đúng vị trí của nó. Sau đó, mảng ở bên trái và bên phải của phần tử trụ được sắp xếp lại bằng cách sử dụng Sắp xếp nhanh. Điều này được thực hiện cho đến khi toàn bộ mảng được sắp xếp.

Một chương trình thể hiện Sắp xếp nhanh bằng cách sử dụng Đệ quy trong C # được đưa ra như sau -

Ví dụ

using System;
namespace QuickSortDemo {
   class Example {
      static public int Partition(int[] arr, int left, int right) {
         int pivot;
         pivot = arr[left];
         while (true) {
            while (arr[left] < pivot) {
               left++;
            }
            while (arr[right] > pivot) {
               right--;
            }
            if (left < right) {
               int temp = arr[right];
               arr[right] = arr[left];
               arr[left] = temp;
            } else {
               return right;
            }
         }
      }
      static public void quickSort(int[] arr, int left, int right) {
         int pivot;
         if (left < right) {
            pivot = Partition(arr, left, right);
            if (pivot > 1) {
               quickSort(arr, left, pivot - 1);
            }  
            if (pivot + 1 < right) {
               quickSort(arr, pivot + 1, right);
            }
         }
      }
      static void Main(string[] args) {
         int[] arr = {67, 12, 95, 56, 85, 1, 100, 23, 60, 9};
         int n = 10, i;
         Console.WriteLine("Quick Sort");
         Console.Write("Initial array is: ");
         for (i = 0; i < n; i++) {
            Console.Write(arr[i] + " ");
         }
         quickSort(arr, 0, 9);
         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.

Quick Sort
Initial array is: 67 12 95 56 85 1 100 23 60 9
Sorted Array is: 1 9 12 23 56 60 67 85 95 100

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

Trong hàm main (), đầu tiên mảng ban đầu được hiển thị. Sau đó, hàm quickSort () được gọi để thực hiện sắp xếp nhanh trên mảng. Đoạn mã cho điều này được đưa ra như sau -

int[] arr = {67, 12, 95, 56, 85, 1, 100, 23, 60, 9};
int n = 10, i;
Console.WriteLine("Quick Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
   Console.Write(arr[i] + " ");
}
quickSort(arr, 0, 9);

Trong hàm quickSort (), một phần tử pivot được chọn bằng cách gọi hàm Partition (). Sau đó, quickSort () lại được gọi với các đối số phụ thuộc vào giá trị của pivot. Đoạn mã cho điều này được đưa ra như sau -

if (left < right) {
   pivot = Partition(arr, left, right);
   if (pivot > 1) {
      quickSort(arr, left, pivot - 1);
   }
   if (pivot + 1 < right) {
      quickSort(arr, pivot + 1, right);
   }
}

Trong hàm Partition (), phần tử pivot được chọn làm phần tử ngoài cùng bên trái của mảng được cung cấp và sau đó nó được đặt về vị trí chính xác của nó trong mảng. Đoạn mã thể hiện tất cả các bước cho việc này được đưa ra như sau.

int pivot;
pivot = arr[left];
while (true) {
   while (arr[left] < pivot) {
      left++;
   }
   while (arr[right] > pivot) {
      right--;
   }
   if (left < right) {
      int temp = arr[right];
      arr[right] = arr[left];
      arr[left] = temp;
   } else {
      return right;
   }
}