LAB 1

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

//-----------------------------------------------------------------------------------sorts functions------------------------------------------------------------------------------------
void bubble_sort( int tab[], int n)
{
    int step;
    int temp;
    int i;
    for( step = 0; step < n - 1; ++ step)
    for(i = 0; i < n - step - 1;++i)
    {
        if(tab[i] > tab[i+1])
        {
            temp = tab[i];
            tab[i] = tab[i+1];
            tab[i+1] =  temp;

        }
    }
}
void re_bubble_sort( int tab[], int n)
{
    int step;
    int temp;
    int i;
    for( step = 0; step < n - 1; ++step)
    for(i = 0; i < n - step - 1; ++i)
    {
        if(tab[i]<tab[i+1])
        {
            temp = tab[i];
            tab[i]=tab[i+1];
            tab[i+1]= temp;

        }
    }
}


void insertion_sort(int tab[], int n) //insertion srt starts at 2_nd element
{
   int i, key, j;
   for (i = 1; i <= n - 1; i++)
   {
       key = i;

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

   }
}


void re_insertion_sort( int tab[], int n)
{
    int i, key, j;
   for (i = 1; i <= n - 1; i++)
   {
       key = i;

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

   }


}

void selection_sort (int tab[], int n)
{
    int k ,j , minimum_position, swap;
    for (k = 0; k < (n - 1); k++)
    {
        minimum_position = k;
        for(j = k + 1; j < n; j++)
        {
            if(tab[j]< tab[minimum_position])
            minimum_position = j;
        }
        //swap(tab[k], tab[minimum_position]);
        swap = tab[k];
        tab[k]= tab[minimum_position];
        tab[minimum_position]= swap;
    }
}

void re_selection_sort (int tab[], int n)
{
    int k ,j , minimum_position, swap;
    for (k = 0; k < n; k++)
    {
        minimum_position = k;
        for(j = k + 1; j < n; j++)
        {
            if(tab[j]> tab[minimum_position])
            minimum_position = j;
        }
        //swap(tab[k], tab[minimum_position]);
        swap = tab[k];
        tab[k]= tab[minimum_position];
        tab[minimum_position]= swap;
    }
}

//-----------------------------------------------------------------------printing the array-------------------------------------------------------------

void print_tab(int tab[], int n)
{
   int i;
   for (i = 0; i < n; i++)
       printf("%d", tab[i]);
   printf("\n");
}

//------------------------------------------------------------------------time---------------------------------------------------------------------------

 void time_Check(float Start, float Stop )
{
    float Time;
    Time = (Stop-Start) /  CLOCKS_PER_SEC;
    printf("Sorting time:\n %f  s ", Time);
}
 //----------------------------------------------------------------------generate numbers------------------------------------------------------------------

void numbers_generate(int tab[], int n)
{
    int i ;
    srand(time(NULL)); //randomize speed
    for(i = 0; i < n; i++)
    {
        tab[i] = rand()%n;
    }
}

//------------------------------------------------------------------------swap function--------------------------------------------------------------------

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



//----------------------------------------------------------------------main function------------------------------------------------------------------------

 int main ()
{
    int numbers[1024];
    float start;
    float stop;
    int n;
    n = (sizeof(numbers))/(sizeof(int)); //find the size of array

    printf("BUBBLE SORT\n");
    numbers_generate(numbers, n);
    start = clock();
    bubble_sort(numbers, n);
    stop = clock();
    time_Check(start, stop);
    printf("\n\n");

    printf("INSERTION SORT\n");
    numbers_generate(numbers, n);
    start = clock();
    insertion_sort(numbers, n);
    stop = clock();
    time_Check(start, stop);
    printf("\n\n");

    printf("SELECTION SORT\n");
    numbers_generate(numbers, n);
    start = clock();
    selection_sort(numbers, n);
    stop = clock();
    time_Check(start, stop);
    printf("\n\n");

    printf("RE-BUBBLE SORT\n");
    numbers_generate(numbers, n);
    start = clock();
    re_bubble_sort(numbers, n);
    stop = clock();
    time_Check(start, stop);
    printf("\n\n");

    printf("RE-INSERTION SORT\n");
    numbers_generate(numbers, n);
    start = clock();
    re_insertion_sort(numbers, n);
    stop = clock();
    time_Check(start, stop);
    printf("\n\n");

    printf("RE-SELECTION SORT\n");
    numbers_generate(numbers, n);
    start = clock();
    re_selection_sort(numbers, n);
    stop = clock();
    time_Check(start, stop);
    printf("\n\n");


    //---------------------------------------------------------Count the number of swaps  for bubble sort, n = 2^16--------------------------------

    int Numbers[65536];//2^16
    int k;
    int i ;
    int j;
    k = (sizeof(Numbers) / sizeof(int));
    numbers_generate(Numbers, k);
    bool swapped = false;
    int count_swap = 0;
    int no_swap = 0;

    do
    {
            for( i = 0; i < k-1; i++)
        {
            for( j = 0; j < k-i-1; j++)
            {
                if(Numbers[j] > Numbers[j+1])
                {
                    swap(&Numbers[j], &Numbers[j+1]);
                    swapped = true;
                    count_swap++;
                }
                else
                {
                    swapped = false;
                    no_swap++;
                }
            }
        }
    }while(swapped == true);
    printf("Bubble sort \n");
    printf("\n\n");
    printf( "Number of swaps: %d" , count_swap );
    printf("\n\n");
    printf("Number of no swaps: %d" , no_swap );
    printf("\n\n");
      return 0;
}
//the best case scenario is when all array is already sorted
//the worst case scenario is then the array is reverse sorted