5 Most Useful Sorting Algorithms
This blog is about the 5 most useful Sorting Algorithms used in programming. While programming languages have easy-to-use sorting methods, it can be helpful to understand how they work and their implementation in C++.
A sorting algorithm is an algorithm that puts elements of an array or a list in a certain order. The most common types of Sorting Algorithms include:-
✅ Selection Sort
✅Bubble Sort
✅Insertion Sort
✅Merge Sort
✅Quick Sort
TIME COMPLEXITY ANALYSIS
👉 SELECTION SORT
In Selection Sort, we divide the array into two parts: sorted and unsorted. The left part is sorted subarray and the right part is unsorted subarray. Initially, the sorted subarray is empty and the unsorted array is the complete given array.
We perform the steps given below until the unsorted subarray becomes empty:
1. Pick the minimum element from the unsorted subarray.
2. Swap it with the leftmost element of the unsorted subarray.
3. Now the leftmost element of unsorted subarray becomes a part (rightmost) of sorted subarray and will not be a part of the unsorted subarray.
Implementation of Selection Sort in C++:-
#include <bits/stdc++.h>
using namespace std;
int findMinIndex(vector<int> &A, int start) {
int min_index = start;
++start; while(start < (int)A.size()) {
if(A[start] < A[min_index]) {
min_index = start;
}
++start;
} return min_index;
}
void selectionSort(vector<int> &A) {
for(int i = 0; i < (int)A.size(); ++i) {
int min_index = findMinIndex(A, i);
if(i != min_index){
swap(A[i], A[min_index]);
}
}
}
int main() {
vector<int> A = {5, 2, 6, 7, 2, 1, 0, 3};
selectionSort(A);
for(int num : A)
cout << num << ' '; return 0;
}
👉 BUBBLE SORT
Bubble Sort is the Simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order.
1. In an unsorted array of 4 elements, start with the first two elements and sort them in ascending order. (Compare the element to check which one is greater).
2. Compare the second and third element to check which one is greater, and sort them in ascending order.
3. Compare the third and fourth element to check which one is greater, and sort them in ascending order.
4. Repeat steps 1–4 until no more swaps are required.
Implementation of Bubble Sort in C++
#include<bits/stdc++.h>
using namespace std;
void BubbleSort (vector<int> &arr, int n) {
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], arr[j + 1]);
}
}
}
}
int main() {
vector<int> arr = {33, 14, 27, 35, 10};
int n = 5; BubbleSort(arr, n); cout << "\nSorted Data: ";
for (int i = 0; i < n; i++)
cout << arr[i] << “ “; return 0;
}
👉 INSERTION SORT
Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.
To sort an array of size n in ascending order:
1. Iterate from arr[1] to arr[n] over the array.
2. Compare the current element (key) to its predecessor.
3. If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.
Implementation of Insertion Sort in C++
#include <bits/stdc++.h>
using namespace std;void printArray(int array[], int size) {
int j; for (j = 0; j < size; j++) {
cout <<" "<< array[j];
}
cout << endl;
}void insertionSort(int arr[], int length) {
int i, j, key; for (i = 1; i < length; i++) {
key = arr[i];
j = i - 1; while (j >= 0 && arr[j] >key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
} cout << "Sorted Array: ";
printArray(arr, length);
}
int main() {
int array[6] = {5, 1, 6, 2, 4, 3}; insertionSort(array, 6);
return 0;
}
👉 MERGE SORT
The Merge Sort Algorithm is based on the principle of Divide and Conquer Algorithm. Here, a problem is divided into multiple sub-problems. Each sub-problem is solved individually. Finally, sub-problems are combined to form the final solution.
Suppose we had to sort an array A. A subproblem would be to sort a sub-section of this array starting at index p and ending at index r, denoted as A[p..r].
1. Divide: If q is the half-way point between p and r, then we can split the subarray A[p..r] into two arrays A[p..q] and A[q+1, r].
2. Conquer: In the conquer step, we try to sort both the subarrays A[p..q] and A[q+1, r]. If we haven’t yet reached the base case, we again divide both these subarrays and try to sort them.
3. Combine: When the conquer step reaches the base step and we get two sorted subarrays A[p..q] and A[q+1, r] for array A[p..r], we combine the results by creating a sorted array A[p..r] from two sorted subarrays A[p..q] and A[q+1, r].
Implementation of Merge Sort in C++
#include <bits/stdc++.h>
using namespace std;
void merge(int arr[], int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;
int L[n1], M[n2];
for (int i = 0; i < n1; i++){
L[i] = arr[p + i];
} for (int j = 0; j < n2; j++){
M[j] = arr[q + 1 + j];
} int i, j, k;
i = 0;
j = 0;
k = p;
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = M[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = M[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++){
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {6, 5, 12, 10, 9, 1};
int size = sizeof(arr) / sizeof(arr[0]); mergeSort(arr, 0, size - 1); cout << "Sorted array: \n";
printArray(arr, size);
return 0;
}
👉 QUICK SORT
The quick sort algorithm attempts to separate the list of elements into two parts and then sort each part recursively. That means it uses divide and conquer strategy. In quick sort, the partition of the list is performed based on the element called pivot. Here pivot element is one of the elements in the list.
The list is divided into two partitions such that “all elements to the left of pivot are smaller than the pivot and all elements to the right of pivot are greater than or equal to the pivot”.
In Quick sort algorithm, partitioning of the list is performed using the following steps:-
1. Consider the first element of the list as pivot (i.e., Element at first position in the list).
2. Define two variables i and j. Set i and j to first and last elements of the list respectively.
3. Increment i until list[i] > pivot then stop.
4. Decrement j until list[j] < pivot then stop.
5. If i < j then exchange list[i] and list[j].
6. Repeat steps 3,4 & 5 until i > j.
7. Exchange the pivot element with list[j] element.
Implementation of Quick Sort in C++
#include <bits/stdc++.h>
using namespace std;void quickSort(int list[10], int first, int last){
int pivot, i, j, temp; if(first < last){
pivot = first;
i = first;
j = last; while(i < j){
while(list[i] <= list[pivot] && i < last) {
i++;
} while(list[j] > list[pivot]) {
j--;
} if(i < j){
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
swap(list[j], list[pivot]); quickSort(list,first,j-1);
quickSort(list,j+1,last);
}
}int main(){
int list[20], size, i;
cout << "Enter size of the list: ";
cin >> size;
cout << "Enter " << size << " integer values: "; for(i = 0; i < size; i++)
cin >> list[i]; quickSort(list, 0, size - 1); cout << "List after sorting is: ";
for(i = 0; i < size; i++)
cout << list[i] << " ";
return 0;
}
Thank you for reading and I hope this blog helps you in clearing your concepts about Sorting Algorithms. If you have any questions or suggestions, feel free to comment.
