Question

IN JAVA Searching and Sorting In An Integer List

File IntegerList contains a Java class representing a list of integers. The following public methods are

provided:

? IntegerList(int size)—creates a new list of size elements. Elements are initialized to 0.

? void randomize()—fills the list with random integers between 1 and 100, inclusive.

? void print()—prints the array elements and indices

? int search(int target)—looks for value target in the list using a linear (also called sequential) search

algorithm. Returns the index where it first appears if it is found, -1 otherwise.

? void selectionSort()—sorts the lists into ascending order using the selection sort algorithm.

File IntegerListTest contains a Java program that provides menu-driven testing for the IntegerList class.

Copy both files to your directory, and compile and run IntegerListTest to see how it works. For example, create

a list, print it, and search for an element in the list. Does it return the correct index? Now look for an element

that is not in the list. Now sort the list and print it to verify that it is in sorted order.

Modify the code in these files as follows:

1. Add a method void replaceFirst(int oldVal, int newVal) to the IntegerList class that replaces the first

occurrence of oldVal in the list with newVal. If oldVal does not appear in the list, it should do nothing (but

it’s not an error). If oldVal appears multiple times, only the first occurrence should be replaced. Note that

you already have a method to find oldVal in the list; use it!

Add an option to the menu in IntegerListTest to test your new method.

2. Add a method void replaceAll(int oldVal, int newVal) to the IntegerList class that replaces all occurrences

of oldVal in the list with newVal. If oldVal does not appear in the list, it should do nothing (but it’s not an

error). Does it still make sense to use the search method like you did for replaceFirst, or should you do

your own searching here? Think about this.

Add an option to the menu in IntegerListTest to test your new method.

3. Add a method void sortDecreasing() to the IntegerList class that sorts the list into decreasing (instead of

increasing) order. Use the selection sort algorithm, but modify it to sort the other way. Be sure you change

the variable names so they make sense!

Add an option to the menu in IntegerListTest to test your new method.

4. Add a method int binarySearchD (int target) to the IntegerList class that uses a binary search to find the

target assuming the list is sorted in decreasing order. If the target is found, the method should return its

index; otherwise the method should return –1. Your algorithm will be a modification of the binary search

algorithm in the text.

Add an option to the menu in IntegerListTest to test your new method. In testing, make sure your method

works on a list sorted in descending order then see what the method does if the list is not sorted

(it shouldn’t be able to find some things that are in the list).

// ****************************************************************
// IntegerListTest.java
// ****************************************************************
import java.util.Scanner;
public class IntegerListTest
{
static IntegerList list = new IntegerList(10);
static Scanner scan = new Scanner(System.in);

public static void main(String[] args)
{
printMenu();
int choice = scan.nextInt();
while (choice != 0)
{
dispatch(choice);
printMenu();
choice = scan.nextInt();
}
}

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;
case 5:
System.out.println("Enter old value you want to replace: ");
int oldVal = scan.nextInt();
System.out.println("Enter new value: ");
int newVal = scan.nextInt();
list.replaceFirst(oldVal, newVal);
break;
case 6:
System.out.println("Enter the old value: ");
int oldVal2 = scan.nextInt();
System.out.println("Enter new value: ");
int newVal2 = scan.nextInt();
list.replaceAll(oldVal2, newVal2);
break;
case 7:
list.sortDecreasing();
break;
case 8:
System.out.println("What number would you like?");
int answer = scan.nextInt();
list.binarySearch(answer);
break;
  
default:
System.out.println("Sorry, invalid choice");
}
}
//------------------------------------------------------
// Print the user's choices
//------------------------------------------------------
public static void printMenu()
{
System.out.println("\n 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.println("5: Replace a value");
System.out.println("6: Replace all values");
System.out.println("7: Sort in decreasing number");
System.out.println("8: Find the number");
System.out.print("\nEnter your choice: ");
}
}

// *************************************************************
// IntegerList.java
// *************************************************************

public class IntegerList
{
int[] list; //values in the list

public IntegerList(int size)
{
list = new int[size];
}

public void randomize()
{
for (int i=0; i<list.length; i++)
list[i] = (int)(Math.random() * 100) + 1;
}

public void print()
{
for (int i=0; i<list.length; i++)
System.out.println(i + ":\t" + list[i]);
}

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;
}

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;
}
}

