Understanding the Bubble Sort Algorithm

https://www.nilebits.com/blog/2023/10/understanding-the-bubble-sort-algorithm/

Computer science, programming and sorting is an essential operation.?This is the practice of placing items or data into an organized fashion usually based on increasing or decreasing values so that information can be easily navigated through and worked with.?Different sorting algorithms can be taken up, each providing one benefit or another.?The simplest sorting algorithm is known as the Bubble Sort.?This post is about exploring the bubble sort algorithm using C# code.

What is Bubble Sort?

Bubble Sort is a straightforward comparison-based sorting algorithm that 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. The algorithm is named because smaller or larger elements “bubble” to the top of the list as the sorting process progresses.

How Bubble Sort Works

1. Comparing Adjacent Elements: Bubble Sort starts by comparing the first two elements of the list.
2. Swapping if Necessary: If the first element is greater than the second element (for ascending order), they are swapped.
3. Moving to the Next Pair: The algorithm proceeds to compare the second and third elements, then the third and fourth, and so on.
4. Iterating Through the List: This process continues for multiple iterations until no more swaps are needed.
5. Termination: The algorithm terminates when no swaps are made in an entire pass through the list, indicating that the list is sorted.

To help you understand Bubble Sort better, let’s dive into some C# code examples.

Bubble Sort in C#

Let’s implement the Bubble Sort algorithm in C# using an array of integers.

using System;
class BubbleSort
{
    static void Main()
    {
        int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
        Console.WriteLine("Original array: ");
        PrintArray(arr);
        BubbleSortArray(arr);
        Console.WriteLine("\nSorted array: ");
        PrintArray(arr);
    }

    static void BubbleSortArray(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])
                {
                    // Swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    static void PrintArray(int[] arr)
    {
        foreach (var num in arr)
        {
            Console.Write(num + " ");
        }
    }
}        

In this example, we create an array arr of integers and then use the BubbleSortArray method to sort it. The PrintArray method is used to display the array before and after sorting.

Bubble Sort Visualization

To better understand the Bubble Sort algorithm, let’s visualize a pass through the array:

Original Array: [64, 34, 25, 12, 22, 11, 90]

• Pass 1:Comparing and swapping 64 and 34: [34, 64, 25, 12, 22, 11, 90]Comparing and swapping 64 and 25: [34, 25, 64, 12, 22, 11, 90]Comparing and swapping 64 and 12: [34, 25, 12, 64, 22, 11, 90]Comparing and swapping 64 and 22: [34, 25, 12, 22, 64, 11, 90]Comparing and swapping 64 and 11: [34, 25, 12, 22, 11, 64, 90]No more swaps needed in Pass 1.
• Pass 2:Comparing and swapping 34 and 25: [25, 34, 12, 22, 11, 64, 90]Comparing and swapping 34 and 12: [25, 12, 34, 22, 11, 64, 90]Comparing and swapping 34 and 22: [25, 12, 22, 34, 11, 64, 90]Comparing and swapping 34 and 11: [25, 12, 22, 11, 34, 64, 90]No more swaps needed in Pass 2.
• Pass 3:Comparing and swapping 25 and 12: [12, 25, 22, 11, 34, 64, 90]Comparing and swapping 25 and 22: [12, 22, 25, 11, 34, 64, 90]Comparing and swapping 25 and 11: [12, 22, 11, 25, 34, 64, 90]No more swaps needed in Pass 3.
• Pass 4:Comparing and swapping 22 and 11: [12, 11, 22, 25, 34, 64, 90]No more swaps needed in Pass 4.
• Pass 5:No swaps needed in Pass 5.
• Pass 6:No swaps needed in Pass 6.

The array is now sorted, and Bubble Sort terminates. The final sorted array is: [11, 12, 22, 25, 34, 64, 90].

Time Complexity

Bubble Sort has a time complexity of O(n^2) in the worst and average cases, making it inefficient for large datasets. However, it has a best-case time complexity of O(n) when the array is already sorted, as no swaps are needed.

Conclusion

One of the easiest examples of how to sort an information is Bubble Sort – it is easily comprehensible and easy to write. Nevertheless, it takes much time and is unsuitable for large datasets.?Mostly meant for school work and not good for production coding.

When compared to these efficient sorting algorithms like Quick Sort or Merge Sort, such kind of algorithms is better suited for real-world scenarios.?Learning Bubble sort is a good entry point for those looking to dive into sorting algorithms, with the potential to lead to deeper exploration of more complex sorting methods.

I’m sure this blog post on the Bubble Sort algorithm in C# has been helpful for you.?Feel free to ask me any question if you are still not clear about something.?Happy coding!

https://www.nilebits.com/blog/2023/10/understanding-the-bubble-sort-algorithm/