Sorting Algorithms

.cpp

#include<bits/stdc++.h>
using namespace std;
void show(int arr[], int size){
	cout<<"\n";
	for(int i = 0; i < size; i++){
		cout<<arr[i]<<" ";
	}
}
int getMax(int arr[], int size){
	int max = arr[0];
	for(int i = 1; i < size; i++){
		if(arr[i] > max) max = arr[i];
	}
	return max;
}
void bubbleSort(int arr[], int size){
	cout<<"\nBubble Sort";
//	[1,12,0,23]
	for(int i = 0; i < size; i++){
		for(int j = 0; j < size - 1; j++){
			if(arr[j] > arr[j + 1]){
				swap(arr[j], arr[j + 1]);
			}
		}
	}
	show(arr,size);
}
void insertionSort(int arr[], int size){
	cout<<"\nInsertion Sort ";
	int comp = 0;
	for(int i = 1; i < size; i++){
		int j = i - 1;
		int current = arr[i];
		for(j; j >=0 && arr[j] > current; j--){
			if(arr[j] > current){
				comp++;
				arr[j + 1] = arr[j];
			}
		}
		swap(arr[j + 1], current);
	}
	cout<<"\nTotal Comparisons "<<comp;
	show(arr,size);
}
void selectionSort(int arr[], int size){
	cout<<"\nSelection Sort ";
	for(int i = 0; i < size - 1; i++){
		int min = i;
		for(int j = i + 1; j < size; j++){
			if(arr[j] < arr[min]){
				min = j;
			}
		}
		swap(arr[i], arr[min]);
	}
	show(arr,size);
}
void merge(int arr [],int start, int middle, int end){
	int len1 = (middle - start) + 1;
	int len2 = (end - middle);
	int arr1[len1]; int arr2[len2];
	int i = 0; int j = 0; int k = start;
	for(int x = 0; x < len1; x++) arr1[x] = arr[x + start];
	for(int x = 0; x < len2; x++) arr2[x] = arr[x + middle + 1];
	while(i < len1 && j < len2){
		if(arr1[i] < arr2[j]) arr[k++] = arr1[i++];
		else arr[k++] = arr2[j++];
	}
	while(i < len1) arr[k++] = arr1[i++];
	while(j < len2) arr[k++] = arr2[j++];
}
void mergeSort(int arr[], int start, int end){
	if(start < end){
		int middle = (start + end) / 2;
		mergeSort(arr,start,middle);
		mergeSort(arr,middle + 1, end);
		merge(arr,start,middle,end);
	}
}
int partition(int arr[], int start, int end){
//	int arr[] = {82,0,8,2,19,0,11,0,1,23,12,7,23,42,1};
	int pivot = end;
	int index = start - 1;
	for(int i = start; i <= end - 1; i++){
		if(arr[i] < arr[pivot]){
			index++;
			swap(arr[i],arr[index]);
		}
	}
	swap(arr[index + 1],arr[pivot]);
	return index +  1;
}
void quickSort(int arr[], int start, int end){
	
	if(start < end){
		int pivot = partition(arr, start, end);
		quickSort(arr,start,pivot - 1 );
		quickSort(arr,pivot + 1, end);
	}
}
void heapify(int arr[], int el, int size){
	int left = 2 * el;
	int right = 2 * el + 1;
	int largest = el;
	if(left < size && arr[left] > arr[largest]){
		largest = left;
	}
	if(right < size && arr[right] > arr[largest]){
		largest = right;
	}
	if(el != largest){
		swap(arr[el],arr[largest]);
		heapify(arr,largest,size);
	}
}
void swap(int arr[], int i, int j){
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}
void heapSort(int arr[], int size){
	for(int i = (size / 2) - 1; i >=0; i--){
		heapify(arr,i,size);
	}
	cout<<"\n";
	for(int i = size - 1; i >= 0; i--){
		swap(arr,0,i);
		heapify(arr,0,i);
	}
}

void radixCountSort(int arr[], int exp, int size){
	int count[10] = {0};
	for(int i = 0; i < size; i++) count[(arr[i] / exp) % 10]++;
	for(int i = 1; i < size; i++) count[i] += count[i - 1];
	int output[size];
	for(int i = size - 1; i >=0; i--){
		output[count[(arr[i] / exp) % 10] - 1] = arr[i];
		count[(arr[i] / exp) % 10]--;
	}
	for(int i = 0; i < size; i++)
		arr[i] = output[i];
}
void radixSort(int arr[],int size){
	int max = getMax(arr,size);
	for(int exp = 1; (max / exp) > 0; exp *= 10){
		radixCountSort(arr,exp,size);
	}
}

void countSort(int arr[], int size){
	int max = getMax(arr,size);
	int count[max + 1] = {0};
	for(int i = 0; i < size; i++) count[arr[i]]++;
	for(int i = 0; i <= max; i++) count[i] += count[i - 1];
	int output[size];
	for(int i = size - 1; i >=0; i--){
		output[count[(arr[i])] - 1] = arr[i];
		count[arr[i]]--;
	}
	for(int i = 0; i < size; i++) arr[i] = output[i];
//	show(output,size);
}

int main(){
	int arr[] = {82,0,8,2,19,0,11,0,1,23,12,7,23,42,1};
	int size = sizeof(arr) / sizeof(arr[0]);	
	int arr1[] = {82,0,8,2,19,0,11,0,1,23,12,7,23,42,1};
	int size1 = sizeof(arr) / sizeof(arr[0]);
	sort(arr1,arr1 + size1);
	show(arr1,size);
	cout<<"\n";
//	bubbleSort(arr,size);
//	insertionSort(arr,size);
//	selectionSort(arr,size);
//	mergeSort(arr,0,size -1);
//	quickSort(arr,0,size - 1);
//	heapSort(arr,size);
//	radixSort(arr,size);
//	countSort(arr,size);	
//	show(arr,size);
}