public void replaceFirst(int oldVal, int newVal){
int something = this.search(oldVal);
if( something == -1){
System.out.println("Nothing");}
else{
list[something] = newVal;}
}

public void replaceAll(int oldVal, int newVal){
int counter = 0;
for(int i=0;i<list.length;i++){
if(list[i] == oldVal){
list[i] = newVal;
counter++;}}
if (counter == 0){
System.out.println("Could not find your number");}
}

public void sortDecreasing(){
int minIndex;
for (int i=0; i < list.length-1; i++)
{
minIndex = i;
for (int j = i+1; j < list.length; j++){
if (list[j] > list[minIndex]){
minIndex = j;}
int temp = list[i];
list[i] = list[minIndex];
list[minIndex] = temp;}
}
}

public void binarySearch(Integer target)
{
int min = 0, max = list.length - 1, mid = 0;
boolean found = false;
while (!found && min <= max)
{
mid = (min + max) / 2;
if (target.equals(list[mid]))
found = true;
else
if ((target.compareTo(list[mid])) < 0)
max = mid - 1;
else
min = mid + 1; // works in increasing order, not decreasing :(
}
if (found)
System.out.println("found the number! the index is: " + mid);
else
System.out.println("could not find it");
}

}

Answer 1

Sample Run1 Results of Given Code:

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 1
How big should the list be?
15

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 4
0:      37
1:      98
2:      93
3:      20
4:      67
5:      1
6:      7
7:      34
8:      1
9:      92
10:     39
11:     23
12:     23
13:     47
14:     8

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 3
Enter the value to look for: 34
Found at location 7

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 5
Enter old value you want to replace: 
20
Enter new value: 
40

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 4
0:      37
1:      98
2:      93
3:      40
4:      67
5:      1
6:      7
7:      34
8:      1
9:      92
10:     39
11:     23
12:     23
13:     47
14:     8

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 6
Enter the old value: 
23
Enter new value: 
33

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 4
0:      37
1:      98
2:      93
3:      40
4:      67
5:      1
6:      7
7:      34
8:      1
9:      92
10:     39
11:     33
12:     33
13:     47
14:     8

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 2

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 4
0:      1
1:      1
2:      7
3:      8
4:      33
5:      33
6:      34
7:      37
8:      39
9:      40
10:     47
11:     67
12:     92
13:     93
14:     98

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 8
What number would you like?
39
found the number! the index is: 8

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 7

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 4
0:      98
1:      93
2:      92
3:      67
4:      47
5:      40
6:      39
7:      37
8:      34
9:      33
10:     33
11:     8
12:     7
13:     1
14:     1

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 0

Sample Run2 Results of Given Code:

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 1
How big should the list be?
20

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 4
0:      48
1:      72
2:      75
3:      22
4:      66
5:      10
6:      47
7:      65
8:      77
9:      85
10:     28
11:     6
12:     17
13:     8
14:     2
15:     59
16:     52
17:     74
18:     22
19:     88

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 3
Enter the value to look for: 34
Not in list

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 5
Enter old value you want to replace: 
43
Enter new value: 
54
Nothing

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 6
Enter the old value: 
56
Enter new value: 
66
Could not find your number

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 2

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 4
0:      2
1:      6
2:      8
3:      10
4:      17
5:      22
6:      22
7:      28
8:      47
9:      48
10:     52
11:     59
12:     65
13:     66
14:     72
15:     74
16:     75
17:     77
18:     85
19:     88

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 8
What number would you like?
67
could not find it

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 7

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 4
0:      88
1:      85
2:      77
3:      75
4:      74
5:      72
6:      66
7:      65
8:      59
9:      52
10:     48
11:     47
12:     28
13:     22
14:     22
15:     17
16:     10
17:     8
18:     6
19:     2

 Menu 
 ====
0: Quit
1: Create a new list (** do this first!! **)
2: Sort the list using selection sort
3: Find an element in the list using linear search
4: Print the list
5: Replace a value
6: Replace all values
7: Sort in decreasing number
8: Find the number

Enter your choice: 0