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


inline void Change(int a[], int first, int second)
// меняем местами эллементы буфера first на second
// a[] - наш массив
// first и second - номера эллементов массива a, которые надо поменять местами!
{
    if (first == second) // Если одинаковые номера эллементов, то
        return; // нах менять их местами

    int i;

    i = a[second];
    a[second] = a[first];
    a[first] = i;

/*
// Можно еще так вот, но так медленее:
    a[first] += a[second]; // Здесь,
    a[second] = a[first] - a[second]; // здесь,
    a[first] = a[first] - a[second]; // и здесь мы меняем местами два числа в буфере
*/
}

int FindMax(int a[], int max)
// Находим максимальное число в массиве от a[0] до a[max]
// a[] - наш массив
// max - размер массива a
{
    int imax = 0;

    for (int i = 0; i <= max; i++)
    {
        if (a[imax] < a[i])
            imax = i;
    }

    return imax;
}

void Sort(int b[], int max)
// Сортировка номер один!
// b[] - наш массив
// max - размер массива b
{
    int i1;
    for (int i = max - 1; i > 0; i--)
    {
        i1 = FindMax(b, i); // Находим самое максимальное число в промежутке от a[0] до a[i]

        Change(b, i, i1); // ставим максимальное число в конец (а именно на место эллемента под номером i)
    }
}

void Sort1(int c[], int max)
// Сортировка номер два!
// c[] - наш массив
// max - размер массива c
{
    for (int i1 = 0; i1 < max; i1++)
    {
        for (int i = max-2; i >= i1; i--)
        {            
            if (c[i+1] > c[i]) continue;

            Change(c, i, i+1); // Двигаем минимальное число вверх, тем самым сортируя числа
        }
    }
}

void main()
{
#define MAX 100
    int a[MAX], b[MAX], c[MAX]; // Объявляем пару буферов

/*
// Можно две строки выше записать еще и так, тогда у юзера будет запрашиваться размер буфера
    int MAX;

    printf("Enter the size of array with the numbers: ");
    scanf("%i", &MAX);

    int *a = new int[MAX]; // Объявляем буфер
    int *b = new int[MAX]; // Объявляем буфер
    int *c = new int[MAX]; // Объявляем буфер
*/

    srand((unsigned)time(0));
    for (int i = 0; i < MAX; i++)
    {
        a[i] = rand(); // заполняем случайными числами
        b[i] = a[i]; // делаем копию
        c[i] = a[i]; // делаем копию
    }

    clock_t begin, end;
    begin = clock();
    Sort(b, MAX); // 
    end = clock();

    float f = (float)(end-begin); // Измеряем время, занятое сортировкой

    printf ("Sorting %i elements with the sort number 1 takes     %.0f msec.\r\n\r\n", MAX, f);

    begin = clock();
    Sort1(c, MAX); // 
    end = clock();
    float f1 = (float)(end-begin); // Измеряем время, занятое сортировкой


    printf ("Sorting %i elements with the sort number 2 takes     %.0f msec.\r\n", MAX, f1);

    printf("\r\n\r\n\r\nDo you really want to view the sorting result? (y/n)"); // Вы хотите просмотреть отсортированные данные?
    short Key = 0;

    while (Key = _getch()) // Ждем, пока чел нажмет какую-нить клавишу
    {
        if (Key == 'n' || Key == 'N' || Key == 27) // если нажата кнопк N или Esc, то
            return; // выход
        else if (Key == 'y' || Key == 'Y') // если y, то
            break; // то продолжаем
    }

    printf("\r\n\r\n\r\n");
    printf(" N.    unsorted     N.    1-st sort     N.    2-nd sort\r\n");
    printf("\r\n");
    for (i = 0; i < MAX; i++)
        printf("%3i.    %5i        %3i.    %5i        %3i.    %5i\r\n", i+1, a[i], i+1, b[i], i+1, c[i]); // Печатаем содержимое массивов!

    printf("\r\nPress any key to continue\r\n");

    Key = 0;

    while (!Key) Key = _getch(); // Ждем, пока чел не нажмет кнопку...
}

/*************************************************/
/* PERFORM SORTING USING BUBBLE METHOD */
/*************************************************/

// Bubble сортировка

void sortbubble(long num, float *array)
// num - число эллементов
// array - указатель на первый эллемент массива
{
    // Sorting using well-known bubble method
    short sorted = 1; //flag, 0 - array not sorted, 1 - sorted
    short changed = 0; //flag, at least one pair was switched
    float temp;

    do
    {
        changed = 0;
        for (long i = 0; i < num - 1; i++)
        {
            if (array[i] > array[i+1])
            {
                temp = array[i];
                array[i] = array[i+1];
                array[i+1] = temp;
                changed = 1;
            }
        }
        sorted = !changed;
    } while (!sorted);

}

/*************************************************/
/* PERFORM SORTING USING MINIMA METHOD */
/*************************************************/

//also known as most "natural" sorting method

// Minima сортировка

void sortminima (long num, float *array)
// num - число эллементов
// array - указатель на первый эллемент массива
{
    long k,s,t;
    k = 0;
    float temp;

    while (k < num)
    {
        s = k;
        t = s;
        while (t < num-1)
        {
            t++;
            if (array[t] < array[s]) s = t;
        }
        temp = array[s];
        array[s] = array[k];
        array[k] = temp;
        k++;
    }
}

/*************************************************/
/* PERFORM SORTING USING SIMPLE INCLUSION METHOD */
/*************************************************/

//taken from alglib block scheme.

// Simple Inclusion сортировка

void sortsimpinc(long num, float *array)
// num - число эллементов
// array - указатель на первый эллемент массива
{
    long i,j,k;
    float temp;

    i = 1;

    do
    {
        j = 0;
        do
        {
            if (array[i] <= array [j])
            {
                k = i;
                temp = array[i];
                do
                {
                    array[k] = array[k-1];
                    k--;
                } while (k > j);

                array[j] = temp;
                j = i;
            }
            else j++;
        } while (j < i);
        i++;
    } while (i < num);
}

/*************************************************/
/* PERFORM SORTING USING BINARY INCLUSION METHOD */
/*************************************************/

//taken from alglib block scheme

// Binary Inclusion сортировка

void sortbininc(long num, float *array)
// num - число эллементов
// array - указатель на первый эллемент массива
{
    long i, b, e, c, k;
    float temp;

    i = 1;
    do
    {
        b = 0;
        e = i - 1;
        c= (b + e)/2;

        while (b != c)
        {
            if (array[c] > array[i]) e=c; else b=c;
            c = (b + e)/2;
        }

        if (array[b] < array[i])
            if (array[i] > array[e]) b = e + 1; else b = e;
        k=i;
        temp = array[i];

        while (k > b)
        {
            array[k] = array[k-1];
            k--;
        }

        array[b] = temp;
        i++;
    } while (i < num);
}

/*************************************************/
/* PERFORM SORTING USING SHELL METHOD */
/*************************************************/

//taken from alglib block scheme

// Shell сортировка

void sortshell (long num, float *array)
// num - число эллементов
// array - указатель на первый эллемент массива
{
    long i,j,g;
    short c; //flag
    float temp;

    g = num/2;
    do
    {
        i = g;
        do
        {
            j = i - g;
            c = 1;
            do
            {
                if (array[j] <= array[j+g]) c = 0;
                else 
                {
                    temp = array[j];
                    array[j] = array[j+g];
                    array[j+g] = temp;
                }
                j--;
            } while(j >= 0 && c);
            i++;
        } while(i < num);
        g = g/2;
    } while(g > 0);
}