Problem Description
Given an integer array, write a program to sort the array in ascending order.
The program must be implemented using the ‘bubble sort’ algorithm.
Bubble sort works by comparing two adjacent elements and swapping them if they are in the wrong order.
This process is repeated until the end of the array, and at the end of one complete pass, the last element will be in sorted order.
Therefore, the number of sorted elements increases by one after each pass.
Input Format
The first line contains the integer N (1 ≤ N ≤ 100).
The second line contains N integers, with each integer in the range of -1000 ≤ A[i] ≤ 1000.
Output Format
Print the sorted N integers, separated by spaces, on a single line.
Example Input
5
5 3 2 4 1
Example Output
1 2 3 4 5
Introduction to Bubble Sort Algorithm
The bubble sort algorithm is one of the simplest sorting algorithms, which works by iteratively traversing the array
and comparing adjacent elements to sort them. This algorithm is not efficient and has a time complexity of O(N²),
but it is often used for educational purposes due to its simplicity in understanding and implementation.
The basic operation of bubble sort is as follows:
- Start from the first element of the array and compare two adjacent elements.
- If the first element is greater than the second, swap their positions.
- Repeat this process until the end of the array.
- After one complete pass, the last element is sorted, so decrease the size of the array by one and repeat.
- Continue this process until the entire array is sorted.
C# Bubble Sort Implementation
Now, let’s implement bubble sort in C# based on the algorithm above.
Below is the C# code that implements bubble sort.
using System;
class Program
{
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])
{
// Swap arr[j] and arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
static void Main(string[] args)
{
int n = int.Parse(Console.ReadLine());
int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
BubbleSort(arr);
Console.WriteLine(string.Join(" ", arr));
}
}
In the code above, we define the BubbleSort method which sorts the array.
This method uses two nested loops to compare and swap adjacent elements to sort the array.
The Main method takes the size and elements of the array as input from the user,
calls the BubbleSort method to sort the array, and then prints the result.
Code Execution and Testing
To run the code, you need to use an IDE or editor that supports C#.
You can use IDEs like Visual Studio or Visual Studio Code.
After entering the code, click the Run button or press Ctrl + F5 to execute.
After execution, if you input integers as in the example, the sorted result in ascending order will be output.
It is advisable to use various test cases to verify the accuracy of the algorithm.
Test Cases
-
Input:
3 5 1 2
Output:
1 2 5
-
Input:
4 3 3 2 1
Output:
1 2 3 3
-
Input:
5 -1 -2 0 2 1
Output:
-2 -1 0 1 2
Pros and Cons of the Bubble Sort Algorithm
The bubble sort algorithm is simple and easy to understand, but it is inefficient for larger data sets.
Below are the pros and cons of bubble sort.
Pros
- Implementation is simple and intuitive.
- It is easy to visually verify the sorting process.
- Does not require additional memory. (in-place sorting)
Cons
- The time complexity is O(N²), making it inefficient. It is not advisable to use for large datasets.
- In the worst case, it may require comparing all N elements, which can take a long time.
- Since it continuously modifies the array while sorting, stability may decrease.
Considering the above pros and cons, bubble sort is mainly used for educational purposes, and in practice,
it is common to use more efficient sorting algorithms like quick sort or merge sort.
Conclusion
Today, we implemented a bubble sort program in C# and examined the process in detail.
While it is a simple algorithm, it is very useful for understanding the basics of sorting algorithms.
I hope it helps to solidify your understanding and improve your programming skills as you learn various sorting algorithms.