Quick Sort Algorithm in C#

1. Introduction

Quick Sort is a divide-and-conquer sorting algorithm that works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

2. Implementation Steps

1. Choose a 'pivot' element from the array.

2. Partition the array such that:

- Elements less than the pivot are moved to its left.

- Elements greater than the pivot are moved to its right.

3. Recursively apply the above steps to the left and right sub-arrays.

4. When a sub-array contains one or zero element, it is considered sorted.

3. Implementation in C#

using System;
public class QuickSort {
    // This function takes last element as pivot, places the pivot element at its correct
    // position in sorted array, and places all smaller (smaller than pivot) to left of
    // pivot and all greater elements to right of pivot
    public static int Partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        // Index of smaller element
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            // If current element is smaller than or equal to pivot
            if (arr[j] <= pivot) {
                i++;
                // Swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // Swap arr[i+1] and arr[high] (or pivot)
        int swapTemp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = swapTemp;
        return i + 1;
    }
    // The main function that implements QuickSort
    public static void Sort(int[] arr, int low, int high) {
        if (low < high) {
            // Pi is partitioning index, arr[pi] is now at right place
            int pi = Partition(arr, low, high);
            // Recursively sort elements before partition and after partition
            Sort(arr, low, pi - 1);
            Sort(arr, pi + 1, high);
        }
    }
}
public class Program {
    public static void Main() {
        int[] arr = {10, 80, 30, 90, 40, 50, 70};
        Console.WriteLine("Unsorted array:");
        foreach (var item in arr) {
            Console.Write(item + " ");
        }
        QuickSort.Sort(arr, 0, arr.Length - 1);
        Console.WriteLine("\nSorted array:");
        foreach (var item in arr) {
            Console.Write(item + " ");
        }
    }
}

Output:

Unsorted array:
10 80 30 90 40 50 70
Sorted array:
10 30 40 50 70 80 90

Explanation:

1. QuickSort is a class that contains the logic for the sorting algorithm.

2. The Partition function is the core of the algorithm. It takes the last element as the pivot and partitions the specified portion of the array based on the pivot's value. After partitioning, the pivot will be in its sorted position.

3. The Sort function is a recursive function that sorts the left and right sub-arrays after the array has been partitioned.

4. The Program class contains the Main method which showcases the sorting of an integer array using the QuickSort class. The unsorted and sorted arrays are displayed.

5. Quick Sort, though very efficient with an average time complexity of O(n log n), can degrade to O(n^2) if the pivot elements aren't chosen wisely (i.e., always choosing the smallest or largest element as the pivot).