C# : Most used Five Sorting Algorithms in .Net

 

Sorting algorithms are fundamental in computer science and play a crucial role in various applications. In this blog post, we'll delve into five popular sorting algorithms implemented in C#: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, and Quick Sort. We'll explore each algorithm's principles, implementation details, and performance characteristics.

1. Bubble Sort: Bubble Sort is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

Bubble Sort Implementation in C#:

public static void BubbleSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

2. Selection Sort: Selection Sort is an in-place comparison-based sorting algorithm that divides the input list into two parts: the sorted sublist and the unsorted sublist. It repeatedly selects the minimum element from the unsorted sublist and swaps it with the leftmost unsorted element.

Selection Sort Implementation in C#:

public static void SelectionSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 0; i < n - 1; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[minIndex])
            {
                minIndex = j;
            }
        }
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

3. Insertion Sort: Insertion Sort is a simple comparison-based sorting algorithm that builds the final sorted array one element at a time by repeatedly inserting the next element into its correct position in the sorted sublist.

Insertion Sort Implementation in C#:

public static void InsertionSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 1; i < n; i++)
    {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

4. Merge Sort: Merge Sort is a comparison-based sorting algorithm that divides the input array into two halves, recursively sorts each half, and then merges the sorted halves.

Merge Sort Implementation in C#:

public static void MergeSort(int[] arr)
{
    if (arr.Length <= 1)
        return;
    
    int mid = arr.Length / 2;
    int[] left = new int[mid];
    int[] right = new int[arr.Length - mid];
    Array.Copy(arr, 0, left, 0, mid);
    Array.Copy(arr, mid, right, 0, arr.Length - mid);

    MergeSort(left);
    MergeSort(right);
    Merge(left, right, arr);
}

private static void Merge(int[] left, int[] right, int[] arr)
{
    int i = 0, j = 0, k = 0;
    while (i < left.Length && j < right.Length)
    {
        if (left[i] <= right[j])
        {
            arr[k++] = left[i++];
        }
        else
        {
            arr[k++] = right[j++];
        }
    }
    while (i < left.Length)
    {
        arr[k++] = left[i++];
    }
    while (j < right.Length)
    {
        arr[k++] = right[j++];
    }
}

5. Quick Sort: Quick Sort is a comparison-based sorting algorithm that divides the input array into two partitions, recursively sorts each partition, and combines them.

Quick Sort Implementation in C#:

public static void QuickSort(int[] arr, int low, int high)
{
    if (low < high)
    {
        int pi = Partition(arr, low, high);
        QuickSort(arr, low, pi - 1);
        QuickSort(arr, pi + 1, high);
    }
}

private static int Partition(int[] arr, int low, int high)
{
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp1 = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp1;
    return i + 1;
}

Conclusion: These five sorting algorithms—Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, and Quick Sort—differ in their implementation strategies and performance characteristics. By understanding and implementing these algorithms in C#, developers can effectively tackle sorting tasks and optimize the performance of their applications.