/*
En möjlig implementering av quicksort
För andra lösningar se tex wikipedia eller 
föreläsningsanteckningarna (F2 sid 181)
*/

import java.util.Arrays;

public class Sort2{
    
    public void quicksort(int[] array){
	quicksort(array,0,array.length-1);
    }
    
    public void quicksort(int[] array, int start, int end){
	if(start >= end) return; 
	int pivotIndex = getPivot(array, start, end);
	int newPivotIndex = partition(array,pivotIndex,start,end);
	quicksort(array,start,newPivotIndex-1);
	quicksort(array,newPivotIndex+1,end);
    }
    
    public int getPivot(int[] array, int start, int end){
	return start;
    }
    
    public int partition(int[] array, int pivotIndex, int start, int end){
	if(start >= end) return -1; 
	int pivotElement = array[pivotIndex];
	//byt plats på pivot och första elementet, så att det inte deltar i partitioneringen
	array[pivotIndex] = array[start];
	array[start] = pivotElement;
	
	int left= start+1;
	int right = end;
	int temp = 0;
	
	while(left < right){
	    
	    //Räkna ner högerindex så länge motsvarande element är tillräckligt stort
	    //Till slut hittar vi ett element som är mindre än pivot
	    //Eller så är vi klara
	    while(left<right && array[right] > pivotElement){
		right --;
		
	    }
	    //byt plats på elementen så att det som var för litet hamnar till vänster
	    temp         = array[left];
	    array[left] = array [right];
	    array[right]= temp;
	    
	    //Motsvarande sker på vänster sida
	    while(left<right && array[left] <= pivotElement){
		left ++;
	    }
	    temp        = array[right];
	    array[right]= array [left];
	    array[left] = temp;
	    
	    //System.out.println("left: "+left);
	    //System.out.println("right: "+right);
	    
	}
	//Till slut är left = right
	
	//Vi vet inte om det som tidigare var på pivotelementets plats är större eller mindre än pivot
	//Om det var mindre är allt bra, annars byter vi dess plats mot vad som helst th om pivot
	if(array[left] > pivotElement){
	    left--;
	}
	
	//Lägg in pivot på plats left
	temp = array[left];
	array[left] = pivotElement;
	array[start] = temp;
	
	//Vi vet inte om det som tidigare var på pivotelementets plats är större eller mindre än pivot
	//Om det var mindre är allt bra, annars byter vi dess plats mot vad som helst th om pivot
	if(array[left] > pivotElement){
	    left--;
	}
	
	//returnerar det rätta indexet för pivotelementet
	return left;
    }

    public static void main(String[] args){
	Sort2 instance = new Sort2();
	int[] array = {0,0,-10,55};
	System.out.println("*Före:  " +Arrays.toString(array));
	instance.quicksort(array);
	System.out.println("*Efter: "+Arrays.toString(array));
    }

}