3 Replies - 967 Views - Last Post: 16 June 2011 - 10:26 PM Rate Topic: -----

#1 Izviral  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 15-June 11

Index out of bounds on my quicksort

Posted 16 June 2011 - 07:21 PM

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


Is This A Good Question/Topic? 0
  • +

Replies To: Index out of bounds on my quicksort

#2 immeraufdemhund  Icon User is offline

  • D.I.C Regular

Reputation: 79
  • View blog
  • Posts: 495
  • Joined: 29-March 10

Re: Index out of bounds on my quicksort

Posted 16 June 2011 - 08:07 PM

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

Was This Post Helpful? 0
  • +
  • -

#3 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8332
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: Index out of bounds on my quicksort

Posted 16 June 2011 - 08:08 PM

				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
Was This Post Helpful? 0
  • +
  • -

#4 itengineer  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 37
  • Joined: 23-April 09

Re: Index out of bounds on my quicksort

Posted 16 June 2011 - 10:26 PM

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
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1