Overall Lab 09 Instructions

Using the instructions from Closed Lab 01, create a new folder named ClosedLab09. Unlike with previous labs, you will need to import the following file into your new lab folder. Follow the instructions from Clsoed Lab 01 to import this file into your ClosedLab09 folder.

Lab09a.java

You will be writing a simple Java program that implements an algorithm known as a Selection Sort. A Selection Sort is a simple sorting algorithm that takes an unsorted array of elements and sorts them into ascending order. This process will be broken down into two parts. For the first part, you will write the code that takes a list of numbers from the user from the console, stores them in an array, and displays them in the order that the user provided. For the second part, you will write a method to sort the array using the Selection Sort algorithm and then display the final results in sorted order.

Exercise 1 Description

Your code will take a list of integers as input from the console, store them in an array, and then display the results in the order that the user provided them.

Exercise 1 Sample Output

This is a sample transcript of what your program should do. Text in bold is expected input from the user rather than output from the program. Please enter the number of digits to be stored: 5 Enter integer 0: -1 Enter integer 1: 10 Enter integer 2: 15 Enter integer 3: -6 Enter integer 4: 3 The contents of your array: Number of digits in array: 5 Digits in array: -1 10 15 -6 3 If the user provides a negative number of digits to be stored, the program should prompt the user to input a non-negative number of digits to store: Please enter the number of digits to be stored: -1 ERROR! You must enter a non-negative number of digits! Please enter the number of digits to be sorted: 3 Enter integer 0: 0 Enter integer 1: -5 Enter integer 2: 16 The contents of your array: Number of digits in array: 3 Digits in array: 0 -5 16 If the user asks to store 0 digits, the program should exit with a simple goodbye message: Please enter the number of digits to be stored: 0 No digits to store? Goodbye!

Exercise 2 Description

Create a copy of your solution for Exercise 1 and name it Lab09b.java in the same ClosedLab09 folder. For this exercise, you should extend the code that you wrote in Exercise 1 with a new method. This new method should use the following method header: private static void selectionSort(int[] digits) It should take an array of digits as input. The program will sort the array of digits in-place using the Selection Sort algorithm described below. "In-place" sorting means that the method will not create a new array - instead it will make changes directly to the array passed into the method. You may find it useful to break the selection sort algorithm up into multiple methods.

The Selection Sort Algorithm

The Selection Sort algorithm is the simplest example of a sorting algorithm. A sorting algorithm takes a list of items and returns them in sorted order. Selection sort performs this action by searching through the list for the smallest value in the list, swapping it with the first item in the list. It then repeats this process (swapping the second elements of the list with the second smallest, the third element with the third smallest, etc.) until the entire list has been sorted. A very simple version of the algorithm for selection sort is as follows:

Set the current index to 0

Loop over the entire list from the current index to the end, searching for the minimum value

Swap the mimum value with the value at the current index

Increment the current index by 1 and repeat from step 2 until the current index is the final position of the list

We can see this at work with an example. Suppose we have the list [ 1, 12, -3 ] and we want to sort it in ascending order:

Set the current index to 0

Find the minimum value between the current index and the end of the list

This would be the value at index postion 2 (-3)

Swap the value at index position 2 with the current index

The list is now [-3, 12, 1]

Increment the current index by 1 (current index is now 1)

The loop now repeats from step 2 - find the minimum value between the current index (1) and the end of the list

This would be the value at index position 2 (1)

Swap the value at index position 2 with the current index

This list is now [-3, 1, 12]

Increment the current index by 1 (current index is now 2)

The current index is equal to the final index of the list, so the loop ends and the list is sorted

Exercise 2 Sample Output

This is a sample transcript of what your program should do. Note that the prompts for the user have changed from "store" to "sort" and your prompts should be changed accordingly: Please enter the number of digits to be sorted: 3 Enter integer 0: 12 Enter integer 1: 0 Enter integer 2: -3 Array before sorting: Number of digits in array: 3 Digits in array: 12 0 -3 Array after sorting: Number of digits in array: 3 Digits in array: -3 0 12 A second run of the same program might produce the following output: Please enter the number of digits to be sorted: 5 Enter integer 0: -12 Enter integer 1: -15 Enter integer 2: 44 Enter integer 3: 0 Enter integer 4: 5 Array before sorting: Number of digits in array: 5 Digits in array: -12 -15 44 0 5 Array after sorting: Number of digits in array: 5 Digits in array: -15 -12 0 5 44 Your code should give the appropriate messages if the user attempts to have a negative number of digits sorted or if the user asks to sort 0 digits: Please enter the number of digits to be sorted: -12 ERROR! You must enter a non-negative number of digits! Please enter the number of digits to be sorted: 0 No digits to sort? Goodbye!

------------------------------------------------------------------------------------------------------------------ import java.util.Scanner; public class Lab09a { public static void main(String[] args) { // Fill in the body. } // Given a Scanner as input, prompts the user for the number of digits they will be // entering into an array. If the number given by the user is less than 0, display // an error message and ask for a number that is 0 or greater. When a valid number is // received, return it to the calling program. private static int getNumDigits(Scanner inScanner) { // Fill in the body } // Given an array and a Scanner as input, prompt the user to input integers to fill the // array. The procedure should display a prompt for the user to enter an integer, and // should loop until the entire array is filled with integer. private static void getDigits(int[] digits, Scanner inScanner) { // Fill in the body } // Given an array as input, displays the total number of digits contained in the array // and displays the contents of the array in order, starting at index 0 and ending // with the final index of the array. private static void displayDigits(int[] digits) { // Fill in the body } // FOR LAB10B // Given an array of integers as input, sorts the array using the Selection Sort algorithm // provided in the Closed Lab 10 write-up. private static void selectionSort(int[] digits) { } }