Transcript File

Get out your notes.
Array Review
Selection Sort
Learning Objectives
• Be able to dry run programs that use arrays
• Be able to dry run programs that use arrays.
• Understand and be able to implement a
Selection Sort.
Dry run 1
int[] egArray = { 2, 4, 6, 8, 10, 1, 3, 5, 7, 9 };
for ( int index= 0 ; index < 5 ; index++ )
System.out.print( egArray[ index ] + " " );
Dry Run 2
int[] egArray = { 2, 4, 6, 8, 10, 1, 3, 5, 7, 9 };
for ( int index= 0 ; index < egArray.length ; index++ )
System.out.print( egArray[ index ] + " " );
Dry Run 3
int[] egArray = { 2, 4, 6, 8, 10, 1, 3, 5, 7, 9 };
for ( int index= 0 ; index < egArray.length ; index = index + 2 )
System.out.print( egArray[ index ] + " " );
Modify the code
Fill in the blanks of the following code fragment so
that the elements of the array are printed
in reverse order, starting with the last element.
int[] egArray = { 2, 4, 6, 8, 10, 1, 3, 5, 7, 9 };
for ( int index= ________ ; _____________ ; ______________ )
System.out.print( egArray[ index ] + " " )
Dry Run 4
int[] array = { 1, 4, 3, 6, 8, 2, 5};
int what = array[0];
// scan the array
for ( int index=0; index < array.length; index++ )
{
if ( array[ index ] > what )
what = array[ index ];
}
System.out.println( what );
Dry Run 5
int[] array = { 1, 4, 3, 6, 8, 2, 5};
int what = array[0];
// scan the array
for ( int index=0; index < array.length; index++ )
{
if ( array[ index ] < what )
what = array[ index ];
}
System.out.println( what );
Dry Run 6
int[] array = { 1, 4, 3, 6 };
int what = 0;
// scan the array
for ( int index=0; index < array.length; index++ )
{
what = what + array[ index ] ;
}
System.out.println( what );
7) Fill in the blank in the following
code fragment so that each element
of the array is assigned twice the
value of its index.
int[] array = new int[10];
// scan the array
for ( int index=0; index < array.length; index++ )
{
_______________________
}
Dry Run 8
int [] list = { 10, 11, 4, 8, 2 } ;
for(int start = 1; start < list.length; start++)
{
int temp = list[start];
int k = start;
while(k > 0 && list[k-1] > temp)
{
list[k] = list[k-1];
k--;
}
list[k] = temp;
}
for (int s:list)
System.out.print(s +" ");
System.out.println();
public static void main (String [] args)
{
int [] a = { 10, 11, 4, 8, 2 } ;
int out, in, min;
int dummy;
for (out=0; out<a.length-1; out++)
{
min = out;
for(in=out+1; in<a.length; in++)
if(a[in] < a[min] )
min = in;
dummy = a[out];
a[out] = a[min];
a[min] = dummy;
for (int s:a)
System.out.print(s +" ");
System.out.println();
} // end for(out)
}
Dry Run 9
Learning Objectives
• Review reading a nested loop program.
• Understand how the selection and
insertion sorts work
• Write a program that uses the selection
and insertion sorts.
What did the previous Code do?
Selection sort
•
•
•
•
•
•
•
•
•
How it works
Example
Low
High
2 6 8 3 15 1 7
Stability
Speed
Your turn
High
Low
8 2 5 3 9 4 6 1 7
• Check, mark, switch
• Not stable
• O(n2)
Selection Sort
//a is the array name,
// nElems = the number of elements being sorted
int out, in, min;
int dummy; // If sorting an array of ints
for(out=0; out<nElems-1; out++) // outer loop
{
min = out; // minimum
for(in=out+1; in<nElems; in++) // inner loop
if(a[in] < a[min] ) // Check if min greater,
min = in; // Mark, we have a new min
dummy = a[out]; //Switch
a[out] = a[min];
a[min] = dummy;
} // end for(out)
import java.util.Scanner; // program uses class Scanner
public class SelectionSort
{
public static void main(String args[])
{
String[] names = new String[5];
String name;
// create Scanner to obtain input from command window
Scanner input = new Scanner( System.in );
for (int count = 0 ; count < names.length; count++)
{
System.out.println("Please enter a name");
names[count] = input.next();
}
for (int j=0; j<names.length; j++)
{
System.out.println(names[j]);
}
//Insert Sort Code here
First Program
Check for
Understanding
Enter this into
BlueJ and test to
make sure it is
sorting.
System.out.println("The names ...");
for (String temp: names) // For each String temp in the array names.
System.out.println(temp);
}
}
Selection Sort Program
• Input 11 scores
• Output:
– Numbers in sorted order (Low to High)
– Mean (average)
– Median (Middle number after sorting)
• Push:
– Find the mode
– Let the user tell you how many scores prior to
entering the scores
– Modify it so the user can continually enter scores
(semantics of a while loop) and calculates the above
when they are finished.