//
// Created by red on 01/12/19.
//

#include "sorts.h"
#include <stdio.h>
#include <stddef.h>

unsigned long partition(double* arr, unsigned long n) {
  double pivot = arr[n-1];
  unsigned long i = 0;
  for (unsigned long j = 0; j < n-1; j++) {
    if (arr[j] < pivot) {
      double tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
      i++;
    }
  }
  double tmp = arr[i];
  arr[i] = arr[n-1];
  arr[n-1] = tmp;
  return i;
}

//quicksort the array pointed at by arr, containing n elements in total.
void quicksort(double* arr, unsigned long n) {
  if (n < 2) { return; }
  unsigned long pivot = partition(arr, n);
  quicksort(arr, pivot);
  quicksort(arr+pivot+1, n-pivot-1);
}


//Ciura (2001), A102549
static size_t const gaps[8] = {701, 301, 132, 57, 23, 10, 4, 1};
static size_t const gaps_num = 8;

void shellsort(double* arr, size_t n) {
  //literally the example code from wikipedia i'm lazy
  for (size_t i = 0; i < gaps_num; i++){
    size_t gap = gaps[i];
    for (size_t j = gap; j < n; j++) {
      double tmp = arr[j];
      size_t k;
      for (k = j; k >= gap && arr[k - gap] > tmp; k -= gap) {
        arr[k] = arr[k-gap];
      }
      arr[k] = tmp;
    }
  }
};


void selectionsort(double* arr, size_t n) {
  for (size_t i = 0; i < n; i++) {
    size_t min = i;
    for (size_t j = i+1; j < n; j++) {
      if (arr[j] < arr[min]) {min = j;}
    }
    if (min != i) {
      double tmp = arr[i];
      arr[i] = arr[min];
      arr[min] = tmp;
    }
  }
}