Untitled

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

LARGE_INTEGER tick1, tick2, freq;


void Swap(int Table[],int a,int b ){ //Wymiana
     int temp;
     temp = Table[a];
     Table[a] = Table[b];
     Table[b] = temp;
     }

void Random(int Table[],int amount)//Generator -> Losowe
     {
                int i;
                for(i=0;i<amount;i++){Table[i]=rand();}
     }

void Upper(int Table[], int amount)// Generator -> Rosnące
     {
     int i;
     for(i=0;i<amount;i++){Table[i]=i;}
     }

void Lower(int Table[], int amount)//Generator -> Malejące
     {
     int i;
     for(i=0;i<amount;i++){Table[i]=amount-i;}
     }

void Still(int Table[], int amount)// Generator -> Stałe
     {
     int i;
     for(i=amount-1;i>=0;i--){Table[i]=2;}
     }

void AShape(int Table[], int amount)//Generator -> Rosnąco-malejące
     {
     int i;
     for(i=0;i<=(amount-1)/2;i++){Table[i]=2*i;}
     for(i=(amount-1)/2+1;i<amount;i++){Table[i]=Table[(amount-i-1)]-1;}
     }

void VShape(int Table[], int amount)//Generator -> Malejąco-rosnące
     {
     int i;
     for(i=0;i<=(amount-1)/2;i++){Table[i]=-2*i+amount;}
     for(i=(amount-1)/2+1;i<amount;i++){Table[i]=Table[(amount-i-1)]+1;}
     }


void QSort(int Table[],int amount, int l, int p) // implementacja z Wirth-a
    {
              int i, j, x, w,a;
              i=l;
              j=p;
              x=Table[(l+p)/2];
              do{
                 while(Table[i]<x){i++;}
                 while(x<Table[j]){j--;}
                 if(i<=j){
                          Swap(Table,i,j);
                          i++;
                          j--;
                          }
              }while(i<=j);
              if(l<j){QSort(Table,amount,l,j);}
              if(i<p){QSort(Table,amount,i,p);}
    }

void Merge(int low,int mid,int high,int Table[],int amount){
 int h,i,j,b[amount],k;

 h=low;
 i=low;
 j=mid+1;

 while((h<=mid)&&(j<=high))
                           {
                           if(Table[h]<=Table[j])
                                                 {
                                                  b[i]=Table[h];
                                                  h++;
                                                  }
                           else
                               {
                                b[i]=Table[j];
                                j++;
                                }
                           i++;
                           }
 if(h>mid)
          {
           for(k=j;k<=high;k++)
                               {
                                b[i]=Table[k];
                                i++;
                                }
          }
 else
     {
      for(k=h;k<=mid;k++)
                         {
                          b[i]=Table[k];
                          i++;
                          }
      }
 for(k=low;k<=high;k++)
                        Table[k]=b[k];
}

void MergeSort(int Table[],int amount,int low,int high)
{
 int mid;
  if(low<high)
               {
                mid=(low+high)/2;
                MergeSort(Table,amount,low,mid);
                MergeSort(Table,amount,mid+1,high);
                Merge(low,mid,high,Table,amount);
                }
}


void Heapify(int Table[], int i, int Heapsize)
    {
     int Left = 2 * i + 1 , Right = 2 * (i + 1) , Largest;

     if((Left < Heapsize) && (Table[Left] > Table[i]))
             {Largest = Left;}
             else
             {Largest = i;}

     if((Right < Heapsize) && (Table[Right] > Table[Largest]))
              {Largest = Right;}

     if(Largest != i)
                {Swap(Table,i,Largest);
                Heapify(Table,Largest,Heapsize);}
    }

void BuildHeap(int Table[],int amount)
     {
      int i;
      int Heapsize = amount;
      for(i = ceil((amount+1)/2-1); i >= 0; i--)
            {
            Heapify(Table,i, Heapsize);
            }
     }

void HeapSort(int Table[],int amount)
    {
     int i,Heapsize=amount;

     BuildHeap(Table, amount);
     for(i = amount-1; i > 0 ; i--)
           {
                       Swap(Table,0,i);
                       Heapsize--;
                       Heapify(Table,0, Heapsize);
           }

    }

