Problem. Professor Zak allows students to drop the three lowest scores on the ni
ID: 3689941 • Letter: P
Question
Problem. Professor Zak allows students to drop the three lowest scores on the nine! 100-point quizzes she gives during the semester. Design and code an application that accepts a student name and the nine quiz scores. Output the student's name and the total points for the six highest scoring quizzes. Then output the corresponding letter grade and words of advice. Use structured programming. range test the input data for the grades. create a table to match the numeric score with a letter grade. Use a parallel array to map the letter grade with an appropriate words of advice.
Explanation / Answer
Pseudocode:
start
perform housekeeping()
while not eof
perform mainLoop()
endwhile
perform finishUp()
stop
housekeeping()
declare variables
open files
perform headings()
read stuRec
return
headings()
print heading1
print heading2
return
mainLoop()
perform sortScores()
sub = 1
total = 0
while sub <= 8
total = total + stuScore[sub]
sub = sub + 1
endwhile
print stuIdNum, stuLastName, stuFirstName, total
read stuRec
return
sortScores()
y = 1
while y < 10
x = 1
while x < 10
if stuScore[x] < stuScore[x + 1]
perform switchTwoValues()
endif
x = x + 1
endwhile
y = y + 1
endwhile
return
switchTwoValues()
temp = stuScore[x + 1]
stuScore[x + 1] = stuScore[x]
stuScore[x ] = temp
return
finishUp()
close files
return
Bubble Sort
As a prelude to searching
One of the most basic operations that we perform on one dimensional arrays, is the operation of sorting (or ordering) the values stored into the array. The values can be sorted into either ascending (from smallest to largest) or descending order (from largest to smallest). For the purposes of illustration most of the examples we do will sort the array elements into ascending order. (the smallest value will be in the first element)
One of the simplest sorting algorithms is the “Bubble Sort”, this is usually the first sorting algorithm presented to students, and while the simplest to learn and code, it is also the least efficient. In this algorithm,
As an example consider the following 5 element integer array:
14
5
10
9
1
0
1
2
3
4
We start at the beginning of the array and compare consecutive elements:
In the first “PASS” through the array
14
5
10
9
1
0
1
5
14
10
9
1
14 is larger than 5, so we swap the elements
5
14
10
9
1
1
2
14 is again larger than 10, so we swap the two elements
5
10
14
9
1
5
10
14
9
1
2
3
Again 14 is larger than 9
5
10
9
14
1
5
10
9
14
1
3
4
14 is larger than 1
5
10
9
1
14
Each “pass” through the array will sort one element into it’s correct position. In the first pass the largest element is sorted into it’s correct position. Now we need only consider n-1 remaining elements.
We continue making passes through the array until all elements are in their correct position.
After pass 2 the array will look like:
5
9
1
10
14
After pass 3 :
5
1
9
10
14
Finally after pass 4 :
1
5
9
10
14
The array is sorted!!!!!
To write this in code we need to consider the following things:
We can implement this algorithm using nested loops!!!!
Implementation 1, write a program to create an integer array named alpha with 10 elements. Prompt the user to enter 10 values and store them into the array. Sort the array elements using a bubble sort.
import java.util.*;
public class sort1 {
public static void main(String args[]) {
int[] alpha = new int [10];
Scanner in = new Scanner(System.in);
// read 10 values into the array
System.out.println(“Please enter 10 integer values”);
for (int i=0; i<alpha.length; i++)
alpha[i] = in.nextInt();
// begin the bubble sort
// make N-1 passes through the array
for (int i=1; i < alpha.length; i++) {
// compare N-1 pairs of elements.
for (int j = 0; j < alpha.length; j++) {
// Compare adjacent elements and swap if needed.
if ( alpha[j] > alpha[j+1] ) {
alpha[j] = alpha[j+1];
alpha[j+1] = alpha[j];
} // end if
} // end inner for
} // end outer for
System.out.println(“The sorted array is: “);
for (int i=0; i<alpha.length; i++)
System.out.println(“alpha[“ + i + “] is: “ + alpha[i]);
} // end main
} // end class
However, the result of running this program generates an
“array out of bounds exception”
Java generates this exception, when ever an array index is less than zero, or greater than the upper bounds of the array… So what happened? The problem must lie, in one of our for loops!!!! The problem is in the loop:
// compare N-1 pairs of elements.
for (int j = 0; j < alpha.length; j++) {
We loop while j < # elements in alpha… so j ranges from 0 to 9. When j is 9, The if statement inside the loop compares elements alpha[j] and alpha[j+1]. Well j=9 and j+1 = 10… there is NO alpha[10]…. WE need to adjust our loop exit condition to fix this.
Implementation 2:
import java.util.*;
public class sort1 {
public static void main(String args[]) {
int[] alpha = new int [10];
Scanner in = new Scanner(System.in);
This version produces the following output:
Please enter 10 integer values
9 5 10 15 2 6 11 15 7 1
The sorted array is:
alpha[0] is: 1
alpha[1] is: 1
alpha[2] is: 1
alpha[3] is: 1
alpha[4] is: 1
alpha[5] is: 1
alpha[6] is: 1
alpha[7] is: 1
alpha[8] is: 1
alpha[9] is: 1
System.out.println(“Please enter 10 integer values”);
for (int i=0; i<alpha.length; i++)
alpha[i] = in.nextInt();
// make N-1 passes through the array
for (int i=1; i < alpha.length; i++) {
// compare N-1 pairs of elements.
for (int j = 0; j < alpha.length - 1; j++) {
if ( alpha[j] > alpha[j+1] ) {
alpha[j] = alpha[j+1];
alpha[j+1] = alpha[j];
} // end if
} // end inner for
} // end outer for
System.out.println(“The sorted array is: “);
for (int i=0; i<alpha.length; i++)
System.out.println(“alpha[“ + i + “] is: “ + alpha[i]);
} // end main
} // end class
The problem in this version lies with the swap. WE do:
alpha[j] = alpha[j+1];
alpha[j+1] = alpha[j];
This puts the value of alpha[j+1] into alpha[j], then puts the value alpha[j] into alpha[j+1]
So after this assignment both elements contain the same value.. the original value of alpha[j] is lost!!! We need to use a temporary variable to preserve the value of alpha[j].
implementation 3:
import java.util.*;
public class sort1 {
public static void main(String args[]) {
int[] alpha = new int [10];
This version produces the following output:
Please enter 10 integer values
9 5 10 15 2 6 11 15 7 1
The sorted array is:
alpha[0] is: 1
alpha[1] is: 2
alpha[2] is: 5
alpha[3] is: 6
alpha[4] is: 7
alpha[5] is: 9
alpha[6] is: 10
alpha[7] is: 11
alpha[8] is: 15
alpha[9] is: 15
Scanner in = new Scanner(System.in);
int temp;
System.out.println(“Please enter 10 integer values”);
for (int i=0; i<alpha.length; i++)
alpha[i] = in.nextInt();
// make N-1 passes through the array
for (int i=1; i < alpha.length; i++) {
// compare N-1 pairs of elements.
for (int j = 0; j < alpha.length - 1; j++) {
if ( alpha[j] > alpha[j+1] ) {
temp = alpha[j];
alpha[j] = alpha[j+1];
alpha[j+1] = temp;
} // end if
} // end inner for
} // end outer for
System.out.println(“The sorted array is: “);
for (int i=0; i<alpha.length; i++)
System.out.println(“alpha[“ + i + “] is: “ + alpha[i]);
} // end main
} // end class
Example2, sorting an array of strings:
import java.util.*;
public class sortNames {
public static void main(String args[]) {
Please enter 10 names
greg
larry
tom
william
john
brett
camille
ian
terry
audrey
The sorted array is:
names[0] is: audrey
names[1] is: brett
names[2] is: camille
names[3] is: greg
names[4] is: ian
names[5] is: john
names[6] is: larry
names[7] is: terry
names[8] is: tom
names[9] is: william
String[] names= new String[10];
Scanner in = new Scanner(System.in);
String temp;
System.out.println("Please enter 10 names");
for (int i=0; i<names.length; i++)
names[i]= in.nextLine();
// make N-1 passes through the array
for (int i=1; i < names.length; i++) {
// compare N-1 pairs of elements.
for (int j = 0; j < (names.length-1); j++) {
if ( (names[j].compareTo(names[j+1])) > 0 ) {
temp = names[j];
names[j] = names[j+1];
names[j+1] = temp;
} // end if
} // end inner for
} // end outer for
System.out.println("The sorted array is: ");
for (int i=0; i<names.length; i++)
System.out.println("names[" + i + "] is: " + names[i]);
} // end main
} // end class
Example 3: Write a static method bubble to sort arrays of integers in ascending order.
import java.util.*;
public class sort2 {
public static void main(String args[]) {
int[] alpha= new int[10];
Scanner in = new Scanner(System.in);
int temp;
System.out.println("Please enter 10 alpha");
for (int i=0; i<alpha.length; i++)
alpha[i]= in.nextInt();
bubble(alpha);
System.out.println("The sorted array is: ");
for (int i=0; i<alpha.length; i++)
System.out.println("alpha[" + i + "] is: " + alpha[i]);
Please enter 10 alpha
5 8 2 10 9 15 12 7 4 1
The sorted array is:
alpha[0] is: 1
alpha[1] is: 2
alpha[2] is: 4
alpha[3] is: 5
alpha[4] is: 7
alpha[5] is: 8
alpha[6] is: 9
alpha[7] is: 10
alpha[8] is: 12
alpha[9] is: 15
} // end main
public static void bubble(int[] anArray) {
int temp;
// make N-1 passes through the array
for (int i=1; i < anArray.length; i++) {
// compare N-1 pairs of elements.
for (int j = 0; j < (anArray.length-1); j++) {
if ( anArray[j] > anArray[j+1] ) {
temp = anArray[j];
anArray[j] = anArray[j+1];
anArray[j+1] = temp;
} // end if
} // end inner for
} // end outer for
} // end bubble
} // end class
Increasing the efficiency of the bubble sort a bit.
One way we can eliminate some comparisons is to adjust the exit condition of our inner loop
public static void bubble(int[] anArray) {
int temp;
// make N-1 passes through the array
for (int i=0; i < anArray.length; i++) {
// compare N-1 pairs of elements.
// Assuming that each pass (controlled by the outer loop) places one element in its
// correct position, then after each pass “ i ” elements have been correctly places
// so these elements no longer need to be compared
for (int j = 0; j < (anArray.length-1) - i ; j++) {
if ( anArray[j] > anArray[j+1] ) {
temp = anArray[j];
anArray[j] = anArray[j+1];
anArray[j+1] = temp;
} // end if
} // end inner for
} // end outer for
} // end bubble
} // end class
Analysis of the bubble sort:
We classify sorting algorithms by determining an expression representing the maximum (worst case) or average number of comparisons required to sort the array – this is called the Big O notation. The dominate or largest term in the expression becomes the O value of the expression.
for the bubble sort, to sort an array of N entries, in the worst case every entry is out of order. Each “pass” through the array accounts for N-1 comparisons, and since we traverse the array N-1 times… our expression is :
(N-1)2 or (N-1) * (N-1) = N2 –N –N +1 = N2 -2N +1
N2 is the dominate term so the bubble sort is an O(N2) algorithm.
Other interesting operations on Arrays:
Copying Arrays:
Since arrays are reference objects, we can not simply duplicate an array using assignment.
int grades = { 77, 82, 91, 100, 88};
int scores = grades;
does the following: int grades = { 77, 82, 91, 100, 88};
grades
77
82
91
100
88
scores=grades;
grades
77
82
91
100
88
scores
This creates a shallow copy of the original array object. To create two arrays, with duplicate values (A “deep” copy) we need to declare each separately, and then use a loop to copy all of the values from one array to the other or:
To create a duplicate of an array, or any object instance, ….. use method “clone” inherited from class Object
scores = grades.clone();
Will create a new 5 element integer array, containing the same values as array “grades” and will store the address of the new array into scores.
77
82
91
100
88
Scores
77
82
91
100
88
14
5
10
9
1
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.