3. Polymorphic Sorting The file Sorting.java contains the Sorting class from lec
ID: 3813400 • Letter: 3
Question
3. Polymorphic Sorting The file Sorting.java contains the Sorting class from lecture slides. This class implements both the selection sort and the insertion sort algorithms for sorting any array of Comparable objects in ascending order. In this exercise, you will use the Sorting class to sort several different types of objects. 1. The file Numbers.java reads in an array of integers, invokes the selection sort algorithm to sort them, and then prints the sorted array. Save Sorting.java and Numbers.java to your directory. Numbers.java won’t compile in its current form. Study it to see if you can figure out why. Hint: Wrapper class of int 2. Try to compile Numbers.java and see what the error message is. The problem involves the difference between primitive data and objects. Change the program so it will work correctly (note: you don’t need to make many changes - the autoboxing feature of Java 1.5 will take care of most conversions from int to Integer when scan in data from keyboard). 3. Write a program Strings.java, similar to Numbers.java, that reads in an array of String objects and sorts them. You may just copy and edit Numbers.java. 4. Modify the insertionSort algorithm so that it sorts in descending order rather than ascending order. Change Numbers.java and Strings.java to call insertionSort rather than selectionSort. Run both to make sure the sorting is correct. 5. The file Salesperson.java partially defines a class that represents a sales person. This is very similar to the Contact class in our lecture. However, a sales person has a first name, last name, and a total number of sales (an int) rather than a first name, last name, and phone number. Complete the compareTo method in the Salesperson class. The comparison should be based on total sales; that is, return a negative number if the executing object has total sales less than the other object and return a positive number if the sales are greater. Use the name of the sales person to break a tie (alphabetical order). 6. The file WeeklySales .java contains a driver for testing the compareTo method and the sorting. Compile and run it. Make sure your compareTo method is correct. The sales staff should be listed in order of sales from most to least with the four people having the same number of sales in reverse alphabetical order. 7. OPTIONAL: Modify WeeklySales.java so the salespeople are read in rather than hardcoded in the program. //****************************************************************** // Sorting.java Author: Lewis/Loftus // // Demonstrates the selection sort and insertion sort algorithms. //****************************************************************** public class Sorting { //----------------------------------------------------------------- // Sorts the specified array of objects using the selection // sort algorithm. //----------------------------------------------------------------- public static void selectionSort (Comparable[] list) { int min; Comparable temp; for (int index = 0; index < list.length-1; index++) { min = index; for (int scan = index+1; scan < list.length; scan++) if (list[scan].compareTo(list[min]) < 0) min = scan; // Swap the values temp = list[min]; list[min] = list[index]; list[index] = temp; } } //----------------------------------------------------------------- // Sorts the specified array of objects using the insertion // sort algorithm. //----------------------------------------------------------------- public static void insertionSort (Comparable[] list) { for (int index = 1; index < list.length; index++) { Comparable key = list[index]; int position = index; // Shift larger values to the right while (position > 0 && key.compareTo(list[position-1]) < 0) { list[position] = list[position-1]; position--; } list[position] = key; } } } //********************************************************** // Numbers.java // // Demonstrates selectionSort on an array of integers. //********************************************************** import java.util.Scanner; public class Numbers { //--------------------------------------------- // Reads in an array of integers, sorts them, // then prints them in sorted order. //--------------------------------------------- public static void main (String[] args) { int[] intList; int size; Scanner scan = new Scanner(System.in); System.out.print (" How many integers do you want to sort? "); size = scan.nextInt(); intList = new int[size]; System.out.println (" Enter the numbers..."); for (int i = 0; i < size; i++) intList[i] = scan.nextInt(); Sorting.selectionSort(intList) ; System.out.println (" Your numbers in sorted order..."); for (int i = 0; i < size; i++) System.out.print(intList[i] + " "); System.out.println (); } } // ******************************************************* // Salesperson.java // // Represents a sales person who has a first name, last // name, and total number of sales. // ******************************************************* public class Salesperson implements Comparable { private String firstName, lastName; private int totalSales; //------------------------------------------------------ // Constructor: Sets up the sales person object with // the given data. //------------------------------------------------------ public Salesperson (String first, String last, int sales) { firstName = first; lastName = last; totalSales = sales; } //------------------------------------------- // Returns the sales person as a string. //------------------------------------------- public String toString() { return lastName + ", " + firstName + ": " + totalSales; } //------------------------------------------- // Returns true if the sales people have // the same name. //------------------------------------------- public boolean equals (Object other) { return (lastName.equals(((Salesperson)other).getLastName()) && firstName.equals(((Salesperson)other).getFirstName())); } //-------------------------------------------------- // Order is based on total sales with the name // (last, then first) breaking a tie. //-------------------------------------------------- public int compareTo(Object other) { int result; return result; } //------------------------- // First name accessor. //------------------------- public String getFirstName() { return firstName; } //------------------------- // Last name accessor. //------------------------- public String getLastName() { return lastName; } //------------------------- // Total sales accessor. //------------------------- public int getSales() { return totalSales; } } // ****************************************************************** // WeeklySales.java // // Sorts the sales staff in descending order by sales. // ****************************************************************** public class WeeklySales { public static void main(String[] args) { Salesperson[] salesStaff = new Salesperson[10]; salesStaff[0] = new Salesperson("Jane", "Jones", 3000); salesStaff[1] = new Salesperson("Daffy", "Duck", 4935); salesStaff[2] = new Salesperson("James", "Jones", 3000); salesStaff[3] = new Salesperson("Dick", "Walter", 2800); salesStaff[4] = new Salesperson("Don", "Trump", 1570); salesStaff[5] = new Salesperson("Jane", "Black", 3000); salesStaff[6] = new Salesperson("Harry", "Taylor", 7300); salesStaff[7] = new Salesperson("Andy", "Adams", 5000); salesStaff[8] = new Salesperson("Jim", "Doe", 2850); salesStaff[9] = new Salesperson("Walt", "Smith", 3000); Sorting.insertionSort(salesStaff); System.out.println (" Ranking of Sales for the Week "); for (Salesperson s : salesStaff) System.out.println (s); } }
Explanation / Answer
// Sorting.java
// Demonstrates the selection sort and insertion sort algorithms.
public class Sorting
{
//----------------------------------------------------------------
// Sorts the specified array of objects using the selection
// sort algorithm.
//-----------------------------------------------------------------
public static void selectionSort (Comparable[] list)
{
int min;
Comparable temp;
for (int index = 0; index < list.length-1; index++)
{
min = index;
for (int scan = index+1; scan < list.length; scan++)
if (list[scan].compareTo(list[min]) < 0)
min = scan;
// Swap the values
temp = list[min];
list[min] = list[index];
list[index] = temp;
}
}
//-----------------------------------------------------------------
// Sorts the specified array of objects using the insertion
// sort algorithm.
//-----------------------------------------------------------------
public static void insertionSort (Comparable[] list)
{
for (int index = 1; index < list.length; index++)
{
Comparable key = list[index];
int position = index;
// Shift larger values to the right
while (position > 0 && key.compareTo(list[position-1]) < 0)
{
list[position] = list[position-1];
position--;
}
list[position] = key;
}
}
}
// ******************************************************
// Numbers.java
//
// Demonstrates selectionSort on an array of integers.
// ******************************************************
import java.util.Scanner;
public class Numbers
{
// --------------------------------------------
// Reads in an array of integers, sorts them,
// then prints them in sorted order.
// --------------------------------------------
public static void main (String[] args)
{
int[] intList;
int size;
Scanner scan = new Scanner(System.in);
System.out.print (" How many integers do you want to sort? ");
size = scan.nextInt();
intList = new int[size];
System.out.println (" Enter the numbers...");
for (int i = 0; i < size; i++)
intList[i] = scan.nextInt();
Sorting.selectionSort(intList);
System.out.println (" Your numbers in sorted order...");
for (int i = 0; i < size; i++)
System.out.print(intList[i] + " ");
System.out.println ();
}
}
// *******************************************************
// Salesperson.java
//
// Represents a sales person who has a first name, last
// name, and total number of sales.
// *******************************************************
public class Salesperson implements Comparable
{
private String firstName, lastName;
private int totalSales;
//------------------------------------------------------
// Constructor: Sets up the sales person object with
// the given data.
//------------------------------------------------------
public Salesperson (String first, String last, int sales)
{
firstName = first;
lastName = last;
totalSales = sales;
}
//-------------------------------------------
// Returns the sales person as a string.
//-------------------------------------------
public String toString()
{
return lastName + ", " + firstName + ": " + totalSales;
}
//-------------------------------------------
// Returns true if the sales people have
// the same name.
//-------------------------------------------
public boolean equals (Object other)
{
return (lastName.equals(((Salesperson)other).getLastName()) &&
firstName.equals(((Salesperson)other).getFirstName()));
}
//--------------------------------------------------
// Order is based on total sales with the name
// (last, then first) breaking a tie.
//--------------------------------------------------
public int compareTo(Object other)
{
int result;
return result;
}
//-------------------------
// First name accessor.
//-------------------------
public String getFirstName()
{
Chapter 9: Polymorphism 185
return firstName;
}
//-------------------------
// Last name accessor.
//-------------------------
public String getLastName()
{
return lastName;
}
//-------------------------
// Total sales accessor.
//-------------------------
public int getSales()
{
return totalSales;
}
}
// *************************************************************
// WeeklySales.java
//
// Sorts the sales staff in descending order by sales.
// ************************************************************
public class WeeklySales
{
public static void main(String[] args)
{
Salesperson[] salesStaff = new Salesperson[10];
salesStaff[0] = new Salesperson("Jane", "Jones", 3000);
salesStaff[1] = new Salesperson("Daffy", "Duck", 4935);
salesStaff[2] = new Salesperson("James", "Jones", 3000);
salesStaff[3] = new Salesperson("Dick", "Walter", 2800);
salesStaff[4] = new Salesperson("Don", "Trump", 1570);
salesStaff[5] = new Salesperson("Jane", "Black", 3000);
salesStaff[6] = new Salesperson("Harry", "Taylor", 7300);
salesStaff[7] = new Salesperson("Andy", "Adams", 5000);
salesStaff[8] = new Salesperson("Jim", "Doe", 2850);
salesStaff[9] = new Salesperson("Walt", "Smith", 3000);
Sorting.insertionSort(salesStaff);
System.out.println (" Ranking of Sales for the Week ");
for (Salesperson s : salesStaff)
System.out.println (s);
}
}
2.
// IntegerList.java
// Define an IntegerList class with methods to create, fill,
// sort, and search in a list of integers.
import java.util.Scanner;
public class IntegerList
{
int[] list; //values in the list
//-------------------------------------------------------
//create a list of the given size
//-------------------------------------------------------
public IntegerList(int size)
{
list = new int[size];
}
//-------------------------------------------------------
//fill array with integers between 1 and 100, inclusive
//-------------------------------------------------------
public void randomize()
{
for (int i=0; i<list.length; i++)
list[i] = (int)(Math.random() * 100) + 1;
}
//-------------------------------------------------------
//print array elements with indices
//-------------------------------------------------------
public void print()
{
for (int i=0; i<list.length; i++)
System.out.println(i + ": " + list[i]);
}
//-------------------------------------------------------
//return the index of the first occurrence of target in the list.
//return -1 if target does not appear in the list
//-------------------------------------------------------
public int search(int target)
{
int location = -1;
for (int i=0; i<list.length && location == -1; i++)
if (list[i] == target)
location = i;
return location;
}
//-------------------------------------------------------
//sort the list into ascending order using the selection sort algorithm
//-------------------------------------------------------
public void selectionSort()
{
int minIndex;
for (int i=0; i < list.length-1; i++)
{
//find smallest element in list starting at location i
minIndex = i;
for (int j = i+1; j < list.length; j++)
if (list[j] < list[minIndex])
minIndex = j;
//swap list[i] with smallest element
int temp = list[i];
list[i] = list[minIndex];
list[minIndex] = temp;
}
}
}
// IntegerListTest.java
// Provide a menu-driven tester for the IntegerList class.
import java.util.Scanner;
public class IntegerListTest
{
static IntegerList list = new IntegerList(10);
static Scanner scan = new Scanner(System.in);
//-------------------------------------------------------
// Create a list, then repeatedly print the menu and do what the
// user asks until they quit
//-------------------------------------------------------
public static void main(String[] args)
{
printMenu();
int choice = scan.nextInt();
while (choice != 0)
{
dispatch(choice);
printMenu();
choice = scan.nextInt();
}
}
//-------------------------------------------------------
// Do what the menu item calls for
//-------------------------------------------------------
public static void dispatch(int choice)
{
int loc;
switch(choice)
{
case 0:
System.out.println("Bye!");
break;
case 1:
System.out.println("How big should the list be?");
int size = scan.nextInt();
list = new IntegerList(size);
list.randomize();
break;
case 2:
list.selectionSort();
break;
case 3:
System.out.print("Enter the value to look for: ");
loc = list.search(scan.nextInt());
if (loc != -1)
System.out.println("Found at location " + loc);
else
System.out.println("Not in list");
break;
case 4:
list.print();
break;
default:
System.out.println("Sorry, invalid choice");
}
}
//-------------------------------------------------------
// Print the user's choices
//-------------------------------------------------------
public static void printMenu()
{
System.out.println(" Menu ");
System.out.println(" ====");
System.out.println("0: Quit");
System.out.println("1: Create a new list (** do this first!! **)");
System.out.println("2: Sort the list using selection sort");
System.out.println("3: Find an element in the list using linear search");
System.out.println("4: Print the list");
System.out.print(" Enter your choice: ");
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.