Sorting algorithms with examples in C++
Sorting algorithms are procedures or sets of instructions used to organize a set of elements in a specific order. These algorithms are widely used in computer science and programming due to their importance for the efficiency and optimization of processes.
There are numerous sorting algorithms, each with its own characteristics and complexities. Below, we will mention some of the main sorting algorithms and implement them in the C++ language:
info The original list for all sorting algorithms will be the following: 54, 37, 81, 12, 95, 6, 23, 68, 47, 76, 29, 42
Bubble Sort
Bubble sort compares adjacent pairs of elements and swaps them if they are in the wrong order. It repeats this process until all elements are sorted.
IMPLEMENTATION IN C++
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int size) {
for (int i = 0; i < size - 1; ++i) {
for (int j = 0; j < size - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
// Swap the elements
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; ++i) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {54, 37, 81, 12, 95, 6, 23, 68, 47, 76, 29, 42};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Original list: ";
printArray(arr, size);
bubbleSort(arr, size);
cout << "Sorted list: ";
printArray(arr, size);
return 0;
}
Insertion Sort
Insertion Sort divides the set of elements into a sorted part and an unsorted part. It takes an element from the unsorted part and inserts it into the correct position in the sorted part. It repeats this process until all elements are sorted.
IMPLEMENTATION IN C++
#include <iostream>
using namespace std;
void insertionSort(int arr[], int size) {
for (int i = 1; i < size; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; ++i) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {54, 37, 81, 12, 95, 6, 23, 68, 47, 76, 29, 42};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Original list: ";
printArray(arr, size);
insertionSort(arr, size);
cout << "Sorted list: ";
printArray(arr, size);
return 0;
}
Selection Sort
Selection Sort searches for the smallest element in the set of elements and places it in the correct position. Then, it searches for the next smallest element and places it in the next correct position. It repeats this process until all elements are sorted.
IMPLEMENTATION IN C++
#include <iostream>
using namespace std;
void selectionSort(int arr[], int size) {
for (int i = 0; i < size - 1; ++i) {
int minIndex = i;
for (int j = i + 1; j < size; ++j) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr[i], arr[minIndex]);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; ++i) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {54, 37, 81, 12, 95, 6, 23, 68, 47, 76, 29, 42};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Original list: ";
printArray(arr, size);
selectionSort(arr, size);
cout << "Sorted list: ";
printArray(arr, size);
return 0;
}
Merge Sort
Merge Sort divides the set of elements into smaller subsets, sorts them separately, and then merges them to obtain a larger sorted set. This algorithm uses a divide and conquer strategy.
IMPLEMENTATION IN C++
#include <iostream>
using namespace std;
void merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (i = 0; i < n1; ++i)
L[i] = arr[left + i];
for (j = 0; j < n2; ++j)
R[j] = arr[mid + 1 + j];
i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
++i;
} else {
arr[k] = R[j];
++j;
}
++k;
}
while (i < n1) {
arr[k] = L[i];
++i;
++k;
}
while (j < n2) {
arr[k] = R[j];
++j;
++k;
}
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
void printList(int arr[], int size) {
for (int i = 0; i < size; ++i) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {54, 37, 81, 12, 95, 6, 23, 68, 47, 76, 29, 42};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Original list: ";
printList(arr, size);
mergeSort(arr, 0, size - 1);
cout << "Sorted list: ";
printList(arr, size);
return 0;
}
Quick Sort
Quick Sort chooses an element called a "pivot" and divides the set into two subsets, one with elements smaller than the pivot and another with elements larger. Then, it applies the same process recursively to each of the subsets. This algorithm also uses the divide and conquer strategy.
IMPLEMENTATION IN C++
#include <iostream>
using namespace std;
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; ++j) {
if (arr[j] < pivot) {
++i;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; ++i) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {54, 37, 81, 12, 95, 6, 23, 68, 47, 76, 29, 42};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Original list: ";
printArray(arr, size);
quickSort(arr, 0, size - 1);
cout << "Sorted list: ";
printArray(arr, size);
return 0;
}
Heap Sort
Heap Sort builds a heap from the elements and then successively extracts the maximum (or minimum) element from the heap, readjusting the heap after each extraction. The final result is a set of sorted elements.
IMPLEMENTATION IN C++
#include <iostream>
using namespace std;
void heapify(int arr[], int size, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < size && arr[left] > arr[largest]) {
largest = left;
}
if (right < size && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, size, largest);
}
}
void heapSort(int arr[], int size) {
for (int i = size / 2 - 1; i >= 0; --i) {
heapify(arr, size, i);
}
for (int i = size - 1; i >= 0; --i) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; ++i) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {54, 37, 81, 12, 95, 6, 23, 68, 47, 76, 29, 42};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Original list: ";
printArray(arr, size);
heapSort(arr, size);
cout << "Sorted list: ";
printArray(arr, size);
return 0;
}
These are just some examples of the most common sorting algorithms. Each of them has different characteristics in terms of time complexity, stability, memory consumption, and adaptability to different scenarios. The choice of the appropriate algorithm will depend on the context and specific requirements of the problem to be solved.