再帰を使用してクイックソートを実行するC＃プログラム

クイックソートは、分割統治法を使用するソートアルゴリズムです。ピボット要素を受け取り、正しい位置に配置します。次に、ピボット要素の左右の配列がクイックソートを使用して再度ソートされます。これは、配列全体がソートされるまで行われます。

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（）では、Partition（）関数を呼び出してピボット要素を選択します。次に、pivotの値に依存する引数を使用してquickSort（）が再度呼び出されます。このためのコードスニペットは次のように与えられます-

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（）関数では、ピボット要素が提供された配列の左端の要素として選択され、配列内の正しい位置に設定されます。このためのすべての手順を示すコードスニペットは次のとおりです。

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