All Types of Sorting in C++ languages
1) Bubble Sort
Bubble sort is a sorting algorithm which iterates through a given array of elements and compares each pair of adjacent elements one after the other. In any of the adjacent pairs, if the first element is greater/larger than the second element, then it swaps the elements and if not, then it moves on to the next pair of elements. The end objective of bubble sort is to sort the given array in ascending order.
Bubble Sort Explanation with Examples
Let us consider an array having 5 elements. Here is the working of bubble sort with an example.
After the first iteration, are the elements in the ascending order?
No. This means we will have to keep repeating this set of actions again and again until the entire array of elements are sorted. But then, how many times will we have to iterate a given array such that the array is completely sorted?
In general, it takes (n-1) iterations in order to sort a given array using the bubble sort algorithm, where n is the number of elements in the array.
So in this case, since there are 5 elements, it takes (5-1), i.e 4 iterations to completely sort the array.
Bubble Sort Pseudo Code
Here is the pseudo-code of bubble sort.
for i = 0 to n - 1 // to keep track of the number of iterationsfor j = 0 to n - 1 // to compare the elements within the particulariteration// swap ifany element is greater than its adjacent elementif arr[j] > arr[j + 1] then swap(arr[j], arr[j + 1]) end if end for end for
Bubble Sort Implementation
Implementation of Bubble sort in C++ is given here
#include<iostream> using namespace std; int main()
{
int n, i, j, temp; cin >> n; int arr[n]; for(i = 0; i < n; i++)
{ cin >> arr[i];
}
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;
}
}
}
for(i = 0; i < n; i++)
{ cout << arr[i] << " ";
}
}
Time Complexity : O(N) { Best Case}
Space Complexity : O(1) {Worst Case}
2) Selection Sort
A Selection sort algorithm sorts an array of elements by iterating and finding the smallest/largest one and then putting it aside into a sorted list. It continues to sort by finding the smallest/largest unsorted element and adding it to the sorted list of elements.This happens until there are no elements left in the unsorted list .
Selection Sort Example
Assume that the array A = [14,16, 3, 6, 50]needs to be sorted in ascending order.
So now, the minimum element in the array i.e.3 is searched for and then swapped with the element that is currently located in the first position, i.e.14. Now the minimum element in the remaining unsorted array is searched for and put in the second position, and so on. Have a look at the implementation explained below.
#include<iostream> using namespace std; int main()
{
int n, i, j, temp, min; cin >> n; int arr[n]; for(i = 0; i < n; i++)
{ cin >> arr[i]; }
for (i = 0; i < n - 1; i++)
{
// Finding the minimum element in unsorted array
min = i;
for (j = i + 1; j < n; j++) if (arr[j] < arr[min]) min = j;
// Swaping the found minimum element with the first element temp = arr[min]; arr[min] = arr[i]; arr[i] = temp;
} for(i = 0; i < n; i++)
{ cout << arr[i] << " ";
}
}
Time Complexity : O(N*N) { Best Case}
Space Complexity : O(1) {Worst Case}
3) Insertion Sort
Insertion sort is slightly different from the other sorting algorithms. It is based on the idea that each element in the array is consumed in each iteration to find its right position in the sorted array such that the entire array is sorted at the end of all the iterations.
In other words, it compares the current element with the elements on the left-hand side (sorted array).If the current element is greater than all the elements on its left hand side, then it leaves the element in its place and moves on to the next element. Else it finds its correct position and moves it to that position by shifting all the elements, which are larger than the current element, in the sorted array to one position ahead.
Conclusion: Each iteration of insertion sort causes the sorted subset to grow, and the unsorted subset to shrink.
Insertion Sort Example & Working
Let us consider an array with 5 elements, A = [7, 1, 23, 4, 19]. Below is how insertion sort works for this array .
Insertion Sort Pseudo Code
Here is the pseudocode implementation of Insertion sort.
for i = 1 to n key = arr[i] j = i - 1
// comparing whether the first element is greater than the second element
// if yes, then store the largest element to the next position while j >= 0 and arr[j] > key arr[j + 1] = arr[j] j = j - 1 end while
// storing the smallest element in the correct position arr[j + 1] = key end for
#include<iostream> using namespace std; int main()
{ int i, n, j, temp, min, key; cin >> n; int arr[n]; for(i = 0; i < n; i++)
{ cin >> arr[i]; }
for (i = 1; i < n; i++)
{ key = arr[i];
j = i - 1;
// comparing whether the first element is greater than the second element
// if yes, then store the largest element to the next position while (j >= 0 && arr[j] > key)
{ arr[j + 1] = arr[j]; j = j - 1;
}
// storing the smallest element in the correct position arr[j + 1] = key;
} for(i = 0; i < n; i++)
{ cout << arr[i] << " ";
}
}
Time Complexity : O(N) { Best Case}
Space Complexity : O(1) {Worst Case}
4) Merge Sort
In Merge sort, the given array is sorted using Divide and Conquer algorithm . This algorithm divides the input array into sub-arrays (until each sub array contains one element only) and then recursively sorts the sub-arrays. The sorted sub-arrays are then merged back together to form a single sorted array. This is where Merge sort differs from all other sorting algorithms.
A simple visualization of this is shown below.
Merge Sort Pseudo Code
procedure merge(array, start, mid, end)
num1 = mid - start + 1 num2 = end - mid
// Copy data to temporary arrays arr1[] and arr2[] for i = 0 to num1 arr1[i] = arr[start + i] for j = 0 to num2 arr2[j] = arr[mid + 1 + j]
// Merge the temp arrays back into arr[] i = 0 // Initial index of first subarray j = 0 // Initial index of second subarray k = start // Initial index of merged subarray while (i < num1 and j < num2) if (arr1[i] <= arr2[j]) then arr[k] = arr1[i] i++ end if else arr[k] = arr2[j] j++ end else k++ end while
// Copy the remaining elements of arr1[], if there are any while (i < num1) arr[k] = arr1[i] i++ k++ end while
// Copy the remaining elements of arr2[], if there are any while (j < num2) arr[k] = arr2[j] j++ k++ end while end procedure
procedure divide(array, start, end) if(start < end) then mid = (start + end) / 2 divide(arr, start, mid) divide(arr, mid + 1, end) merge(arr, start, mid, end) end if end procedure
#include <iostream> using namespace std;
int merge(int arr[], int start, int mid, int end)
{
int i, j, k;
int num1 = mid - start + 1; int num2 = end - mid; // create temporary arrays int arr1[num1], arr2[num2];
// Copy data to temporary arrays arr1[] and arr2[] for (i = 0; i < num1; i++)
arr1[i] = arr[start + i]; for (j = 0; j < num2; j++) arr2[j] = arr[mid + 1 + j];
// Merge the temp arrays back into arr[] i = 0; // Initial index of first subarray j = 0; // Initial index of second subarray k = start; // Initial index of merged subarray while (i < num1 && j < num2)
{ if (arr1[i] <= arr2[j])
{ arr[k] = arr1[i]; i++;
} else
{ arr[k] = arr2[j]; j++; } k++;
}
// Copy the remaining elements of arr1[], if there are any while (i < num1)
{ arr[k] = arr1[i]; i++; k++;
}
// Copy the remaining elements of arr2[], if there are any while (j < num2)
{ arr[k] = arr2[j]; j++; k++;
} } int divide(int arr[], int start, int end)
{ if(start < end) { int mid; mid = (start + end) / 2; divide(arr, start, mid); divide(arr, mid + 1, end); merge(arr, start, mid, end);
}
}
int print(int arr[], int n)
{
for(int i = 0; i < n; i++)
{ cout << arr[i] << " ";
}
} int main() {
int n, i; cin >> n; int arr[n]; for(i = 0; i < n; i++)
{ cin >> arr[i];
} divide(arr, 0, n - 1); print(arr, n);
}
Time Complexity : O(N log N) { Best Case}
Space Complexity : O(N) {Worst Case}
5) Quick Sort
Quicksort is the quickest and one of the most efficient sorting algorithm. Similar to Merge sort , Quick sort follows Divide and conquer algorithm to sort the given array.
The quicksort algorithm is a sorting algorithm that sorts an array by choosing a pivot element, and partition the array around the pivot such that
Elements smaller than the pivot are moved to the left of pivot, and elements larger than the pivot are moved to the right of pivot.
It continues to choose a pivot element and break down the array into single-element array, before combing them back together to form a single sorted array.
Note: Don't get confused as to how to determine a pivot. Simply choose the first/last/ideally the middle element as pivot without any confusion.
Quick Working of Quick Sort Algorithm
Here is how a quick sort algorithm works for a given array of 6 elements.
#include<iostream> using namespace std;
int partition(int arr[], int low, int high)
{ int temp; int pivot = arr[high]; // assuming last element of the array as the pivot element
int i = (low - 1); // assuming the index of i pointer as one position less than the first element
for (int j = low; j <= high - 1; j++) // assuming the index of j pointer as the first position {
// If current element is smaller than or equal to pivot if (arr[j] <= pivot)
{ i++; // increment index of i pointer and swap the elemets at index i and j temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}
}
// swapping the pivot (last) element and element at i + 1 index temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp;
// returning the index of pivot element having lesser elements to the left and greater elements to the right
return (i + 1); } void quick_sort(int arr[], int low, int high)
{ if (low < high)
{
// partitioning the single array into two sub-arrays int pi = partition(arr, low, high);
// sorting the sub-arrays quick_sort(arr, low, pi - 1); quick_sort(arr, pi + 1, high);
} } int print(int arr[], int n)
{
for(int i = 0; i < n; i++)
{ cout << arr[i] << " ";
}
} int main()
{
int n, i; cin >> n; int arr[n]; for(i = 0; i < n; i++) { cin >> arr[i];
} quick_sort(arr, 0, n - 1); print(arr, n);
}
Time Complexity : O(N log N) { Best Case}
Space Complexity : O(N) {Worst Case}
6) Shell Sort
Shell sort algorithm is very similar to that of the Insertion sort algorithm. In case of Insertion sort, we move elements one position ahead to insert an element at its correct position. Whereas here, Shell sort starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements, it can move some out-of-place elements into the position faster than a simple nearest-neighbor exchange.
A simple look at Shell Sort Vs Insertion Sort
Shelling out the Shell Sort Algorithm with Examples
Here is an example to help you understand the working of Shell sort on array of elements name A = {17, 3, 9, 1, 8}
#include<iostream> using namespace std; int main() { int n, i, j, temp, gap; cin >> n; int arr[n]; for(i = 0; i < n; i++)
{ cin >> arr[i];
} for (gap = n/2; gap > 0; gap = gap / 2)
{
// Do a gapped insertion sort
// The first gap elements arr[0..gap-1] are already in gapped order // keep adding one more element until the entire array is gap sorted
for (i = gap; i < n; i = i + 1)
{
// add arr[i] to the elements that have been gap sorted // save arr[i] in temp and make a empty space at index i int temp = arr[i];
// shift earlier gap-sorted elements up until the correct location for arr[i] is found for (j = i; j >= gap && arr[j - gap] > temp; j = j - gap) arr[j] = arr[j - gap];
// put temp (the original arr[i]) in its correct position
arr[j] = temp;
} } for(i = 0; i < n; i++)
{ cout << arr[i] << " ";
}
}
Time Complexity : O(N log N) { Best Case}
Space Complexity : O(1) {Worst Case}
7) Heap Sort
Before we get into Heap sort, let's understand what a Heap data structure is.
Heap is a special kind of binary tree in which elements are stored in a hierarchical manner. Heap has some additional rules it must always have a heap structure, where all the levels of the binary tree are filled up from left to right. Second, it must either be ordered as a max heap or a min-heap.
● Max heap Parent node is greater than or equal to the value of its children node
● Min heap Parent node is less than or equal to the value of its children node
In Heap sort, we will be dealing with Max heap. Using max heaps, we can sort an unsorted array of elements. In simple, this is how it works
Heap Sort Example
Lets see how sorting takes place with the help of heap.Consider an array arr[] = {4, 3, 7, 1, 8, 5}
1) Firstly, lets convert the given array to a binary tree.The representation of a binary tree for the given array looks as shown below.
2) Next, build max-heap from the above tree. A max tree is where all the parent nodes are of higher value than the children nodes.
3) Now, swap the root node with the last element of the heap node. This means largest value has moved to its correct position. So, remove the largest value from the tree. After removing, the tree looks as shown below.
4) Repeat step 3 until no elements are left in the heap
Selection Sort Pseudo code
for i = 0 to n - 1
// Finding the minimum element in unsorted array min = i for j = i + 1 to n
if arr[j] < arr[min] then min = j end if end for
// Swapping the found minimum element with the first element swap(arr[min], arr[i]) end for
#include<iostream> using namespace std; int temp; void swap_largest(int arr[], int n, int i)
{ int largest = i; // Initialize largest as root int left = 2*i + 1; int right = 2*i + 2;
// If left child is larger than root if (left < n && arr[left] > arr[largest]) largest = left;
// If right child is larger than largest if (right < n && arr[right] > arr[largest]) largest = right;
// If largest is not root if (largest != i)
{ temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp;
// Recursively call the swap_largest swap_largest(arr, n, largest);
} } void heap(int arr[], int n)
{
// Build heap from an unsorted array (rearrange array) for (int i = n / 2 - 1; i >= 0; i--) swap_largest(arr, n, i);
// One by one extract an element from heap for (int i = n - 1; i >= 0; i--)
{
// Move current root to end
temp = arr[0]; arr[0] = arr[i]; arr[i] = temp;
// call swap_largest on the reduced heap swap_largest(arr, i, 0);
} } int print(int arr[], int n)
{
for(int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
} int main() { int n, i; cin >> n; int arr[n]; for(i = 0; i < n; i++)
{ cin >> arr[i]; } heap(arr, n); print(arr, n);
}
Time Complexity : O(N log N) { Best Case}
Space Complexity : O(1) {Worst Case}
8) Comb Sort
Comb Sort is an improvised version of bubble sort . The basic idea in comb sort is to eliminate the relatively smaller values situated to the end of the list. This is done as applying bubble sort on such an array would highly slow down the process. In bubble sort, adjacent elements are compared and swapped if necessary to state them in a sorted order. The gap between elements being compared in bubble sort is 1. However, comb sort aims to improvise in this stage by allowing to compare elements with a gap much more than 1. The internal program in bubble sort which swaps the elements is modified such that gap between the swapped elements goes down on each iteration of the outer loop with respect to a shrink factor 'k'. The value of k is generally set to 1.3 for better performance of comb sort.
Once the shrink factor is applied, the list is sorted with the new gap and further the process of reducing the gap is continued. The final stage obtained through this have most of their smaller elements towards the end of the list eliminated. Therefore, at this stage bubble sort can be implemented to reach the final sorted matrix.
The worst-case scenario of comb sort is similar to bubble sort having O(n^2). Below is C++, Java and Python implementation of comb sort.
C++ implementation of Comb Sort
// C++ implementation of Comb Sort
#include<bits/stdc++.h> using namespace std;
// To find gap between elements int getNextGap(int gap)
{
// Shrink gap by Shrink factor gap = (gap*10)/13;
if (gap < 1) return 1; return gap;
}
// Function to sort a[0..n-1] using Comb Sort void combSort(int a[], int n)
{
// Initialize gap int gap = n;
// Initialize swapped as true to make sure that loop runs bool swapped = true;
// Keep running while gap is more than 1 and last iteration caused a swap while (gap != 1 || swapped == true)
{
// Find next gap gap = getNextGap(gap); // Initialize swapped as false so that we can check if swap happened or not swapped = false;
// Compare all elements with current gap for (int i=0; i<n-gap; i++)
{ if (a[i] > a[i+gap])
{ swap(a[i], a[i+gap]); swapped = true;
}
}
}
} int main() {
int a[] = {8, 4, 1, 56, 3, -44, 23, -6, 28, 0}; int n = sizeof(a)/sizeof(a[0]);
combSort(a, n);
printf("Sorted array: \n"); for (int i=0; i<n; i++) printf("%d ", a[i]);
return 0;
}
Time Complexity : O(N log N) { Best Case}
Space Complexity : O(1) {Worst Case}
Posts
0 Comments