/*
	description: gapsort sorts integer arrays. Tests gapsort with a randomly initialized array of integers.
	author:          K. Hug, T. Tali
	history:         04-10-28
*/

public class Sorter
{
	private static final double shrink_factor = 1.3;
			
	public static boolean sorted (int[] array)
	{
		int index =0;
		while (index < array.length - 1 && array[index] <= array[index + 1])      // Fehlerträchtige Unstetigkeitsstelle!
			index++;
		return index >= array.length - 1;
	}
	
	public static void gapsort (int[] array)
	{
		boolean swapped = true;
		int gap = array.length;
		while (swapped || gap > 1)
		{
			swapped = false;
			gap = Math.max((int)(gap / shrink_factor), 1);
			for (int index1 = 0; index1 + gap < array.length; index1++)
			{
				int index2 = index1 + gap;
				if (array[index1] > array[index2])
				{
					int temp = array[index1];
					array[index1] = array[index2];
					array[index2] = temp;
					swapped = true;
				};
			};
		};
		if (!sorted(array)) System.exit(60);
	}

	private static final int size = 100;
	
	private static int[] array = new int[size];
		
	private static void initRandom (int[] array)
	{
		java.util.Random random = new java.util.Random();
		for (int index = 0; index < array.length; index++)
		{
			array[index] = random.nextInt(10 * size);
		};
	}

	private static void print (int[] array)
	{
		System.out.print("[");
		for (int index = 0; index < array.length; index++)
		{
			System.out.print(array[index] + " ");
		};
		System.out.println("]");
	}
	
	public static void main (String[] args)
	{
		initRandom(array);
		print(array);
		gapsort(array);
		print(array);
	}
}