//Copyright Dr. Marek A. Suchenek, 2005, 2006, 2007, 2008 - 2025
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package list;

/**
 *
 * @author suchenek
 */

// YOU ARE NOT ALLOWED TO MODIFY THE FOLLOWING CLASS, EXCEPT FOR:
// 1. WRITING-IN APPROPRIATE CODE AS INDICATED BELOW
// 2. CHANGING TYPE NAMES LIST AND POSITION TO: LIST_AR, POSITION_AR, 
//    LIST_DLL, AND POSITION_DLL AS APPROPRIATE, IF NECESSARY.

public class ListSelectionSort {

      /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
           LIST Array;
           int N;
 for (N = 1; N<=100; N++)
 {
        Array = new LIST();
//        for (int i = 0; i < N; i++)
//        Array.Insert(Array.End(), new Integer((int)(Math.sqrt(97)*(13*i + 1)*(19*i + 2)+i - 17)%1000));
        for (int i = 0; i < N; i++)
        Array.Insert(Array.End(), new Integer(i));

        for (POSITION i = Array.First(); !i.isEqual(Array.End()); i = Array.Next(i)) System.out.print((Integer)Array.Select(i) + " ");
        System.out.println();
        cnt.clr(); //counts cost of LIST operations while sorting
        cnt2.clr(); // counts moves of elements while sorting
        Bcnt.clrAll(); //counts comparisons of keys while sorting
        SelectionSort(Array);
        for (POSITION i = Array.First(); !i.isEqual(Array.End()); i = Array.Next(i)) System.out.print((Integer)Array.Select(i) + " ");
        System.out.println();
//        Tcomp(N) is the sorting "time" measured by the number of comparisons
//        of keys
        System.out.print("Tcomp(" + N +")");
        Bcnt.out(" = ");
        System.out.print("  " + (N*(N-1)/2) + " = N*(N-1)/2");
//        Tmove(N) is the sorting "time" measured by the number of moves of keys
        System.out.print("  Tmove(" + N +")");
        cnt2.out(" = ");
        System.out.print("  " + (N + N*(N-1)/2) + " = N + N*(N-1)/2 (lower bound)");
        System.out.print("  " + (2*(N + N*(N-1)/2)-1) + " = 2*(N + N*(N-1)/2)-1 (upper bound)");
//        Tlist(N) is the sorting "time" measured by the cost of LIST operations
        System.out.print("  Tlist(" + N +")");
        cnt.outln(" = ");

 }
    }
    public static void  SelectionSort(LIST A)
    {
//    YOUR CODE GOES HERE    
    }

// YOU CAN WRITE ADDITIONAL METHODS HERE IF YOU WISH

}