//sortirovka
#include <iostream.h>
#include <fstream.h>
#include <iomanip.h>

template <class Item>
void exch(Item &x, Item &y)
{ Item t = x; x = y; y = t; }

template <class Item>
void compexch (Item &A, Item &B)
{ if (B < A) exch(A, B) ; }

template <class Item>
void Printarray (Item a[],int l){
   // int c;if((c>=0)&&(c<1000)){c=4;}if((c>=1000)&&(c<10000)){c=5;}if((c>=10000)&&(c<100000)){c=6;}else{c=7;}
    for(int i=0;i<l;i++){
        cout<<setw(7);
        cout<<a[i];
        if(i%11==0){
            cout<<endl;
            }
        }

    }

//vyborom
template <class Item>
void selection (Item a[], int l, int r) {
      for (int i = 0; i < r; i++) {
          int min = i ;
          for (int j = i+1; j <= r; j++){
              if (a[j] < a [min]) min = j;
              exch(a[i],a[min]);
              }
          }
      }

template <class Item>
void insertion (Item a[], int l, int r) {
     int i;
     for (i = r; i > l; i--)
        compexch(a[i-1],a[i]);
        for (i = l+2; i <= r; i++) {
            int j = i; Item v = a[i];
            while (v < a[j-1]) {
                a[j] = a[j-1];
                j --;
                }
            a[j] = v;
            }
        }

template <class Item>
void bubble (Item a[],int l,int r){
    for (int i = l; i < r; i++)
        for (int j = r; j > i; j--)
            compexch(a[j-1],a[j]);
    }

template <class Item>
void shellsort(Item a[] , int l, int r)
{ int h;
for (h = 1; h <= (r-l)/9; h = 3*h+l) ;
for ( ; h > 0; h /= 3)
    for (int i = l+h; i <= r; i++)
        { int j = i; Item v = a[i] ;
        while (j >= l+h && v < a[j-h])
            { a[j] = a[j-h]; j -= h; }
        a[j] = v;
        }
}

#define MAXSTACK 2048

template<class T>
void quickSortR(T* a, long N) {
//N is last element
  long i = 0, j = N;
  T temp, p;

  p = a[ N>>1 ];

  do {
    while ( a[i] < p ) i++;
    while ( a[j] > p ) j--;

    if (i <= j) {
      temp = a[i]; a[i] = a[j]; a[j] = temp;
      i++; j--;
    }
  } while ( i<=j );


  if ( j > 0 ) quickSortR(a, j);
  if ( N > i ) quickSortR(a+i, N-i);
}

template<class T>
void qSortI(T a[], long size) {
  long i, j;
  long lb, ub;
  long lbstack[MAXSTACK], ubstack[MAXSTACK];
  long stackpos = 1;
  long ppos;
  T pivot;
  T temp;
  lbstack[1] = 0;
  ubstack[1] = size-1;
  do {
    lb = lbstack[ stackpos ];
    ub = ubstack[ stackpos ];
    stackpos--;
    do {
      ppos = ( lb + ub ) >> 1;
      i = lb; j = ub; pivot = a[ppos];
      do {
        while ( a[i] < pivot ) i++;
        while ( pivot < a[j] ) j--;
        if ( i <= j ) {
          temp = a[i]; a[i] = a[j]; a[j] = temp;
          i++; j--;
        }
      } while ( i <= j );
      if ( i < ppos ) {
        if ( i < ub ) {
          stackpos++;
          lbstack[ stackpos ] = i;
          ubstack[ stackpos ] = ub;
        }
        ub = j; } else {
        if ( j > lb ) {
          stackpos++;
          lbstack[ stackpos ] = lb;
          ubstack[ stackpos ] = j;
        }
        lb = i;
      }
    } while ( lb < ub );
  } while ( stackpos != 0 );
}

main () {
ifstream fin ("input.txt");
    long long int N,choose;
    cout<<"It's sorting program...\nChoose settings of input : \nEnter 1 to use this window to input\nor\n      2 to use input.txt : ";
    cin>>choose;
    cout<<"Enter number of elements in array : ";
    cin>>N;
    long long int a[N];
    cout<<"Enter elements : "<<endl;

    if (choose==1){
    for (int i=0;i<N;i++){
        cin>>a[i];
        }
    }
    else{
    for (int i=0;i<N;i++){
        fin>>a[i];
        }

        }
    cout<<"Sort method : \n1)selection\n2)insertion\n3)bubble\n4)shell\n5)quick(mod)\n6)quick";
    cin>>choose;
    switch (choose){
        case 1:selection(a,0,N-1);break;
        case 2:insertion(a,0,N-1);break;
        case 3:bubble(a,0,N-1);break;
        case 4:shellsort(a,0,N-1);break;
        case 5:qSortI(a,N);break;
        case 6:quickSortR(a,N-1);break;
        }
cout<<"                 sorting ended"<<endl<<"enter any key to print result : ";
cin>>choose;
    Printarray(a,N);
fin.close();
    system("pause");
    return 0;
     }