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;
}