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

/*-------- SELECTION SORTING ----------*/
int selectsort(float p[], int size)
{
    float min, t;
    int minidx, i, j;
    int count = 0;//time complexity counter
    for (j = 0; j < size; j++)
    {
        min = p[j]; minidx = j;
        for (i = j; i < size; i++)
            if (p[i] < min)
            {
                min = p[i]; minidx = i;
            }
        t = p[j]; p[j] = min; p[minidx] = t;
        count++;
    }
    return count;
}
/* ------- STRAIGHT INSERTION SORTING-------*/
int straightInsSort(float p[], int size)
{
    int i, j, count=0; float x;

    for (i = 1; i < size; i++)
    {
        count++;
        x = p[i]; j = i - 1;
        while (x < p[j] && j >= 0)
        {
            p[j + 1] = p[j];
            j--;
        }
        p[j + 1] = x;
    }
    return count;
}
/*---------- BUBBLE SORTING -------------*/
int bubblesort(float p[], int size)
{
    int i; float sw; bool sorted; //int count = 0;
    int count = 0;
    do
    {
        sorted = true;
        for (i = 1; i < size; i++)
        {   count++;
            if (p[i - 1]>p[i])
            {        
                sw = p[i]; p[i] = p[i - 1]; p[i - 1] = sw;
                sorted = false;
                
            }
        }
    } while (!sorted);
    return count;
}
/*--------QUICK SORTING ---------*/
int quicksort(float p[], int left, int right)
{
    int l = left, r = right, i; 
    float x,t;
    //static int count = 0;

    if (left >= right) return 1;// count;
    
    printf("left = %d, right = %d\n", left, right);// demo, remove
    for (i = left; i <= right; i++)printf("%.0f  ", p[i]);//demo
    
    x = p[(l + r) / 2];    
    printf("\nx=%.2f\n", x); //demo
    
    do
    {
        while (p[l] < x)l++;
        while (p[r] > x)r--;
        printf("l = %d, r = %d\n", l, r); getchar();// demo, remove
        if (l > r)break;
        if (p[l] != p[r])
        {
            t = p[l]; p[l] = p[r]; p[r] = t; //count++;
        }
        for (i = left; i <= right; i++)printf("%.0f  ", p[i]);//demo
        getchar();// demo
        
    } while (++l < --r);
    quicksort(p, left, r);
    quicksort(p, l, right);
}
/*------------ QUICK SORTING USING POINTERS -----------*/
int Pquicksort(float* left, float* right)
{
    float *l = left, * r = right, x, t;

    if (l >= r) return 1;
    x = *(l + (r - l) / 2);
    do
    {
        while (*l < x)l++;
        while (*r > x)r--;
        if (l > r)break;
        if (*l != *r)
        {
            t = *l; *l = *r; *r = t;
        }
    } while (++l < --r);//++l <= --r 
    Pquicksort(left, r);
    Pquicksort(l, right);
}
/*-----------------------------------------------------*/
void  press_enter()
{
    printf("Press ENTER to continue");
    getchar();
    while (getchar() != '\n');
}
/*---------------------------------------------------*/
void displayresults(float q[], int size)
{
    int i;
    for (i = 0; i < size; i++) printf("%.0f  ", q[i]);
    printf("\n");
}
/*======== MAIN FUNCTION ========*/
void main()
{
    float p[8], q[8];
    int size, i, key;
   
    size = sizeof(p) / sizeof(float);

    srand(time(NULL));

    for (i = 0; i < size; i++)
    {
        p[i] = rand() % 100 * 1.0;
        q[i] = p[i];
        printf("%.0f  ", p[i]);
    }
    printf("\n");    

    do
    {
        system("cls");
        printf("Sorting methods, Data:"); displayresults(p, size);
        printf("1.With selection\n");
        printf("2.With Straigth insertion\n");
        printf("3.Bubble sort\n");
        printf("4.Quick sorting\n");
        printf("5.Quick sorting using pointers\n");
        printf("0.Exit\n");
        key = getchar();
        switch (key)
        {
        case '1':printf("count=%d\n", selectsort(q, size));
            displayresults(q, size);
            break;
        case '2':printf("count=%d\n", straightInsSort(q, size));
                 displayresults(q, size);
            break;
        case '3':printf("count=%d\n", bubblesort(q, size));
                 displayresults(q, size);
            break;
        case '4':quicksort(q, 0, size - 1);
                 displayresults(q, size);
            break;
        case '5':Pquicksort(q, (float*)(q + size - 1));
                 displayresults(q, size);
            break;
        case '0':break;
        };
        press_enter();
    } while (key != '0');

}