#include<stdio.h>
#include <stdlib.h>
#include <time.h>
//#define MAX 60000l
#define MLD 1000000000.0
void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}
void printArray(int A[], int size)
{
    int i;
    for (i=0; i < size; i++){
        printf("%d ", A[i]);
}
        printf("\n");
}

int Partition (int A[], int p, int r)
{
    int x = A[r];
    int i = (p - 1);
    int j;
    for (j = p; j <= r; j++)
    {
        if (A[j] <= x)
        {
            i++;
            swap(&A[i], &A[j]);
        }
    }
    if(i<r)
    return i;
    else return i-1;
}
void QuickSort(int A[], int p, int r)
{
    if (p < r)
    {
        int q = Partition(A, p, r);
        QuickSort(A, p, q);
        QuickSort(A, q + 1, r);
    }
}
void BubbleSort(int A[], int n)
{
   int i, j;
   for (i = 0; i < n; i++)
       for (j = 0; j < n-i; j++)
           if (A[j] > A[j+1])
              swap(&A[j], &A[j+1]);
}
void BubbleQuickSort(int A[], int p, int r)
{
    if (p < r)
    {
        if(r<=1000)
        {
            BubbleSort(A,r);
        }
        else
        {
            int q = Partition(A, p, r);
            QuickSort(A, p, q);
            QuickSort(A, q + 1, r);
        }
    }
}

int main()
{printf("DANE LOSOWE\nrozmiar tablicy N|QuickSort|BubbleQuickSort\n");
struct timespec tp0, tp1;
    double Tn,Tn2;
    int n;

for(n=10000;n<1000000;n=n+10000)
   { srand( time(NULL));
    int i,j;
    int A[n];
    int A2[n];
    for(i=0; i<n; i++)
    {
        A[i] = rand()%n+1;
    }
    for(i=0;i<n;i++)
    {
        A2[i]=A[i];
    }

clock_gettime(CLOCK_PROCESS_CPUTIME_ID,&tp0);
QuickSort(A,0,n);
clock_gettime(CLOCK_PROCESS_CPUTIME_ID,&tp1);
Tn=(tp1.tv_sec+tp1.tv_nsec/MLD)-(tp0.tv_sec+tp0.tv_nsec/MLD);
clock_gettime(CLOCK_PROCESS_CPUTIME_ID,&tp0);
BubbleQuickSort(A2,0,n);
clock_gettime(CLOCK_PROCESS_CPUTIME_ID,&tp1);
Tn2=(tp1.tv_sec+tp1.tv_nsec/MLD)-(tp0.tv_sec+tp0.tv_nsec/MLD);
printf("%d            | %3.5lf | %3.5lf \n",n,Tn,Tn2);
}
    return 0;
}


#include<stdio.h>
#include <stdlib.h>
#include <time.h>
//#define MAX 60000l
#define MLD 1000000000.0
void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}
void printArray(int A[], int size)
{
    int i;
    for (i=0; i < size; i++){
        printf("%d ", A[i]);
}
        printf("\n");
}

int Partition (int A[], int p, int r)
{
    int x = A[r];
    int i = (p - 1);
    int j;
    for (j = p; j <= r; j++)
    {
        if (A[j] <= x)
        {
            i++;
            swap(&A[i], &A[j]);
        }
    }
    if(i<r)
    return i;
    else return i-1;
}
void QuickSort(int A[], int p, int r)
{
    if (p < r)
    {
        int q = Partition(A, p, r);
        QuickSort(A, p, q);
        QuickSort(A, q + 1, r);
    }
}
void BubbleSort(int A[], int n)
{
   int i, j;
   for (i = 0; i < n; i++)
       for (j = 0; j < n-i; j++)
           if (A[j] > A[j+1])
              swap(&A[j], &A[j+1]);
}
void BubbleQuickSort(int A[], int p, int r)
{
    if (p < r)
    {
        if(r<=1000)
        {
            BubbleSort(A,r);
        }
        else
        {
            int q = Partition(A, p, r);
            QuickSort(A, p, q);
            QuickSort(A, q + 1, r);
        }
    }
}

int main()
{printf("DANE NIEKORZYSTNE\nrozmiar tablicy N|QuickSort|BubbleQuickSort\n");
struct timespec tp0, tp1;
    double Tn,Tn2,Tn3,Tn4;
    int n;

for(n=100;n<50000;n=n+100)
   { srand( time(NULL));
    int i,j;
    int A[n];
    int A2[n];
    for(i=0; i<n; i++)
    {
        A[i] = rand()%n+1;
    }
    QuickSort(A,0,n);
        for(i=n-1,j=0;i>j;i--,j++)
    {
    swap(&A[j],&A[i]);}

    for(i=0;i<n;i++)
    {
        A2[i]=A[i];
    }
clock_gettime(CLOCK_PROCESS_CPUTIME_ID,&tp0);
QuickSort(A,0,n);
clock_gettime(CLOCK_PROCESS_CPUTIME_ID,&tp1);
Tn=(tp1.tv_sec+tp1.tv_nsec/MLD)-(tp0.tv_sec+tp0.tv_nsec/MLD);
clock_gettime(CLOCK_PROCESS_CPUTIME_ID,&tp0);
BubbleQuickSort(A2,0,n);
clock_gettime(CLOCK_PROCESS_CPUTIME_ID,&tp1);
Tn2=(tp1.tv_sec+tp1.tv_nsec/MLD)-(tp0.tv_sec+tp0.tv_nsec/MLD);
printf("%d            | %3.5lf | %3.5lf \n",n,Tn,Tn2);
}
    return 0;
}