int main(int argc, char *argv[])
{
  int i, Table[200000], amount;
  float Results;
  int *Table1 = (int*)malloc(200000 * sizeof(int));
  QueryPerformanceFrequency(&freq);
  srand ( time(NULL) );
  printf("Random\n");
  printf("QS\n");
  Random(Table,150000);
  for(i=0;i<150000;i++){Table1[i]=Table[i];}
  for(amount=0;amount<=150000;amount+=10000){ //Random

                                          QueryPerformanceCounter(&tick1);
                                          QSort(Table,amount,0,amount-1);
                                          QueryPerformanceCounter(&tick2);
                                           printf("%d\t",amount);
                                           printf( "%f\n",1000* ( tick2.QuadPart - tick1.QuadPart ) / (float) freq.QuadPart );
                                           for(i=0;i<150000;i++){Table[i]=Table1[i];}
                                          }
  printf("HS\n");
  for(amount=0;amount<=150000;amount+=10000){
                                          QueryPerformanceCounter(&tick1);
                                          HeapSort(Table,amount);
                                          QueryPerformanceCounter(&tick2);
                                           printf("%d\t",amount);
                                           printf( "%f\n",1000* ( tick2.QuadPart - tick1.QuadPart ) / (float) freq.QuadPart );
                                           for(i=0;i<150000;i++){Table[i]=Table1[i];}
                                          }
  free(Table1);
  printf("MS\n");
  for(amount=0;amount<=150000;amount+=10000){
                                          QueryPerformanceCounter(&tick1);
                                          MergeSort(Table,amount,0,amount-1);
                                          QueryPerformanceCounter(&tick2);
                                           printf("%d\t",amount);
                                           printf( "%f\n",1000* ( tick2.QuadPart - tick1.QuadPart ) / (float) freq.QuadPart );
                                          }
  printf("Still\n");
  printf("QS\n");
  for(amount=0;amount<=150000;amount+=10000){ //Still
                                          Still(Table,amount);
                                          QueryPerformanceCounter(&tick1);
                                          QSort(Table,amount,0,amount-1);
                                          QueryPerformanceCounter(&tick2);
                                           printf("%d\t",amount);
                                           printf( "%f\n",1000* ( tick2.QuadPart - tick1.QuadPart ) / (float) freq.QuadPart );
                                          }
  printf("HS\n");
  for(amount=0;amount<=150000;amount+=10000){
                                          Still(Table,amount);
                                          QueryPerformanceCounter(&tick1);
                                          HeapSort(Table,amount);
                                          QueryPerformanceCounter(&tick2);
                                           printf("%d\t",amount);
                                           printf( "%f\n",1000* ( tick2.QuadPart - tick1.QuadPart ) / (float) freq.QuadPart );
                                          }
  printf("MS\n");
  for(amount=0;amount<=150000;amount+=10000){
                                          Still(Table,amount);
                                          QueryPerformanceCounter(&tick1);
                                          MergeSort(Table,amount,0,amount-1);
                                          QueryPerformanceCounter(&tick2);
                                           printf("%d\t",amount);
                                           printf( "%f\n",1000* ( tick2.QuadPart - tick1.QuadPart ) / (float) freq.QuadPart );
                                          }
  printf("Upper\n");
  printf("QS\n");
  for(amount=0;amount<=150000;amount+=10000){//Upper
                                          Upper(Table,amount);
                                          QueryPerformanceCounter(&tick1);
                                          QSort(Table,amount,0,amount-1);
                                          QueryPerformanceCounter(&tick2);
                                           printf("%d\t",amount);
                                           printf( "%f\n",1000* ( tick2.QuadPart - tick1.QuadPart ) / (float) freq.QuadPart );
                                          }
  printf("HS\n");
  for(amount=0;amount<=150000;amount+=10000){
                                          Upper(Table,amount);
                                          QueryPerformanceCounter(&tick1);
                                          HeapSort(Table,amount);
                                          QueryPerformanceCounter(&tick2);
                                           printf("%d\t",amount);
                                           printf( "%f\n",1000* ( tick2.QuadPart - tick1.QuadPart ) / (float) freq.QuadPart );
                                          }
  printf("MS\n");
  for(amount=0;amount<=150000;amount+=10000){
                                          Upper(Table,amount);
                                          QueryPerformanceCounter(&tick1);
                                          MergeSort(Table,amount,0,amount-1);
                                          QueryPerformanceCounter(&tick2);
                                           printf("%d\t",amount);
                                           printf( "%f\n",1000* ( tick2.QuadPart - tick1.QuadPart ) / (float) freq.QuadPart );
                                          }
  printf("Lower\n");
  printf("QS\n");
  for(amount=0;amount<=150000;amount+=10000){//Lower
                                          Lower(Table,amount);
                                          QueryPerformanceCounter(&tick1);
                                          QSort(Table,amount,0,amount-1);
                                          QueryPerformanceCounter(&tick2);
                                           printf("%d\t",amount);
                                           printf( "%f\n",1000* ( tick2.QuadPart - tick1.QuadPart ) / (float) freq.QuadPart );
                                          }
  printf("HS\n");
  for(amount=0;amount<=150000;amount+=10000){
                                          Lower(Table,amount);
                                          QueryPerformanceCounter(&tick1);
                                          HeapSort(Table,amount);
                                          QueryPerformanceCounter(&tick2);
                                           printf("%d\t",amount);
                                           printf( "%f\n",1000* ( tick2.QuadPart - tick1.QuadPart ) / (float) freq.QuadPart );
                                          }
  printf("MS\n");
  for(amount=0;amount<=150000;amount+=10000){
                                          Lower(Table,amount);
                                          QueryPerformanceCounter(&tick1);
                                          MergeSort(Table,amount,0,amount-1);
                                          QueryPerformanceCounter(&tick2);
                                           printf("%d\t",amount);
                                           printf( "%f\n",1000* ( tick2.QuadPart - tick1.QuadPart ) / (float) freq.QuadPart );
                                          }
  printf("AShape\n");
  printf("QS\n");
  for(amount=0;amount<=150000;amount+=10000){//AShape
                                          AShape(Table,amount);
                                          QueryPerformanceCounter(&tick1);
                                          QSort(Table,amount,0,amount-1);
                                          QueryPerformanceCounter(&tick2);
                                           printf("%d\t",amount);
                                           printf( "%f\n",1000* ( tick2.QuadPart - tick1.QuadPart ) / (float) freq.QuadPart );
                                          }
  printf("HS\n");
  for(amount=0;amount<=150000;amount+=10000){
                                          AShape(Table,amount);
                                          QueryPerformanceCounter(&tick1);
                                          HeapSort(Table,amount);
                                          QueryPerformanceCounter(&tick2);
                                           printf("%d\t",amount);
                                           printf( "%f\n",1000* ( tick2.QuadPart - tick1.QuadPart ) / (float) freq.QuadPart );
                                          }
  printf("MS\n");
  for(amount=0;amount<=150000;amount+=10000){
                                          AShape(Table,amount);
                                          QueryPerformanceCounter(&tick1);
                                          MergeSort(Table,amount,0,amount-1);
                                          QueryPerformanceCounter(&tick2);
                                           printf("%d\t",amount);
                                           printf( "%f\n",1000* ( tick2.QuadPart - tick1.QuadPart ) / (float) freq.QuadPart );
                                          }
  printf("VShape\n");
  printf("QS\n");
    for(amount=0;amount<=150000;amount+=10000){//VShape
                                          VShape(Table,amount);
                                          QueryPerformanceCounter(&tick1);
                                          QSort(Table,amount,0,amount-1);
                                          QueryPerformanceCounter(&tick2);
                                           printf("%d\t",amount);
                                           printf( "%f\n",1000* ( tick2.QuadPart - tick1.QuadPart ) / (float) freq.QuadPart );
                                          }
  printf("HS\n");
  for(amount=0;amount<=150000;amount+=10000){
                                          VShape(Table,amount);
                                          QueryPerformanceCounter(&tick1);
                                          HeapSort(Table,amount);
                                          QueryPerformanceCounter(&tick2);
                                           printf("%d\t",amount);
                                           printf( "%f\n",1000* ( tick2.QuadPart - tick1.QuadPart ) / (float) freq.QuadPart );
                                          }
  printf("MS\n");
  for(amount=0;amount<=150000;amount+=10000){
                                          VShape(Table,amount);
                                          QueryPerformanceCounter(&tick1);
                                          MergeSort(Table,amount,0,amount-1);
                                          QueryPerformanceCounter(&tick2);
                                           printf("%d\t",amount);
                                           printf( "%f\n",1000* ( tick2.QuadPart - tick1.QuadPart ) / (float) freq.QuadPart );
                                          }
  system("PAUSE");
  return 0;
}