//------------------------------------------------------------------------------
#pragma  hdrstop
#pragma  argsused
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
//------------------------------------------------------------------------------
 void sort1r(float *arr,int l,int r,int opB)
{
      int i=l, j=r, d, m=arr[(l+r)/2];
      while(i<=j)
    {
            for(i = l; arr[i]<m; i++);
            for(j = r; arr[j]>m; j--);
            if(i<=j)
            {
               d=arr[i];
               arr[i++]=arr[j];
               arr[j--]=d;
               opB++;
            }
    }
    if(l<j) sort1r(arr,l,j,opB);
    if(i<r) sort1r(arr,i,r,opB);
}
//------------------------------------------------------------------------------
 void sort2r(int *arr, int a, int b)
{
      int c, i, j, mode;
      double sr=0;

      if(a>=b) return;
      for (i = a; i <= b; ++i)
           sr+=arr[i];
           sr=sr/(b-a+1);

      for (i=a, j=b; i <= j;) {
           if (arr[i] < sr) { i++; continue; }
           if (arr[j] >= sr) { j--; continue; }

           c = arr[i];
           arr[i] = arr[j];
           arr[j] = c;

           i++,j--;
       }
      if (i==a) return;
          sort2r(arr,a,j);
          sort2r(arr,i,b);
}
//------------------------------------------------------------------------------
 int main(void)
{
     int a, b, i, j, size, opA = 0, opB = 0, min, buf;
     float A[100], B[100], key = NULL;

     printf("Size of array: ");
     scanf("%d",&size);

     printf("Elements of Array: \n");
     for(i = 0; i < size; ++i) {
         printf("A[%d] = ", i+1);
         scanf("%f", &A[i]);
         B[i] = A[i];
     }

     printf("1th array:\n");
     printf("1. Metod Vstavki \n");
     printf("2. Metod Bul'bashok\n");
     printf("3. Metod Vibora\n");
     //printf("4. Exit\n");
     printf("Vash vibir?: ");
     scanf("%d", &a);

     printf("~~~~~~~~~~~~~~~\n");

     printf("2th array: \n");
     printf("1. Metod Hoara\n");
     printf("2. Metod Rekursivnogo Rozdilu\n");
     //printf("3. Exit\n");
     printf("Vash vibir?: ");
     scanf("%d", &b);

     switch (a) {
             case 1:
                    for(i = 0; i < size; ++i) { // 1) Ìåòîä Âñòàâêè;
                        j = i - 1 ;
                        key = A[i];
                    while(A[j] > key && j >= 0) {
                          A[j+1] = A[j];
                          j -= 1;
                          opA++;
                    }
                          A[j+1] = key;
                    }
                    break;
             case 2:
                    for(i = size - 1; i >= 0; --i) {
                        for(j = 0; j < i; ++j) {
                            int tmp = 0;
                            if (A[j] > A[j + 1])
                            {
                                tmp = A[j];
                                A[j] = A[j + 1];
                                A[j + 1] = tmp;
                            }
                        }
                    }
                    break;
             case 3:
                    for(i = 0; i < size - 1; ++i) {
                        min = i;
                        for(j = i + 1; j < size; ++j) {
                            if(A[j] < A[min]) {
                               min = j;
                            }
                        }
                        buf = A[i];
                        A[i] = A[min];
                        A[min] = buf;
                    }
                    break;
     }

     switch (b) {
             case 1:
                    sort1r(B,0,size-1,opB);
                    break;
             case 2:
                    sort2r(B,0,size-1);
                    break;
     }
//------------------------------------------------------------------------------
     for(i = 0; i < size; ++i) {
         printf("|A[%d] = %f|\n", i+1, A[i]);
     }
     printf("|~~~~~~~~~~~~~~~|\n");
     for(i = 0; i < size; ++i) {
         printf("|B[%d] = %f|\n", i+1, B[i]);
     }
     printf("|opA = %d opB = %d|",opA, opB);

        getch();
        return 0;
}
//------------------------------------------------------------------------------