Difference Between Bubble Sort and Selection Sort
Sorting is a fundamental operation in computer science, and numerous algorithms are designed to accomplish this task efficiently.
Two popular sorting algorithms are Bubble Sort and Selection Sort. While both algorithms aim to arrange elements in ascending or descending order, they differ in their approach and performance characteristics.
In this article, we will explore the differences between Bubble Sort and Selection Sort, along with their implementation examples in the C programming language, including data types in C++.
Bubble Sort Algorithms
Bubble Sort is a simple comparison-based sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order.
It gets its name from how smaller elements "bubble" to the top of the list during each pass.
The basic idea behind Bubble Sort is to iterate through the entire list multiple times until it becomes sorted.
The algorithm works as follows:
Start at the beginning of the list.
Compare the first element with the second element. If they are out of order, swap them.
Move to the next pair of elements and repeat the comparison and swapping process.
Continue this process until reaching the end of the list.
Repeat the above steps for the remaining unsorted portion of the list.
Repeat the process until the entire list is sorted.
Bubble Sort has a time complexity of O(n^2) in the worst and average cases. It is not suitable for large datasets due to its slow performance.
However, Bubble Sort has the advantage of simplicity and ease of implementation.
Here's an example of an implementation Bubble Sort program in C:
#include <stdio.h>
void bubbleSort(int arr[], int n) {
int i, j, temp;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Selection Sort
Selection Sort is another comparison-based sorting algorithm that divides the input list into two parts: the sorted part at the left end and the unsorted part at the right end.
It repeatedly selects the smallest (or largest) element from the unsorted part and swaps it with the leftmost (or rightmost) element of the unsorted part. This process continues until the entire list becomes sorted.
The algorithm works as follows:
Find the minimum (or maximum) element in the unsorted part of the list.
Swap it with the leftmost (or rightmost) element of the unsorted part.
Move the boundary of the sorted part one element to the right (or left).
Repeat the above steps until the entire list is sorted.
Selection Sort also has a time complexity of O(n^2) in the worst and average cases. Although it performs better than Bubble Sort in practice, it is still inefficient for large datasets. However, Selection Sort requires fewer swaps compared to Bubble Sort.
Here's an example of a Selection Sort program implemented in C++:
#include <iostream>
template <typename T>
void selectionSort(T arr[], int n) {
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;
}
}
std::swap(arr[i], arr[minIndex]);
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
std::cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}
return 0;
}
In the above C++ example, the selection Sort function uses templates to support sorting arrays of different data types.
Data Types in C++
C++ is a statically typed programming language, meaning variables must be declared with their respective data types before use.
C++ provides several built-in data types that are used to define variables, specify the size of memory required, and determine the operations that can be performed on those variables. Here are some commonly used data types in C++:
Integer Types:
int: Represents signed integers, typically 4 bytes in size.
short: Represents signed short integers, usually 2 bytes in size.
long: Represents signed long integers, typically 4 bytes or 8 bytes in size.
long long: Represents signed long long integers, usually 8 bytes in size.
unsigned int: Represents unsigned integers with no negative values.
unsigned short: Represents unsigned short integers.
unsigned long: Represents unsigned long integers.
unsigned long long: Represents unsigned long long integers.
Floating-Point Types:
float: Represents single-precision floating-point numbers.
double: Represents double-precision floating-point numbers.
long double: Represents extended-precision floating-point numbers.
Character Types:
char: Represents a single character.
wchar_t: Represents a wide character.
char16_t: Represents a 16-bit Unicode character.
char32_t: Represents a 32-bit Unicode character.
Boolean Type:
- bool: Represents boolean values true or false.
Void Type:
- void: Represents the absence of type. It is commonly used as a return type for functions that do not return a value.
Enumeration Types:
- enum: Allows defining a set of named constants.
Derived Types:
array: Represents a fixed-size sequence of elements of the same type.
pointer: Represents a memory address.
reference: Represents an alias to an existing variable.
structure: Allows grouping related variables of different types into a single unit.
union: Allows storing different types of data in a single memory location.
class: Similar to a structure, but with additional features such as member functions and access control
User-Defined Types:
- C++ allows defining custom data types using the typedef or using keywords.
These are the basic data types in C++. Additionally, C++ supports type modifiers and qualifiers, such as const (to create constant variables), signed and unsigned (to specify signedness), and volatile (to indicate that a variable may change unexpectedly).
C++ also allows defining custom data types using classes and templates, enabling the creation of more complex and specialized types.
Understanding the different data types in C++ is crucial for proper variable declaration, memory allocation, and performing operations on variables based on their respective types.
Final Words
In conclusion, Bubble Sort and Selection Sort are simple sorting algorithms with their own characteristics. Bubble Sort repeatedly swaps adjacent elements, while Selection Sort selects the minimum or maximum element and places it in the sorted part of the list.