#include <iostream>
#include <stdlib.h>
#include <ctime>
#include <cmath>
#include <windows.h>

using namespace std;

const int TAB_SIZE = 100;
const int MAX_VAL = 100;

int tab_1[TAB_SIZE][TAB_SIZE];
int tab_2[TAB_SIZE][TAB_SIZE];
int tab_3[TAB_SIZE][TAB_SIZE];

void _w(int tab[TAB_SIZE][TAB_SIZE], int index, int val)
{
 int y = index/TAB_SIZE;
 //cout << "y = " << y << endl;
 int x = index - (y*TAB_SIZE);
 //cout << "y = " << x << endl;
 tab[y][x] = val;        
}    

int& _r(int tab[TAB_SIZE][TAB_SIZE], int index)
{
 int y = index/TAB_SIZE;
 //cout << "y = " << y << endl;
 int x = index - (y*TAB_SIZE);
 //cout << "y = " << x << endl;
 return tab[y][x];
}    

void pisz_tab(int tab[TAB_SIZE][TAB_SIZE])
{
    cout << endl << endl;
    cout << "Zawartosc tablicy:" <<endl;
    for(int y=0; y<TAB_SIZE; y++)
    {
        for(int x=0; x<TAB_SIZE; x++)
        {
           cout << tab[y][x] << " ";    
        }    
        cout << endl;
    }    
    cout << endl << endl;
}    

void babel(int tab[TAB_SIZE][TAB_SIZE], int n=TAB_SIZE*TAB_SIZE)
{
   for (int i=0; i<n; i++)
   {
      for (int j=0; j<n-1; j++)
      {
         if (_r(tab,j)>_r(tab,j+1))
         {
            int tmp;
            tmp = _r(tab,j);
            _w(tab, j, _r(tab, j+1));
            //tab[j] = tab[j+1];
            _w(tab, j+1, tmp);
            //tab[j+1] = tmp;
         }
      }
   }
}

void zamiana(int &a, int &b)
{
 int tmp(a);
 a = b;
 b = tmp;    
}    

void qsort (int tab[TAB_SIZE][TAB_SIZE], int left=0, int right=TAB_SIZE*TAB_SIZE)
{
  if (left < right)
 {
  int m=left;
  for (int i=left+1;i<right;i++)
    if (_r(tab, i) < _r(tab, left))
    {
        zamiana(_r(tab, ++m), _r(tab, i));    
    }   
  
  zamiana(_r(tab, left), _r(tab, m));  

  qsort (tab,left,m);
  qsort (tab,m+1,right);
  }
}

void countingsort(int tab[TAB_SIZE][TAB_SIZE], int n=TAB_SIZE*TAB_SIZE) 
{
const int k = MAX_VAL;             // elementami tablicy T są liczby całkowite z 
                              // z przedziału 1..77
int TPom[k];                  // zawiera ilość elementów o danej wartości

int i;  // pomocnicza zmienna (indeks)

// wyzerowanie pomocniczej tablicy
  for (i = 0 ; i < k ; i++)
    TPom[i] = 0;

// zliczenie elementów o danej wartości
  for (i = 0 ; i < n ; i++)
    TPom[_r(tab,i)] += 1;

// w tym miejscu możemy przepisać dane znowu do tablicy początkowej
  int j, l = 0;
  for (i = 0 ; i < k ; i++)
    for (j = 0 ; j < TPom[i] ; j++)
    {
       _w(tab, l, i);      // miejsce w tablicy pomocniczej określa wartość zmiennej
       l++;
    }    
}    

void generujTablice()
{
/*
    wylosowanie wartości i od razu spisanie ich do 
    trzech tablic: potrzebne są trzy tablice, aby 
    móc przeprowadzić test sortowania mając idealnie
    ułożone dane dla każdej z 3 metod.
  */
  for(int y=0; y<TAB_SIZE; y++)
  {
    for(int x=0; x<TAB_SIZE; x++)
    {
        tab_1[y][x] = tab_2[y][x] = tab_3[y][x] = rand()%MAX_VAL;
    }   
  }    
} 

void zmierz_qs()
{
    DWORD t_start = GetTickCount();
    qsort(tab_1);
    DWORD t_end = GetTickCount();
    cout << "QuickSort: \t"<< t_end - t_start << endl;
}   

void zmierz_babel()
{
    DWORD t_start = GetTickCount();
    babel(tab_2);
    DWORD t_end = GetTickCount();
    cout << "Babelkowe: \t"<< t_end - t_start << endl;    
}        

void zmierz_counting()
{
    DWORD t_start = GetTickCount();
    countingsort(tab_3);
    DWORD t_end = GetTickCount();
    cout << "Przez zliczanie: \t"<< t_end - t_start << endl;    
}        


int main(int argc, char *argv[])
{
  //inicjalizacja generatora liczb losowych
  srand(time(0));
  
  generujTablice();   
  
  cout << "Tablica nieposortowana:" << endl;
  //pisz_tab(tab_1);
  
  
  //_w(tab_1, 13, -10);
  //pisz_tab(tab_1);
  //countingsort(tab_2);
  zmierz_qs();
  zmierz_babel();
  zmierz_counting();
  //pisz_tab(tab_1);
  
  
  system("PAUSE");	
  return 0;
}