/*
 * @topic T02505 selectionSort(), insertionSort( ), and binarySearch( ) demo
 * @brief Array of integers sorted, then searched
*/
package demo;

public class Main {

    public static void main(String[] args) {
        int[] iarr = {100, 17, 23, 25, 30, 18, 45, 35};
        for (int value : iarr) {
            System.out.print(value + " ");
        }

        // Use insertionSort or selectionSort here:
        //insertionSort(iarr, iarr.length);
        selectionSort(iarr, iarr.length);

        System.out.println();
        for (int value : iarr) {
            System.out.print(value + " ");
        }

        System.out.println();
        int searchFor = 18;
        int found = binarySearch(iarr, iarr.length, searchFor);
        if ( found == -1 ) {
            System.out.print("element " + searchFor + " not found");
        }
        System.out.print("element " + searchFor + " found at ["+found+"]");
        System.out.println();
    }//end main

    public static void insertionSort(int[] list, int listLength) {
        int firstOutOfOrder, location;
        int temp;
        for (firstOutOfOrder = 1; firstOutOfOrder < listLength; firstOutOfOrder++) {
            if (list[firstOutOfOrder] < list[firstOutOfOrder - 1]) {
                // list[firstOutOfOrder] is indeed out of order!
                temp = list[firstOutOfOrder];
                location = firstOutOfOrder;
                do {
                    list[location] = list[location - 1]; // shift previous down
                    location--;
                } while (location > 0 && list[location - 1] > temp);
                list[location] = temp;
            }
        }
    } //end insertionSort

    public static int binarySearch(int[] list, int listLength,
            int searchItem) {
        int first = 0;
        int last = listLength - 1;
        int mid = 0;
        boolean found = false;

        while (first <= last && !found) {
            mid = (first + last) / 2;
            if (list[mid] == searchItem) {
                found = true;
            } else if (list[mid] > searchItem) {
                last = mid - 1;
            } else {
                first = mid + 1;
            }
        }
        if (found) {
            return mid;
        } else {
            return -1;
        }
    } //end binarySearch

    public static void selectionSort(int[] list, 
                                     int listLength)
    {
        int index;
        int smallestIndex;
        int minIndex;
        int temp;

        for (index = 0; index < listLength - 1; index++)
        {
            smallestIndex = index; 
            for (minIndex = index + 1; 
                 minIndex < listLength; minIndex++)
                if (list[minIndex] < list[smallestIndex])
                    smallestIndex = minIndex; 

            temp = list[smallestIndex];
            list[smallestIndex] = list[index];
            list[index] = temp;
        }
    }//end selectionSort

}//class Main

/*

Output:

100 17 23 25 30 18 45 35
17 18 23 25 30 35 45 100
element 18 found at [1]

 */