public class Quicksort {

	//Her har jeg laget en main-metode som tester de metodene som er laget med de testdataene
	//som ble gått igjennom for hånd i øvingsforelesningen. Det er anbefalt å forstå det som skjer
	//ved å sette inn forskjellige System.out.println() i koden ellers slik at man ser hva som skjer
	//i de forskjellige trinnene.

	public static void main(String[] args){
		int[] usortert = {5, 2, 6, 9, 3, 4};
		System.out.println("Usortert:");
		System.out.print("[");
		for(int i = 0;i!=usortert.length; i++){
			System.out.print(""+usortert[i]);
			if(i!=usortert.length-1){
				System.out.print(", ");
			}
		}
		System.out.println("]");
		System.out.println("");
		int[] sortert = quickSort(usortert, 0, usortert.length-1);
		System.out.println("Sortert:");
		System.out.print("[");
		for(int i = 0;i!=sortert.length; i++){
			System.out.print(""+sortert[i]);
			if(i!=sortert.length-1){
				System.out.print(", ");
			}
		}
		System.out.println("]");
	}

	//Dette er en implementasjon av partition med akkurat samme prinsipper som i boken.
	//Den eneste forskjellen er at denne implementasjonen baserer seg på at indekseringen
	//av arrays i java går fra 0 til n-1, mens pseudokoden i boken bruker array-indeksering
	//fra 1 til n.

	public static int partition(int[] a, int fra, int til){
		int pivotVerdi = a[til];
		int pivotIndeks =fra;
		for(int j = fra;j<til;j++){
			if(a[j]<=pivotVerdi){
				int temp = a[pivotIndeks];
				a[pivotIndeks] = a[j];
				a[j] = temp;
				pivotIndeks++;
			}
		}
		int sisteTemp = a[til];
		a[til] = a[pivotIndeks];
		a[pivotIndeks] = sisteTemp;
		return pivotIndeks;
	}


	//Dette er en direkte implementasjon av den quicksort-algoritmen som er presentert i boken.
	//Den er helt identisk.
	public static int[] quickSort(int[] a, int fra, int til){
		if(fra<til){
			int pivotPlass = partition(a, fra, til);
			quickSort(a, fra, pivotPlass-1);
			quickSort(a, pivotPlass, til);
		}
		return a;
	}
}