재귀를 사용하여 빠른 정렬을 수행하는 C# 프로그램

빠른 정렬은 분할 정복 방법을 사용하는 정렬 알고리즘입니다. 피벗 요소를 가져와 올바른 위치에 배치합니다. 그런 다음 피벗 요소의 왼쪽과 오른쪽에 있는 배열이 Quick Sort를 사용하여 다시 정렬됩니다. 이것은 전체 배열이 정렬될 때까지 수행됩니다.

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() 함수를 호출하여 피벗 요소를 선택합니다. 그런 다음, 피벗 값에 따라 달라지는 인수로 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;
   }
}