import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
public class quickSortComparisons {
public static class Comparisons{
long count;
public Comparisons() {
count = 0;
}
}
public static void quickSort(int[] array){
Comparisons comparisons = new Comparisons();
quickSort(array, 0, array.length-1, comparisons);
System.out.println(comparisons.count);
}
public static void quickSort(int[]array, int left, int right, Comparisons c){
if(left >= right){
return;
}
int index = partition(array, left, right, c);
quickSort(array, left, index-1, c);
quickSort(array, index+1, right, c);
}
public static int partition(int[] array, int left, int right, Comparisons c){
c.count += right - left;
int index = pivotChoser(array, left, right,(right+left)/2);
swap(array, left, index); //put the pivot at the beginning of the array
int pivot = array[left];
int i = left+1;
for (int j= left+1; j<=right; j++) {
if(array[j] < pivot) {
swap(array, i, j);
i++;
}
}
swap(array, left, i-1);
return i-1;
}
public static int pivotChoser(int[] array, int left, int right, int middle) {
int[] temp = new int[3];
temp[0] = array[left];
temp[1] = array[middle];
temp[2] = array[right];
for(int i=0; i<temp.length; i++) {
for(int j=0; j<temp.length-1; j++) {
if(temp[i]<temp[j])swap(temp, i, j);
}
}
if(temp[1] == array[left])return left;
if(temp[1] == array[middle])return middle;
else return right;
}
public static void swap(int[]a, int left, int right) {
int e = a[left];
a[left] = a[right];
a[right] = e;
}
public static void main(String[] args) throws NumberFormatException, IOException {
int[] arr = new int[10000];
BufferedReader abc = new BufferedReader(new FileReader("quick.txt"));
int i=0;
String line = "";
while((line = abc.readLine()) != null) {
arr[i] = Integer.parseInt(line);
i++;
}
abc.close();
quickSort(arr);
boolean sorted = true;
for(int x=0; x<arr.length-1; x++) {
if(arr[x]>arr[x+1])sorted = false;
}
System.out.println("HA FUNCIONADO: "+ sorted);
System.out.println(Arrays.toString(arr));
}
}