#include <stdio.h>
#include <math.h>
#include <stdlib.h>


///////////////////////
/////   冒泡排序   /////
///////////////////////

void test_bubble_sort_1() // 冒泡排序
{
    int arr[] = {4, 3, 66, 22, 15, 958, 100};
    int n = 7;
    for(int i = 0; i < n - 1; i ++) // i 指代轮次
    {
        for(int j = 0; j < n - i - 1; j ++) // j 指代位置
        {
            if(arr[j] > arr[j + 1])
            {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
    for(int i = 0; i < n; i ++)
        printf("%d ", arr[i]);
}


void test_bubble_sort_2() // 冒泡排序 2
{
    int arr[] = {4, 3, 66, 22, 15, 958, 100};
    int n = 7;

    // your code here
    for(int i = 0; i < n; i ++) // i 指代轮次
        for(int j = n - 1; j >= 1 + i; j --) // j 指代位置
            if(arr[j] < arr[j - 1])
            {
                int tmp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = tmp;
            }
    for(int i = 0; i < n; i ++)
        printf("%d ", arr[i]);
}


void bubbleSortRecursive(int arr[], int i)
{
    if(i == 0)
        return;

    for(int j = 0; j < i; j ++)
        if(arr[j] > arr[j + 1])
        {
            int tmp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = tmp;
        }

    bubbleSortRecursive(arr, i - 1);
}

void test_bubble_sort_3()
{
    int arr[] = {4, 3, 66, 22, 15, 958, 100};
    int n = 7;

    bubbleSortRecursive(arr, n - 1);

    for(int i = 0; i < n; i ++)
        printf("%d ", arr[i]);
}

void bubbleSortRecursive_2(int arr[], int n, int i)
{
    if(i == n - 1)
        return;

    for(int j = n - 1; j >= 1 + i; j --) // j 指代位置
            if(arr[j] < arr[j - 1])
            {
                int tmp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = tmp;
            }

    bubbleSortRecursive_2(arr, n, i + 1);
}

void test_bubble_sort_4()
{
    int arr[] = {4, 3, 66, 22, 15, 958, 100};
    int n = 7;

    bubbleSortRecursive_2(arr, n, 0);

    for(int i = 0; i < n; i ++)
        printf("%d ", arr[i]);
}


///////////////////////
///  Insertion Sort  //
///////////////////////

/* Function to sort an array using insertion sort*/
void insertion_sort(int arr[], int n)
{
    int i, key, j;
    for (i = 1; i < n; i ++) {
        key = arr[i];
        j = i - 1;

        /* Move elements of arr[0..i-1], that are
          greater than key, to one position ahead
          of their current position */
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}


int test_insertion_sort()
{
    int arr[] = { 12, 11, 13, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);

    insertion_sort(arr, n);

    for (int i = 0; i < n; i ++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

void insertion_sort_recursive(int arr[], int n, int i)
{
	if(i == n)
        return;

	int key = arr[i];
    int j = i - 1;

	while (j >= 0 && arr[j] > key) {
		arr[j + 1] = arr[j];
		j = j - 1;
	}
	arr[j + 1] = key;

	insertion_sort_recursive(arr, n, i + 1);
}

int test_insertion_sort_recursive()
{
    int arr[] = { 12, 11, 13, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);

    insertion_sort_recursive(arr, n, 1);

    for (int i = 0; i < n; i ++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}


///////////////////////
///  Selection Sort  //
///////////////////////

void swap(int* xp, int* yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

void selection_sort(int arr[], int n)
{
    int i, j, min_idx;

    // One by one move boundary of unsorted subarray
    for (i = 0; i < n-1; i ++)
    {
        // Find the minimum element in unsorted array
        min_idx = i;
        for (j = i + 1; j < n; j ++)
          if (arr[j] < arr[min_idx])
            min_idx = j;

        // Swap the found minimum element with the first element
        swap(&arr[min_idx], &arr[i]);
    }
}


int test_selection_sort()
{
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    selection_sort(arr, n);

    printf("Sorted array: \n");
    for (int i = 0; i < n; i ++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}


///////////////////////////
/////  Ranking Sort  //////
///////////////////////////

/**
 * Ref: https://stackoverflow.com/questions/11656532/returning-an-array-using-c
 * Ref: https://www.javatpoint.com/return-an-array-in-c
 */

void ranking_sort(int arr[], int n, int arr_sorted[])
{
    int index_in_element, scan_index, nb_smaller;

    for (index_in_element = 0; index_in_element < n; index_in_element ++)
    {
        nb_smaller = 0;
        for (scan_index = 0; scan_index < n; scan_index ++)
        {
            if (arr[scan_index] < arr[index_in_element])
                nb_smaller ++;
        }
        arr_sorted[nb_smaller] = arr[index_in_element];
    }
}

void test_ranking_sort()
{
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    int arr_sorted[n];

    ranking_sort(arr, 5, arr_sorted);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i ++)
        printf("%d ", arr_sorted[i]);
    printf("\n");
}