/* insertion sort, heapsort, quicksort */

#include <Rcpp.h>

using namespace Rcpp;

// [[Rcpp::export]]
NumericVector insertion_sort(NumericVector x)
{
    double key;
    int i, j, n = x.length();
    NumericVector A(n);
    for (j = 0; j < n; j++) A[j] = x[j];
    for (j = 1; j < n; j++) {
	key = A[j];
	i = j - 1;
	while (i > -1 && A[i] > key) {
	    A[i+1] = A[i];
	    i--;
	}
	A[i+1] = key;
    }
    return A;
}


int parent(int i) {
    return (i+1)/2 - 1;
}

int left(int i) {
    return 2 * i + 1;
}

int right(int i) {
    return 2 * i + 2;
}

void max_heapify(NumericVector A, int i, int size)
{
    double tmp;
    int l = left(i), r = right(i), largest = i;
    if (l < size && A[l] > A[i]) largest = l;
    if (r < size && A[r] > A[largest]) largest = r;
    if (largest != i) {
	tmp = A[i];
	A[i] = A[largest];
	A[largest] = tmp;
	max_heapify(A, largest, size);
    }
    return;
}

int build_max_heap(NumericVector A)
{
    int i, size = A.length();
    for (i = parent(size-1); i >= 0; i--)
	max_heapify(A, i, size);
    return size;
}


// [[Rcpp::export]]
Rcpp::NumericVector heap_sort(Rcpp::NumericVector x)
{
    double tmp;
    int size, i, n = x.length();
    Rcpp::NumericVector A(n);
    for (i = 0; i < n; i++) A[i] = x[i];
    size = build_max_heap(A);
    for (i = n-1; i > 0; i--) {
    	tmp = A[0];
    	A[0] = A[i];
    	A[i] = tmp;
    	size--;
    	max_heapify(A, 0, size);
    }
    return A;
}

int partition(NumericVector A, int p, int r)
{
    double tmp, x = A[r];
    int j, i = p-1;
    for (j = p; j < r; j++) {
	if (A[j] <= x) {
	    i++;
	    tmp = A[i];
	    A[i] = A[j];
	    A[j] = tmp;
	}
    }
    tmp = A[r];
    A[r] = A[i+1];
    A[i+1] = tmp;
    return i+1;
}

void quicksort(NumericVector A, int p, int r)
{
    if (p < r) {
	int q = partition(A, p, r);
	quicksort(A, p, q-1);
	quicksort(A, q+1, r);
    }
    return;
}


// [[Rcpp::export]]
Rcpp::NumericVector quick_sort(Rcpp::NumericVector x)
{
    int i, n = x.length();
    Rcpp::NumericVector A(n);
    for (i = 0; i < n; i++) A[i] = x[i];
    quicksort(A, 0, n-1);
    return A;
}