#include <iostream>
#include <string>
#include <fstream>
#include <stdlib.h>

using namespace std;

void swap (int &x, int &y) {int z=x;x=y;y=z;}

void qSort( long int* A, int n, int& compres) {

     int i=1;
      int j=1;
      int pivot=n-1;//0,median

      if (n>1) {

     int x=A[pivot];
     compres+=n-1;

      for (;j<n;j++){
      if(i<j && x>A[j]){
        swap (A[j],A[i]);
        i++;
        }
      if(i==j && x> A[j]) i++;
        }
      swap (A[pivot],A[i-1]);

      long int *b=A+i;

      qSort (A, i-1, compres);
      qSort (b, n-i, compres);

   }


  }


int main(int argc, char **argv)
{
    fstream myReadFile;
 myReadFile.open("array1.txt");
 long int *numbers;
 int size=23;
 numbers = new long int[size];
 int count=0;
 int compres=0;
 string read;

 if (myReadFile.is_open()) {
 while (!myReadFile.eof()) {
   myReadFile >> read;
   numbers[count]=atoi(read.c_str());
    count++;
}
}


    qSort (numbers,size,compres);
    for (int i=0;i<size;i++)
    cout<<i<<" "<<numbers[i]<<endl;

    cout<<endl<<endl<<compres;

    return 0;
}