import java.util.*;

class ArrayUtils {

    public static void insertionSort(int[] A) {

	for (int firstUnsortedIndex = 1; 
	     firstUnsortedIndex < A.length; 
	     firstUnsortedIndex++) {

	    // A[0] through A[firstUnsortedIndex-1] are in sorted order.
	    // Goal:  put A[firstUnsortedIndex] into proper position.

	    int swappable = firstUnsortedIndex;
	    while (swappable > 0 && A[swappable] < A[swappable-1]) {
		// move swappable to the left by one.
		int temp = A[swappable - 1];
		A[swappable - 1] = A[swappable];
		A[swappable] = temp;
		swappable--;
	    }
	    System.out.println(Arrays.toString(A));
	}
    }


    public static void selectionSort(int[] A) {
	
	for (int i = 0; i < A.length; i++) {
	    // A[0] is the smallest element,
	    // A[1] is the next-smallest element, and
	    // ...
	    // A[i-1] is the (i-1)st-smallest element.

	    // Goal: find the (i)th-smallest element (aka the smallest
	    // remaining element) and put it in A[i].

	    int min = A[i];
	    int minIndex = i;
	    for (int j = i+1; j < A.length; j++) {
		if (A[j] < min) {
		    minIndex = j;
		    min = A[j];
		}
	    }
	    
	    // Swap A[i] and A[minIndex].
	    int temp = A[i];
	    A[i] = A[minIndex];
	    A[minIndex] = temp;

	    System.out.println(Arrays.toString(A));
	}
    }

    public static boolean sequentialSearch(int[] dict, int x) {
	int i = 0;
	while (i < dict.length && dict[i] <= x) {
	    if (dict[i] == x) {
		return true;
	    }
	    i++;
	}
	return false;
    }

    public static void main(String[] args) {
	int[] dict = new int[10];
	Random rand = new Random();
	for (int i = 0; i < 10; i++) {
	    dict[i] = rand.nextInt(100);
	}

	System.out.println(Arrays.toString(dict));
	//	insertionSort(dict);
	selectionSort(dict);
	System.out.println(Arrays.toString(dict));

    }

}