# Quicksort Implementierung-- Exception ArrayOutOfBounds



## JavaNewby (2. Jun 2009)

Hallo zusammen,

Gerade probiere ich, den berühmten Quicksort-Algorithmus selber zu implementieren. Dazu erzeuge ich ein Array aus zufällig generierten Zahlen, und der Benutzer darf entscheiden, wie gross das Array sein darf. Jedoch kriege ich eine Exception ArrayIndexOutOfBounds, und absolut keine Ahnung wieso!

Mein Code sieht folgendermassen aus:


```
public class Quicksort {
	
	//Initialise global variables:
	static int n;
	static int[] array ;
	
	public static void main(String[] args){
		
		Quicksort to_sort = new Quicksort();
		array = to_sort.CreateArray();
		quicksort(array, 0, array.length - 1);
		
	}
	
	//create an array of random numbers depending on user input:
	public int[] CreateArray(){
		
		//size of array must be between 2 and 20:
		try{
			//prompting for input:
			System.out.println("Please input any number between 2 and 20: ");
			Scanner scanner = new Scanner(System.in);
			n = scanner.nextInt();
			
			if(n < 2 || n>20) throw new MyException();			
			
		}catch(MyException e){
			System.out.println("You were expected to input a number between 2 and 20!");
		}
		
		//generate a random-numbers array
		Random rd = new Random();
		array = new int[n];
		
		//print it:
		for(int i = 0; i< array.length; i++){
			array[i] = rd.nextInt(30);
			System.out.println(array[i]);
		}
		
		return array;
		
	}
	
	//the actual sorting algorithm
	public static void quicksort(int[] a, int l, int r){				
		
		//Initialise indexes
		int i = l;
		int j = r;
		int pivot = a[r];
		int temp;
		
		do{
			//traverse the array from left and right simultaneously:
			do{ i++; }while(i<pivot);
			do{ j--; }while(j>pivot);
			if(i<j){
				//swap elements at positions i and j
				temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
			
			else break;
			
		}while(i < j);
		
		//swap i-th element with the pivot:
		
		temp = a[i];
		a[i] = a[r];
		a[r] = temp;		
		
		//recursive call:
		quicksort(a, l, i-1);
		quicksort(a, i+1, r);	
	
	}

}

class MyException extends Exception{}
```

So sieht Output/Fehlermeldung aus:

```
Please input any number between 2 and 20: 5
5
20
0
11
2
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 20
	at Quicksort.quicksort(Quicksort.java:75)
	at Quicksort.quicksort(Quicksort.java:80)
	at Quicksort.main(Quicksort.java:15)
```

Könnt ihr mir bitte ein Paar Tipps oder Gedankenanstösse geben, wo der Fehler liegen kann? Ich benutze Windows Vista; die Entwicklungsumgebung ist Eclipse.

Vielen Dank im Voraus!


----------



## tomse (2. Jun 2009)

Hallo,

in Zeile 56 und 57 vergleichtst du die Laufvariablen mit den Zufallszahlen ...


----------



## JavaNewby (2. Jun 2009)

Danke schön!  Hab den Fehler jetzt beseitigt.
Exceptions sind allerdings immer noch da...


----------



## Landei (2. Jun 2009)

Und die Exceptions heißen wie...? Sorry, meine Glaskugel ist gerade beschlagen ...


[edit]Kann es sein, dass deine quicksort-Methode noch eine Abbruchbedingung braucht? 
if (l + 1 >= r) { return; }  oder so?


----------



## JavaNewby (2. Jun 2009)

Es ist ArrayIndexOutOfBoundException, hab ich in der ersten Post erwähnt. 

Quicksort hab ich mit der void-Methode implementiert, daher brauchts keinen return-statement... Denk ich.


----------



## Landei (3. Jun 2009)

Jede Rekursion braucht eine Abbruchbedingung. Manchmal ergibt sie sich "automatisch", manchmal nicht. Was genau passiert bei dir, wenn r == l+1 oder r == l ist? Keine Ahnung, bin gerade zu faul nachzuschauen. Aber wenn du die if-Anweisung an den Anfang von quicksort stellst, kannst du das zumindest als Fehlerursache ausschalten (ich habe mir angewöhnt, bei solchen Sachen nicht zu "clever" sein zu wollen). Ansonsten streu ein paar System.out.printlns mit nützlichen Infos ein, um zu sehen, wo es hakt.


----------



## vogella (6. Sep 2009)

Hallo JavaNewby,

eine funktionierende Quicksort Implementierung findest Du hier: Quicksort in Java

Der Article beinhaltet auch einen JUnit Test mit Zufallszahlen; den Teil kannst Du dann relativ leicht durch Deine Scanner Klasse ersetzen.


----------

