#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int nc, nc_clever;

int compare(int **x, int a, int *p, int d){
  int j;
  for(j=0; j<d; j++){
    nc++;
    if(x[a][j] < p[j])
      return -1;
    if(x[a][j] > p[j])
      return 1;
  }
  return 0;
}

void vecswap(int **x, int a, int b, int d){
  int j, t;
  for(j=0; j<d; j++){
    t = x[a][j];
    x[a][j] = x[b][j];
    x[b][j] = t;
  }
}

/*** Quicksort ***/
int partition(int **x, int l, int h, int d)
{
  srand(time(NULL));
  int r = rand()%(h-l+1);
  r += l;
  
  int *pivot;
  pivot = (int*)malloc(d*sizeof(int));
  for(int k=0; k<d; k++)
    pivot[k] = x[r][k];

  vecswap(x,r,h,d);

  int i= (l-1); 
 
  for (int j = l; j <= h - 1; j++) {
    if (compare(x,j,pivot,d) < 0) {
      i++; 
      vecswap(x,i,j,d);
    }
  }
  vecswap(x,i+1,h,d);
  return i+1;
}

void sort(int **x, int l, int h, int d)
{
    if (l < h) {
      int p = partition(x, l, h,d);
      sort(x, l, p - 1,d);
      sort(x, p + 1, h,d);
    }
}
/*** End of Quicksort ***/


/*** Clever Quicksort ***/
void cpartition(int **x, int l, int h, int *i, int *j,int c, int d){
  int r;
  srand(time(NULL));
  r = l+rand()%(h-l+1);
  vecswap(x,r,h,d);
  int pivot = x[h][c], low;
  int high = h;
  int equal = l;
  
  for (low = l; low <= high; low++){
    if (x[low][c] < pivot){
      nc_clever++;
      vecswap(x,low,equal,d);
      equal++;
    }
    else if (x[low][c] > pivot){
      nc_clever+=2;
      vecswap(x,low, high,d);
      high--;
      low--;
    }
  }
  
  *i = low;
  *j = equal - 1;
}

void cleversort(int **x, int l, int h, int c, int d)
{
  if (h <= l || c == d)
        return;
    int i, j;
   
    cpartition(x, l, h, &i, &j, c, d);
    
    cleversort(x, l, j, c, d);
    cleversort(x, j+1, i-1, c+1, d);
    cleversort(x, i, h, c, d);
}
/*** End of Clever Quicksort ***/


int main(){
  int **x, **y;
  int n,d;
  int i,j;

  nc = nc_clever = 0;
  
  scanf("%d %d", &d, &n);

  x = (int**)malloc(n*sizeof(int*));
  for(i=0; i<n; i++)
    x[i] = (int*)malloc(d*sizeof(int));

  y = (int**)malloc(n*sizeof(int*));
  for(i=0; i<n; i++)
    y[i] = (int*)malloc(d*sizeof(int));

  printf("Enter %d points, one in each line\n",n);

  for(i=0; i<n; i++)
    for(j=0; j<d; j++){
      scanf("%d", &x[i][j]);
      y[i][j] = x[i][j];
    }
  sort(x,0,n-1,d);
  printf("\n---QUICKSORT---\n\n   Sorted Array:\n      ");
  for(i=0; i<n; i++){
    for(j=0; j<d; j++){
      printf("%d ",x[i][j]);
    }
    printf("\n      ");
  }
  printf("\n   Number of single integer comparisons: %d\n\n",nc);
  cleversort(y, 0, n-1, 0, d);
  printf("\n--- CLEVER QUICKSORT ---\n\n   Sorted Array:\n      ");
  for(i=0; i<n; i++){
    for(j=0; j<d; j++){
      printf("%d ",y[i][j]);
    }
    printf("\n      ");
  }
  printf("\n   Number of single integer comparisons: %d\n\n",nc_clever);
  return 0;
}