#include <Rcpp.h>
using namespace Rcpp;

int minp(NumericVector A, int k, int l)
{
    double m = A[k];
    int i, p = k;
    for (i = k+1; i <= l; i++)
        if (A[i] < m) {
            m = A[i];
            p = i;
        }
    return p;
}

void swap(NumericVector x, int i, int j)
{
    double tmp = x[j];
    x[j] = x[i];
    x[i] = tmp;
}

// [[Rcpp::export]]
NumericVector exchange_sort_cpp(NumericVector x)
{
    NumericVector A;
    int i, p, n = x.length();
    A = NumericVector(n);
    for (i = 0; i < n; i++) A[i] = x[i];
    if (n < 2) return(A);
    for (i = 0; i < n-1; i++) {
        p = minp(A, i, n-1);
	swap(A, i, p);
    }
    return A;
}

// [[Rcpp::export]]
NumericVector selection_sort_cpp(NumericVector x)
{
    NumericVector A;
    int i, j, n = x.length();
    A = NumericVector(n);
    for (i = 0; i < n; i++) A[i] = x[i];
    if (n < 2) return(A);
    for (i = 0; i < n-1; i++) {
	for (j = i+1; j < n; j++) {
	    if (A[i] > A[j])
		swap(A, i, j);
	}
    }
    return A;
}

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