/*  
    CSci 211, Fall 1996, Examination #1, Problem #8
    H. Conrad Cunningham, 23 September 1996
*/
public class Sort
{
    // Bubble Sort
    public static void sort (int[] arr)
    {   int len = arr.length;
        for (int i = 0; i < len; i++)
            // arr[0..i-1] has the i smallest values in ascending order
	    for(int j = i+1; j < len; j++)
	        if (arr[i] > arr[j])
		{   int temp = arr[i];
		    arr[i] = arr[j];
		    arr[j] = temp;
		}
    }

    // Insertion Sort
    public static void insertionSort (int[] arr) 
    {   int len = arr.length;
        for (int i = 1; i < len; i++)
        {   // arr[0..i-1] is in ascending order
            int temp = arr[i];
	    int loc = i;
	    for ( ; loc > 0 && arr[loc-1] > temp; loc--)
	        arr[loc] = arr[loc-1];
	    arr[loc] = temp;
        }
    }

    // Shell Sort (adapted from _Core_Java)
    public static void shellSort(int[] arr)
    {   int len = arr.length;
        for (int incr = len / 2; incr >= 1; incr = incr / 2)
            for (int i = incr; i < len; i++)
            {   int temp = arr[i];
                int j = i;
                for ( ; j >= incr && temp < arr[j-incr]; j = j - incr)
                    arr[j] = arr[j-incr];
                arr[j] = temp;
             }
     }

    public static void main(String[] args)
    {   int[] a = new int[100];
        for(int i = 0; i < 100; i++)
	    a[i] = (int) (Math.random() * 1000);
        for(int i = 0; i < 100; i++)
	    System.out.println(i + ":" + a[i]);
	sort(a);  // sort(a) OR insertionSort(a) OR shellSort(a)
        for(int i = 0; i < 100; i++)
	    System.out.println(i + ":" + a[i]);
    }
}