#include "common.h"
#include <math.h>
#include <stdlib.h>
#include <stdio.h>

/**
 *
 * Interface  
 *
 *
 * */
inline int partition(int A[], int lower, int upper);
inline int overlap(int a, int b, int c, int d);
void PartialQuicksort(int A[], int lower, int upper, int first, int last);


/**
 *
 * Implementação 
 *
 *
 * */


int overlap(int a, int b, int c, int d)
{
	return b >= c && a <= d;
}



void PartialQuicksort(int A[], int lower, int upper, int first, int last)
{
	int m;

	if (!overlap(lower,upper, first,last)){
		return;
	}
	
	if (lower < upper) {
		m = partition(A, lower,upper);
		PartialQuicksort (A, lower, m, first, last);
		PartialQuicksort (A, m + 1, upper, first,last);
	}
}

int partition(int A[], int lower, int upper)
{
	int i,j,pivot;
	
	pivot = A[(lower+upper)/2];
	i=lower;
	j=upper;
	
	while (i<j) {
	    while (A[i] < pivot){ i++;COUNT_COMP;};
	    while (A[j] > pivot){ j--;COUNT_COMP;};
	    if (j < i) {
		    break;
	    } else {
		    swap(&A[i], &A[j]);
	    }
	}

	return j;
}


void partial_quick_sort( int A[], int n, int k)
{
	PartialQuicksort(A,0,n-1,0,k-1);
}