|
- //
- // 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;
- }
- }
- }
|