#ifndef SORTING_ALGORITHMS_HPP
#define SORTING_ALGORITHMS_HPP

#include <iostream>
#include <cstdint>
#include <utility>

using namespace std;

template <typename T>
class Row;

//bubble sort
template <typename T>
void bubble_sort(Row<T>& s){
	uint32_t n=s.size();

	for(uint32_t i=0; i<n-1; i++){
		for(uint32_t j=0; j<n-i-1; j++){
			swap(s[j],s[j+1]);
			}
		}
}

//selection sort
template <typename T>
void selection_sort(Row<T>& s){
	uint32_t n= s.size();

	for(uint32_t i=0; i<n-1; i++){
		uint32_t min_idx=i;

		for(uint32_t j=i+1; j<n; j++){
			if(s[j] <s[min_idx])
				min_idx=j;
				}
		swap(s[i],s[min_idx]);
			}
}

//insertion sort

template <typename T>
void insertion_sort(Row<T>& s){
	uint32_t n=s.size();

	for (uint32_t i=1; i<n; i++){
		T key=s[i];
		int32_t j=i-1;

		while(j>=0 && s[j]>key){
			s[j+1]=s[j];
			j--;
			}
		s[j+1]=key;
	}
}

//merge sort

template <typename T>
void merge(Row<T>& s,uint32_t left, uint32_t mid, uint32_t right){
	uint32_t n1=mid-left+1;
	uint32_t n2=right-mid;

	T* L=new T[n1];
	T* R=new T[n2];

	for (uint32_t i=0; i<n1; i++){
		L[i]=s[left+i];
		}

	for (uint32_t j=0; j<n2; j++){
		R[j]=s[mid+1+j];
		}
		
	uint32_t i=0; 
	uint32_t j=0; 
	uint32_t k=left;

	while (i<n1 && j<n2){
		if (L[i] <= R[j])
			s[k++]=L[i++];
		else
			s[k++]=R[j++];
		}
	while (i<n1){
		s[k++]=L[i++];
		}

	while (j<n2){
		s[k++]=R[j++];
		}

	delete[] L;
	delete[] R;
}

template <typename T>
void merge_sort_recursive(Row<T>& s, uint32_t left, uint32_t right){
	if(left < right){
	uint32_t mid=left + (right-left)/2;

	merge_sort_recursive(s,left,mid);
	merge_sort_recursive(s,mid +1, right);
	merge(s, left, mid, right);
	}
}

template <typename T>
void merge_sort(Row<T>& s){
	if (s.size() >1)
		merge_sort_recursive(s, 0, s.size()-1);
}


//quick sort
template <typename T>
int partition(Row<T>& s, int low, int high){
	T pivot=s[high];
	int i=low-1;

	for (int j=low; j<high; j++){
		if (s[j] <pivot){
			i++;
			swap(s[i],s[j]);
			}
		}
	swap(s[i+1],s[high]);
	return i+1;
}

template <typename T>
void quick_sort_recursive(Row<T>& s, int low, int high){
	if (low <high){
		int pi=partition(s, low, high);

		quick_sort_recursive(s, low, pi-1);
		quick_sort_recursive(s, pi+1, high);
		}
}

template <typename T>
void quick_sort(Row<T>& s){
	if (s.size() >1)
		quick_sort_recursive(s, 0, s.size()-1);
}


//enumeration sort (or rank sort)

template <typename T>
void enumeration_sort(Row<T>& s){
	uint32_t n=s.size();

	if (n <=1)
	return;

	T* temp= new T[n];

	for (uint32_t i=0; i<n; i++){

		uint32_t rank=0;

		for (uint32_t j=0; j<n; j++){
			if (s[j]<s[i])
				rank++;

			if (s[j] == s[i]  && j<i)
				rank++;
				}
			temp[rank]=s[i];
			}

	for (uint32_t i=0; i<n; i++)
		s[i] =temp[i];


	delete[] temp;
}



#endif