C# - Sorting Algorithms(Bubble Sort, Insertion Sort)

A sorting algorithm is a well-defined and step-by-step procedure for rearranging elements in a list or array in a specific order, often numerical or lexicographical (alphabetical) order. Sorting algorithms are tools that help arrange information so it's easier to find and retrieve quickly. There are various sorting algorithms, each with its own approach and characteristics, but they all share the common goal of arranging elements in a specified order.

Let's examine two sorting methods that people often use: Bubble Sort and Insertion Sort.

1. Bubble Sort:

Bubble Sort is a simple comparison-based sorting algorithm. It repeatedly steps through the list to be sorted, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Algorithm Steps:

1. Compare the first two elements of the array. If the first element is greater than the second element, swap them.
2. Move to the next pair of adjacent elements and repeat step 1 until the end of the array is reached.
3. Repeat the above steps for the remaining elements in the array, excluding the last sorted element in each pass.
4. The largest element in the unsorted part of the array "bubbles" to the end in each pass.
5. Continue until the entire array is sorted.

Here's a C# implementation of Bubble Sort:

using System;

class Program
{
    public static void BubbleSort(int[] arr)
    {
        int n = arr.Length;
        bool swapped;

        for (int i = 0; i < n - 1; i++)
        {
            swapped = false;

            for (int j = 0; j < n - i - 1; j++)
            {
                if (arr[j] > arr[j + 1])
                {
                    // Swap arr[j] and arr[j + 1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }

            // If no two elements were swapped in the inner loop, the array is already sorted.
            if (!swapped)
                break;
        }
    }

    static void Main()
    {
        int[] arr = { 64, 34, 25, 12, 22, 11, 90 };

        Console.WriteLine("Original Array:");
        foreach (int num in arr)
        {
            Console.Write(num + " ");
        }

        Console.WriteLine("\n\nSorting the Array using Bubble Sort...\n");

        BubbleSort(arr);

        Console.WriteLine("Sorted Array:");
        foreach (int num in arr)
        {
            Console.Write(num + " ");
        }

        Console.WriteLine("\n");
    }
}

Explanation

1. The program starts with an unsorted array arr containing integers.
2. The BubbleSort method implements the bubble sort algorithm to sort the array in ascending order. It iterates through the array, comparing adjacent elements and swapping them if they are in the wrong order. This process continues until no more swaps are needed.
3. In the Main method, the original array is displayed using a foreach loop, showing the initial order of elements.
4. After calling BubbleSort(arr), the array is sorted using the bubble sort algorithm.
5. Finally, the sorted array is displayed again, demonstrating that the elements are now in ascending order.

The output of the program will show the original array, a message indicating that the array is being sorted using the bubble sort algorithm, and the sorted array.

Sample Output

Original Array:
64 34 25 12 22 11 90 

Sorting the Array using Bubble Sort...

Sorted Array:
11 12 22 25 34 64 90 

The output demonstrates that the bubble sort algorithm successfully sorts the original array in ascending order.

2. Insertion Sort:

Insertion Sort is another comparison-based sorting algorithm. It builds the final sorted array one element at a time, shifting elements that are greater than the current element to the right.

Algorithm Steps:

1. Consider the first element of the array as sorted.
2. Take the next element and insert it into the correct position in the already sorted portion of the array.
3. Repeat step 2 for all elements in the array.

Here's a C# implementation of Insertion Sort:

using System;

class Program
{
    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;

            // Move elements that are greater than the key to one position ahead of their current position
            while (j >= 0 && arr[j] > key)
            {
                arr[j + 1] = arr[j];
                j--;
            }

            // Insert the key into its correct position
            arr[j + 1] = key;
        }
    }

    static void Main()
    {
        int[] arr = { 64, 34, 25, 12, 22, 11, 90 };

        Console.WriteLine("Original Array:");
        foreach (int num in arr)
        {
            Console.Write(num + " ");
        }

        Console.WriteLine("\n\nSorting the Array using Insertion Sort...\n");

        InsertionSort(arr);

        Console.WriteLine("Sorted Array:");
        foreach (int num in arr)
        {
            Console.Write(num + " ");
        }

        Console.WriteLine("\n");
    }
}

Explanation:

1. The InsertionSort method takes an array of integers as input and sorts it in ascending order using the Insertion Sort algorithm.
2. In the Main method, an unsorted array arr containing integers is created.
3. The original array is displayed using a foreach loop, showing the initial order of elements.
4. After calling InsertionSort(arr), the array is sorted using the Insertion Sort algorithm.
5. Finally, the sorted array is displayed again, showing that the elements are now in ascending order.

The output of the program will display the original array, a message indicating that the array is being sorted using the Insertion Sort algorithm, and the sorted array.

Sample Output

Original Array:
64 34 25 12 22 11 90 

Sorting the Array using Insertion Sort...

Sorted Array:
11 12 22 25 34 64 90 

This output demonstrates that the Insertion Sort algorithm successfully sorts the original array in ascending order.

Bubble Sort and Insertion Sort are basic methods to put things in order, and they work well when you have only a few things to sort or when the things are almost in order already. But when you need to sort a lot of things, it's better to use faster methods like Merge Sort, Quick Sort, or Heap Sort.