Play this article
Before starting the advanced topics for sorting elements, we must have these basic sorting methods:
Bubble Sort
Quick Sort
Merge Sort
Insertion Sort
Selection Sort
Let's quickly review the algorithm one by one below:
Bubble Sort
The idea is to place the largest/minimal element in its position and keep doing the same for every other element.
Code:
void bubble () {
int n = v.size();
for (int i = 0; i<n; i++) {
for (int j =0; j<n; j++) {
if (v[i] < v[j])
swap(v[i], v[j]);
}
}
}
Selection Sort
Code:
void selection () {
int n = v.size();
for (int i = 0; i<n; i++) {
for (int j =i+1; j<n; j++) {
if (v[i] > v[j])
swap(v[i], v[j]);
}
}
}
Insertion Sort
Code:
void insertion () {
int n = v.size();
for(int i=1;i<n;i++){
int x = v[i];
for (int j = i-1; j >=0; j--) {
if (x < v[j]) {
v[j+1] = v[j];
v[j] = x;
}else {
break;
}
}
}
}
Quick Sort:
Code:
int partition (vector<int>& v, int low, int high) {
int pivot = v[low];
int i = low +1;
int j = high;
while (true) {
while (i <= j && v[i] <= pivot) {
i++;
}
while ( i <= j && v[j] >= pivot) {
j--;
}
if (i <= j) {
swap (v[i], v[j]);
}else {
break;
}
}
swap(v[low], v[j]);
return j;
}
void quicksort (vector<int>& v, int low, int high)
{
if (low < high) {
int pi = partition (v, low, high);
quicksort(v, low, pi-1);
quicksort(v, pi+1, high);
}
}
Merge Sort
Code:
#include <bits/stdc++.h>
using namespace std;
int arr[] = {4, 2, 4, 5, -30, -02, 3, -60};
void merge(int low, int mid, int hi)
{
int sa1 = mid - low + 1;
int sa2 = hi - mid;
int L[sa1 + 1], R[sa2 + 1];
for (int i = 0; i < sa1; i++)
{
L[i] = arr[low + i];
}
for (int j = 0; j < sa2; j++)
{
R[j] = arr[mid + 1 + j];
}
L[sa1] = INT_MAX;
R[sa2] = INT_MAX;
int i = 0, j = 0;
for (int k = low; k <= hi; k++)
{
if (L[i] <= R[j])
arr[k] = L[i++];
else
arr[k] = R[j++];
}
}
void mergeSort(int low, int hi)
{
if (low < hi)
{
int mid = (low + hi) / 2;
mergeSort(low, mid);
mergeSort(mid + 1, hi);
merge(low, mid, hi);
}
}
int main()
{
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(0, size);
for (int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
}
N.B: Interesting sorting techniques are coming soon in this article.