We have covered almost all the data structures that are used in C# programming. Now, it's time to move forward and learn some algorithms that come in handy in numerous situations. As the introduction to data structures and algorithms states, an algorithm is a step-by-step solution to a recurring programming problem. In this and various upcoming articles, we will learn the most important and helpful algorithms we use in numerous situations while writing the solutions. So, let's begin with the sorting algorithms.
What are the Sorting Algorithms?
Generally, the word sorting refers to arranging the elements or contents in an ordered way for easy searching and access. The same goes for the sorting algorithms in programming. The sorting algorithms help you arrange the elements or data in an organized manner so it can be retrieved quickly and easily.
The order in which the items are arranged can be numerical (ascending or descending order), lexicographical (alphabetical), or any other property.
Characteristics of Sorting Algorithms
When we talk about sorting algorithms, we must keep the following characteristics in mind:
- In-Place and Out-of-Place Sorting: The in-place sorting algorithms sort the items within the same array or collection without occupying any auxiliary space. On the other hand, the out-of-place algorithms create a temporary copy of the data for sorting.
- Stable and Unstable Sorting: A stable algorithm maintains the relative position of the elements with equal values, whereas an unstable algorithm changes the relative order of the equal elements.
Bubble Sort Algorithm
The Bubble Sort is the most basic algorithm that arranges the items into ascending order by comparing and swapping the larger elements to the end of the list. It iterates through the list repeatedly until no more swaps are needed. At the end, it gives a sorted list with larger items at the end.
Demonstration
Let's understand the working of the Bubble Sort algorithm with an example:
Consider an array of integers [5, 3, 7, 2, 0]. The items are randomly placed in the array and must be sorted in ascending order. Let's break down this into steps:
Round 1:
• First, compare 5 and 3. They are in the wrong order, so the algorithm swaps them. Our array becomes [3, 5, 7, 2, 0].
• Compare 5 and 7. They are in the correct order, so leave them as is.
• Compare 7 and 2. They are in the wrong order, so the algorithm swaps them. Our array becomes [3, 5, 2, 7, 0].
• Compare 7 and 0. They are in the wrong order, so the algorithm swaps them. Our array becomes [3, 5, 2, 0, 7].
Round 2:
• Compare 3 and 5. They are in the correct order, so the array remains the same.
• Compare 5 and 2. They are in the wrong order, so swap. Array becomes [3, 2, 5, 0, 7].
• Compare 5 and 0. They are in the incorrect order, so swap. Array becomes [3, 2, 0, 5, 7].
• Compare 5 and 7. They are in the correct order, so the array remains the same.
Round 3:
• Compare 3 and 2. The order is incorrect, so swapping occurs. Our array becomes [2, 3, 0, 5, 7].
• Compare 3 and 0. Again, it's an incorrect order, so swap it. Array becomes [2, 0, 3, 5, 7].
• Compare 3 and 5. The order is correct, so no swapping.
Round 4:
• Compare 2 and 0. The order is incorrect, so swapping occurs. Array becomes [0, 2, 3, 5, 7].
• Compare 2 and 3. The order is correct, so no swapping. The array remains the same.
Round 5:
• Compare 0 and 2. Correct order, so no swapping.
• Compare 2 and 3. Correct order, so no swapping.
The array is considered sorted since no swaps are made in round 5.
Implementing Bubble Sort in C#
Now that you have understood how the bubble sort algorithm works, let's write a program to implement this functionality.
using System;
using System.Collections.Generic;
class Sorting {
public static void BubbleSort(int[] numbers)
{
int items = numbers.Length; //Getting the length of the array
bool swap; //Tracks the swapping
for(int i = 0; i< items-1; i++) //Looping through the array
{
swap = false;
for(int j = 0; j<items-i-1; j++) //For comparing the adjacent elements
{
if(numbers[j] > numbers[j + 1]) //if the element at j is bigger than the element at j+1
{
int temp = numbers[j]; //Store the larger element in temp variable
numbers[j] = numbers[j + 1]; //store the smaller element at j
numbers[j + 1] = temp; //Store the larger element at j+1
swap = true;
}
}
if (!swap) //if no swapping occurs
{
break; //break the loop
}
}
}
static void Main() {
int[] nums = {5, 3, 7, 2, 0};
Console.WriteLine("Array Before Sorting: ");
for(int i=0; i<nums.Length; i++)
{
Console.Write(nums[i] + " ");
}
Console.WriteLine("\nArray After Sorting:");
BubbleSort(nums);
for(int i=0; i<nums.Length; i++)
{
Console.Write(nums[i] + " ");
}
}
}
When to use the Bubble Sort Algorithm?
Due to its time complexity, the bubble sort algorithm is not considered an efficient solution for sorting large data sets. It is majorly used to explain the pedagogical tool to explain the sorting concepts to beginners. But we can still use it when:
- The data set is very small.
- The data does not need much sorting.
- Simplicity is more important than efficiency.
That being said, I'll wrap up this article. In the next article, we will learn about the Select Sort Algorithm and compare it with the Bubble Sort.