[333OnlyHalfEvil]

import java.util.*;
public class Project2 {
	/** Task: Sorts equally spaced elements of an array into
	 * 		  ascending order.
	 *  @param a		an array of Comparable objects
	 *  @param first	the integer index of the first array element to
	 *				  consider; first >= 0 and < a.length
	 *  @param last		the integer index of the last array element to
	 *				  consider; last >= first and < a.length
	 *  @param space	the difference between the indices of the
	 *				  elements to sort */
	private static <T extends Comparable<? super T>> int incrementalInsertionSort(T[] a, int first, int last, int space) {
		int unsorted, index;
		int count = 0;
		for (unsorted = first + space; unsorted <= last; unsorted = unsorted + space) {
			T firstUnsorted = a[unsorted];
			for (index = unsorted - space; (index >= first) && (firstUnsorted.compareTo(a[index]) < 0); index = index - space) {
				a[index + space] = a[index];
				count++;
			} // end for
			a[index + space] = firstUnsorted;
		} // end for
		return count;
	} // end incrementalInsertionSort
	
	public static <T extends Comparable<? super T>> int shellSort(T[] a, int first, int last) {
		int count = 0;
		int n = last - first + 1; // number of array elements
		for (int space = n / 2; space > 0; space = space / 2) {
			for (int begin = first; begin < first + space; begin++) {
				count += incrementalInsertionSort(a, begin, last, space);
			} // end for
		} // end for
		return count;
	} // end shellSort
	
	public static void main(String[] args) {
		Random random = new Random();
		Integer[] a = new Integer[10];
		Integer[] b = new Integer[10];
		for (int i = 0; i < a.length; i++) {
			a[i] = random.nextInt(100);
			b[i] = a[i];
			System.out.println("Random");
		}
		System.out.println("Here");
		Integer insertion = incrementalInsertionSort(a, 0, 19, 0);
		System.out.println("The incrementalInsertionSort had " + insertion + " comparisons.");
		Integer shell = shellSort(b, 0, 19);
		System.out.println("The shellSort had " + shell + " comparisons.");		
	}
}

When I run this program, it compiles fine but it never finishes. I use eclipse and the method incrementalInsertionSort() has a red square in the outline instead of a green circle. This method and shellSort are copied directly out of a book. The main() method is what I did. Does anyone know what I can do/try that will make the program finish? Does anyone know what the red square in the outline section of eclipse means? Thanks.

[pbl]

Obviously

Integer insertion = incrementalInsertionSort(a, 0, 19, 0);

is an infinite loop
put a System.out.println() in it and you will see why tou loop forever

[Martyr2]

Your first for loop in that incrementalInsertSort is passed a 0 for first and a 0 for space. So unsorted starts at 0, keeps going until it hits 19 and is incremented by adding 0. See a problem with that? No where in your loop are you changing the values of space or unsorted so it never gets past 0.

Look at your book code again and try passing it a space value that is not 0. And again take a look at how that for loop condition works in the book.

This post has been edited by Martyr2: 13 June 2009 - 08:28 PM

[333OnlyHalfEvil]

Just curious, did you both find this manually or did you use eclipse to find the problem? If so, is there a function in eclipse that tells you where the infinite loop is at? Does the red square in the outline mean infinite loop somewhere and that it will never finish?

[pbl]

333OnlyHalfEvil, on 13 Jun, 2009 - 08:38 PM, said:

Just curious, did you both find this manually or did you use eclipse to find the problem? If so, is there a function in eclipse that tells you where the infinite loop is at? Does the red square in the outline mean infinite loop somewhere and that it will never finish?

cut & paste your program and ran it
the "here" appears but nothing after it