#ifndef SORT_ALGORITHMS_HPP
#define SORT_ALGORITHMS_HPP

#include <cstdint>
#include <utility>

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++)
			if(s[j]>s[j+1])
				std::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=1+i; j<n; j++)
			if(s[j] <s[min_idx])
				min_idx = j;

		std::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, j=0, 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++;
		std::swap(s[i],s[j]);
		}
	}
	std::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);

}
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[i]>s[j])
			rank++;

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

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

	delete[] temp;
}

#endif