algo_homework1.java

import java.io.*;
import java.util.*;

public class Main {
  private static int global_assignments;

	static private void printArray(int[] array)
	{
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + " ");
		}
	}

	public static int[] arrayMinWithIndex(int[] arr) {
		int i = 0;
		int min = Integer.MAX_VALUE;
		int index = 0;
		if (arr == null) {
			//return 0;
		} else {
			while (i < arr.length) {
				if (arr[i] < min) {
					min = arr[i];
				}
				i++;
			}
		}

		for(i=0; i <= arr.length; i++){
			if(arr[i] == min){
				index = i;
				break;
			}
		}

		int[] returnArray = {min, index};
		return returnArray;
	}

	static private void quickSort(int[] array, int left, int right, int cutOff)
	{
		if (left < right)
		{
			if((right - left) < cutOff){
				for (int i = left+1; i <= right; i++) {
					int v = array[i];
					int j = i;
					while (j > left && v < array[j-1]) {
						array[j] = array[j-1];
						global_assignments++;
						j--;
					}
					array[j] = v;
					global_assignments++;
				}
			} else {
				int[] partitionReturnArray = partition(array, left, right);
				global_assignments += partitionReturnArray[1];

				quickSort(array, left, partitionReturnArray[0]-1, cutOff);
				quickSort(array, partitionReturnArray[0]+1, right, cutOff);
			}
		}
	}

	private static int[] partition(int[] array, int left, int right)
	{
		int pivotValue = array[ right ];
		int assignments = 0;
		int index = left;

		for (int i = left; i < right; i++)
		{
			if (array[i] < pivotValue)
			{
				swap(array, i, index);
				global_assignments += 2;
				index++;
			}
		}
		swap(array, right, index);
		global_assignments += 2;

		int[] returnArray = {index, assignments};
		return returnArray;
	}

	private static void swap(int[] array, int i, int j)
	{
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}

	public static void main (String[] args) throws IOException
	{
		InputStream stdin = System.in;
		int[] counts = new int[50];
		int[] finalSorted = null;

		Scanner scanner = new Scanner(System.in);

		int testNumCount = Integer.parseInt(scanner.nextLine());
		String testNumString = scanner.nextLine();

		scanner.close();

		String[] testNumsArray = testNumString.split(" ");
		int[] intNumArray = new int[testNumsArray.length];

		for (int i = 0; i < intNumArray.length; i++) {
			try {
				intNumArray[i] = Integer.parseInt(testNumsArray[i]);
			} catch (NumberFormatException nfe) {};
		}

		for (int i = 0; i < 50; i++) {
			int[] cloneArray = intNumArray.clone();
			// Sort
			quickSort(cloneArray, 0, cloneArray.length-1, i);
			counts[i] = global_assignments;
			finalSorted = cloneArray;
			global_assignments = 0;
		}

		int[] result = arrayMinWithIndex(counts);

		System.out.println(result[1]);
		System.out.println(result[0]);
		printArray(finalSorted);
	}
}