irborrero
8/18/2019 - 9:04 PM

Stanfort QuickSort

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));
	} 

}