#include <stdlib.h>
#include <time.h>
#include <conio.h>
#include <iostream.h>
#include <graphics.h>

class Tarray {
  protected:
    int *farray, count;
    void Merge(int odkud, int a, int pokud);
    void Msort(int odkud, int pokud);
    void Qsort(int odkud, int pokud);
    void Swap(int i,j);
  public:
    Tarray(int n=0) {farray = new int[n]; count= n;};
    Tarray(Tarray &a) {count=a.count; farray= new int[count]; farray=a.farray;}; 
    ~Tarray() {delete []farray;};
    int &operator[](int n) {return farray[n];};
    void quicksort(void);
    void bubblesort(void);
    void mergesort(void);
};

void Tarray::mergesort(void)
{
  Msort(0,count-1);
}

void Tarray::Msort(int odkud, int pokud)
{ int a=(odkud+pokud)/2;
  if(odkud != pokud)
  {
    Msort(a+1,pokud);
    Msort(odkud,a);
    Merge(odkud,a,pokud);
  }
}

void Tarray::Merge(int odkud, int a, int pokud)
{ int i= odkud,j= a+1;
  Tarray B(count);
  for(int c= odkud;c<=pokud;c++)
    B[c]= farray[c];

  while((i<=a)||(j<=pokud))
    if((i>a)||((pokud>=j)&&(B[j]<=B[i])))
    {
      farray[j+i-a-1]=B[j];
      Sawp(j+i-a-1,j)
      j++;
    }
    else {
      farray[j+i-a-1]=B[i];
      Swap(j+i-a-1,i);
      i++;
    }
}

void Tarray::bubblesort(void)
{
  for(int i=0;i<count;i++)
    for(int j=count-2;j>=i;j--)
      if(farray[j]>farray[j+1])
		{
        int pom=farray[j];
        farray[j]= farray[j+1];
        farray[j+1]= pom;
        Swap(j,j+1);
      };
}

void Tarray::quicksort(void)
{
  Qsort(0, count-1);
}

void Tarray::Qsort(int odkud, int pokud)
{
  if(odkud<pokud)
  {
    int pivot= (farray[odkud] + farray[(pokud+odkud)/2] + farray[pokud])/3;
    int i= odkud, j= pokud;
    while(i<=j)
    {
      while(farray[i] < pivot)
        i++;
      while(farray[j] > pivot)
        j--;
      if (i <= j)
      {
        int pom= farray[i];
        farray[i]= farray[j];
        farray[j]= pom;
        Swap(i,j);
        i++;
        j--;
      }
    }
    Qsort(i,pokud);
    Qsort(odkud,j);
  }
}

void Tarray::Swap(int i,j)
{
  int old= getcolor();
  setcolor(0);
  line(i+10,10,i+10,farray[i]+10);
  line(j+10,10,j+10,farray[j]+10);
  setcolor(old);
  line(i+10,10,i+10,farray[j]+10);
  line(j+10,10,j+10,farray[i]+10);
}

void main(void)
{
  int c=100;
  Tarray a(c);
  randomize();
  clrscr();

  for(int i=0;i<c;i++)
    a[i]= random(100);
  for (int i=10;i<c+10;i++)
    line(i,10,i,a[i]+10);
  for(int i=0;i<c;i++)
    cout<<a[i]<<" ";
  cout<<"\n\n";

  a.quicksort();
  for(int i=0;i<c;i++)
    cout<<a[i]<<" ";
  getch();
}