[Izviral]

Hi all. Im new to java and Im writing a quicksort method for my class. Im getting an out of bounds exception on line 34. Ive stepped through the program several times, but i must be missing something because i cant figure it out. Its probably something Im going to feel silly about when i find out why.

import java.util.ArrayList;

public class Quicksort
{
	public static void main (String [] args)
	{
		ArrayList <Integer> numbers = new ArrayList<Integer>();
		numbers.add(5);
		numbers.add(3);
		numbers.add(2);
		numbers.add(7);
		numbers.add(6);
		numbers.add(4);
		numbers.add(1);
		System.out.println(numbers);
		sortquickly(numbers, 0, numbers.size() - 1);
		System.out.println(numbers);
	}

	public static void sortquickly (ArrayList <Integer> numbers, int begin, int end)
	{
		
		int i = begin;
		int j = end;
		int pivot = begin;
		
		if (j - i >= 1)
		{
			while (i < j)
			{
				while (numbers.get(i) <= pivot && i <= end && j > i)
					i++;
			
				while (numbers.get(j) > pivot && j >= begin && j >= i)
					j--;
				
				if (i < j)
					Swap(numbers, i, j);
				
			}
			Swap(numbers, begin, j);
			
			sortquickly(numbers, begin, j - 1);
			sortquickly(numbers, j + 1, end);
		}
		else
			return;
		
	}

	public static void Swap (ArrayList <Integer> nums, int i, int j)
	{
		int temp = nums.get(i);
		nums.set(i, nums.get(j));
		nums.set(j, temp);
	}
}

This post has been edited by Izviral: 16 June 2011 - 07:22 PM

[immeraufdemhund]

you could just make it a List of something that is comparable. then use Collections.sort().

Look into this Comparable API

as for why your program is throwing a out of bounds loop is probably because of your >= and you <=. What I do sometimes is put a System.out.println(counter) or in your case system.out.println(i) and system.out.println(j);

This post has been edited by immeraufdemhund: 16 June 2011 - 08:08 PM

[pbl]

				while (numbers.get(j) > pivot && j >= begin && j >= i) {
					j--;
					System.out.println("Next J will be: " + j);
				}

will yields

Next J will be: 5
Next J will be: 4
Next J will be: 3
Next J will be: 2
Next J will be: 1
Next J will be: 0
Next J will be: -1

[itengineer]

I may be wrong on this.... but even after solving this Exception issue does it works properly..

I saw you are doing

numbers.get(i) <= pivot

Comparing a number with some index.

--itengineer