Sorting Cheatsheet
Bubble Sort
#include<iostream>
using namespace std;
int main() {
int arr[] = {5,2,6,1,4,3};
int n = sizeof arr/sizeof arr[0];
for (int i=0 ; i<n-1 ; i++) {
for (int j=0 ; j<n-1 ; j++) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
for (int i=0 ; i<n; i++) {
cout << arr[i] << " ";
} cout << endl;
return 0;
}
Insertion Sort
#include <iostream>
using namespace std;
int main() {
int arr[] = {5,2,6,1,4,3};
int n = sizeof arr/sizeof arr[0];
for (int i=1 ; i<n ; i++) {
int key = arr[i];
int j=i-1;
while (j>=0 and arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
for (int i=0 ; i<n; i++) {
cout << arr[i] << " ";
} cout << endl;
return 0;
}
Selection Sort
#include <iostream>
using namespace std;
int findMinIndex(int arr[], int start, int n) {
int minIndex = start;
for (int i=start+1 ; i<n ; i++) {
if (arr[i] < arr[minIndex]) {
minIndex = i;
}
}
return minIndex;
}
int main() {
int arr[] = {5,2,6,1,4,3};
int n = sizeof arr/sizeof arr[0];
for (int i=0 ; i<n ; i++) {
// Finding Minimum Index
int minIndex = findMinIndex(arr, i, n);
if (minIndex != i) {
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
for (int i=0 ; i<n; i++) {
cout << arr[i] << " ";
} cout << endl;
return 0;
}
Merge Sort
#include <iostream>
using namespace std;
void merge(int arr[], int start, int mid, int end) {
int temp[end-start+1];
int i=start, j=mid+1, k=0;
while (i<=mid and j<=end) {
if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
while (i<=mid)
temp[k++] = arr[i++];
while (j<=end)
temp[k++] = arr[j++];
for (int i=start ; i<=end ; i++)
arr[i] = temp[i-start];
}
void mergeSort(int arr[], int start, int end) {
if (start < end) {
int mid = (start+end)/2;
mergeSort(arr, start, mid);
mergeSort(arr, mid+1, end);
merge(arr, start, mid, end);
}
}
int main() {
int arr[] = {5,2,6,1,4,3};
int n = sizeof arr/sizeof arr[0];
mergeSort(arr, 0, n-1);
for (int i=0 ; i<n; i++) {
cout << arr[i] << " ";
} cout << endl;
return 0;
}
Last updated