#include <cstdlib>
#include <iostream>

using namespace std;



void bubbleSort_flag(int a[],int from, int n,  bool reverse)
{
   int i, j, temp, flag;
   for(i=n-1; i>from; i--)
   {
     flag = 1;
     for(j=from; i>j; j++)
     {
       if(reverse==false)
       {                         
           if(a[j]>a[j+1])
           {
             flag = 0;
             temp = a[j];
             a[j] = a[j+1];
             a[j+1] = temp;
           }
       }else
       {
           if(a[j]<a[j+1])
           {
             flag = 0;
             temp = a[j];
             a[j] = a[j+1];
             a[j+1] = temp;
           }
       }
       
     }
     //out this block when flag is true
     //i.e. inner loop performed no swaps, so the list is already sorted
     if(flag)
       break;
   }
}

void print_array(int a[],int size)
{
   int i;
   cout<<"[";
   for(i=0;i<size;i++)
   {
     cout<<a[i]<<",";
   }  
   cout<<"]\n";
}



void petorki(void)
{
    int  a[20]={1,5,3,2,15,225,23,10,1,6,8,4,7,88,231,33,554,113,143,567}; 
    int i;
     
    //sort the whole array 
    bubbleSort_flag(a,0,20,false);
   
    cout<<"Array before is:\n";
    print_array(a,20);

    //reverse sort every even 5
    for(i=5;i<20;i=i+5)
    {
      cout<<i<<",";
      if((i/5)%2!=0)
      {        
         bubbleSort_flag(a,i,i+5,true);
      }               
    }
   
   cout<<"\nArray after is:\n";
   print_array(a,20);
   
     
}


void posledna(void)
{
    int  a[20]={10,0,3,2,15,225,23,20,1,6,8,4,7,88,231,33,554,113,143,999}; 
    int  b[10]={0,0,0,0,0,0,0,0,0,0};
    int i, j, temp, flag, prev,next, from;

    print_array(a,20);

    for(i=19; i>0; i--)
    {
      flag = 1;
      for(j=0; i>j; j++)
      {   
          if(a[j]>=10)
               prev=a[j]%10;
          else if(a[j]<10)
               prev=a[j];

          if(a[j+1]>=10)
               next=a[j+1]%10;
          else if(a[j+1]<10)
               next=a[j+1];
               
           if(prev > next)
           {        
             flag = 0;
             temp = a[j];
             a[j] = a[j+1];
             a[j+1] = temp;
           }
       }
     }
    
    print_array(a,20);
    
    
    for(i=0;i<20;i++)
    {
      if(a[i]>=10)
         b[a[i]%10]++;
      else if(a[i]<10)
         b[a[i]]++;                     
    }
    print_array(b,10);
    
    from=0;
    for(i=0;i<10;i+=b[i])
    {
       int size;
       size=b[i];
       bubbleSort_flag(a,from,size,false); 
       from+=b[i];                 
    }
    
    print_array(a,20);
    
}

int main(int argc, char *argv[])
{
    //petorki();
    //posledna();
    system("PAUSE");
    return EXIT_SUCCESS;
}