โปรแกรม C # เพื่อทำการเรียงลำดับด่วนโดยใช้ Recursion

Quick Sort คืออัลกอริธึมการเรียงลำดับที่ใช้วิธีการแบ่งและพิชิต ใช้องค์ประกอบเดือยและวางไว้ในตำแหน่งที่ถูกต้อง จากนั้นอาร์เรย์ทางด้านซ้ายและด้านขวาขององค์ประกอบ pivot จะถูกจัดเรียงอีกครั้งโดยใช้ Quick Sort นี้จะทำจนกว่าอาร์เรย์ทั้งหมดจะถูกจัดเรียง

โปรแกรมที่แสดง Quick Sort โดยใช้ Recursion ใน C# มีดังนี้ -

ตัวอย่าง

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] + " ");
         }
      }
   }
}

ผลลัพธ์

ผลลัพธ์ของโปรแกรมข้างต้นมีดังนี้

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

ตอนนี้เรามาทำความเข้าใจโปรแกรมข้างต้นกัน

ในฟังก์ชัน main() อันดับแรกจะแสดงอาร์เรย์เริ่มต้น จากนั้น ฟังก์ชัน quickSort() จะถูกเรียกให้ทำการเรียงลำดับอย่างรวดเร็วบนอาร์เรย์ ข้อมูลโค้ดสำหรับสิ่งนี้จะได้รับดังนี้ −

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);

ในฟังก์ชัน quickSort() องค์ประกอบ pivot จะถูกเลือกโดยการเรียกใช้ฟังก์ชัน Partition() จากนั้น quickSort() จะถูกเรียกอีกครั้งด้วยอาร์กิวเมนต์ที่ขึ้นอยู่กับค่าของ 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);
   }
}

ในฟังก์ชัน Partition() องค์ประกอบ pivot จะถูกเลือกเป็นองค์ประกอบด้านซ้ายสุดของอาร์เรย์ที่มีให้ จากนั้นจึงตั้งค่าเป็นตำแหน่งที่ถูกต้องในอาร์เรย์ ข้อมูลโค้ดที่แสดงขั้นตอนทั้งหมดสำหรับการดำเนินการนี้มีดังนี้

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;
   }
}