Transcript Slide 1

Advanced Array Concepts
Chapter 9

Sorting


Ascending order


Process of arranging series of objects in some
logical order
Begin with object that has lowest value
Descending order

Start with object that has largest value

Simplest possible sort
Involves two values that are out of order
 Swap two values
{16, 2} →
{2, 16}
temp = valA; // 16 goes to temp
valA = valB; // 2 goes to valA
valB = temp; // 16 goes to valB


Bubble sort

Continue to compare pairs of items

Swapping them if they are out of order
for(int a = 0; a < myList.length - 1; a++)
for(int b = 0; b < myList.length - 1; b++)
if (myList[b] > myList[b+1]) {
temp = myList[b];
myList[b] = myList[b+1];
myList[b+1] = temp;
}

Selection sort
Finds the smallest number in the list and places
it first. It then finds the smallest number
remaining and places it next to first, and so on
until the list contains only a single number.
 Can also find the largest number in the list and
place it last.


Make passes through the list (or part of it)
on each pass select one item (smallest or
largest) to be correctly position
 exchange that item with the one that was in its
place

67
33
21
84
49
50
78
21
33
67
84
49
50
78

On successive passes

must only check beyond where smallest item
has been placed
21


33
67
84
49
50
A pair of nested for() loops will
accomplish this checking and swapping of
values
Note: this is a simple but inefficient
algorithm
78

As list is built, keep it sorted

always place a new value in the list where it belongs
49

Tasks include





21
33
67
49
84
67
84
finding where the new item belongs
shifting all elements from that slot and beyond over
one slot
inserting the new item in the vacated spot
Again, a double nested loop can accomplish this
task
This is efficient for small lists



Very efficient
Implemented by a recursive algorithm
Strategy





choose a pivot point
perform exchanges so all elements to the left are less
than the pivot
all elements on the right are greater
this makes 2 sub lists where the same strategy with the
pivot can be performed (repeatedly)
this is a "divide and conquer" concept

Since sorting is frequently used in programming,
Java provides several overloaded sort methods for
sorting an array of int, double, char, short, long, and
float in the java.util.Arrays class.
 For example, the following code sorts an array of
numbers and an array of characters.
double[] numbers = {6.0, 4.4, 1.9, 2.9, 3.4, 3.5};
java.util.Arrays.sort(numbers);
char[] chars = {'a', 'A', '4', 'F', 'D', 'P'};
java.util.Arrays.sort(chars);


Many data types are in a table
format
Need two indices to access
elements of the table

Row and column
myList [a][b]
Also possible to have higher
dimensional arrays



n-dimensional array requires n
indeces
Student #
Test 1
1
85
2
92
3
90
4
74
5
83


Row
Requires two indices
Which cell is
MILEAGE_CHART [3][2]?
[0]
[1]
[2]
[3]
[4]
[5]
[0]
0
97
90
268
262
130
[1]
97
0
74
337
144
128
[2]
90
74
0
354
174
201
[3]
268
337
354
0
475
269
[4]
262
144
174
475
0
238
[5]
130
128
201
269
238
0
Column




In Java, a 2-D array is basically a 1-D array of
1-D arrays, its rows. Each row is stored in a
separate block of consecutive memory
locations.
If m is a 2-D array, then myList[k] is a 1-D
array, the k-th row.
myList.length is the number of rows.
myList[k].length is the length of the k-th row.
12-13

A 2-D array can be traversed using nested loops:


Number of rows is myList.length
Number of columns is myList[0].length
for (int r = 0; r < myList.length; r++)
{
for (int c = 0; c < myList[0].length; c++)
{
... // process myList[ r ][ c ]
}
}
12-14


Java allows “ragged” arrays, in which
different rows have different lengths.
In a rectangular array, m[0].length can be
used to represent the number of columns.
“Ragged” array:
Rectangular array:
m.length
m[3].length
m.length
m[0].length
12-15

“Transpose a matrix” idiom:
int n = m.length;
for (int r = 1; r < n; r++)
{
for (int c = 0; c < r; c++)
{
double temp = m [ r ][ c ];
m [ r ][ c ] = m [ c ][ r ];
m [ c ][ r ] = temp;
}
}
The total number of
iterations through the
inner loop is:
1 + 2 + 3 + ... + (n-1) =
n (n - 1) / 2
12-16



Recall that arrays represent a class of
objects
We used shortcut notation as a convenience
to bypass the class
The array class has useful tools
import java.util.Arrays;
import java.util.ArrayList;








ArrayList() //constructor
void add(int index, Object x)
boolean add(Object x)
Object set(int index, Object x)
Object remove(int index)
int size ()
Object get(int index)
Iterator iterator()

add:
boolean add(Object x) – inserts the Object x at
the end of the list (size increases by 1), returns
true
 void add(int index, Object x) – inserts the Object
x at the given index position (elements will be
shifted to make room and size increases by 1)


get:
returns the Object at the specified index
 should cast when using value returned
 throws IndexOutOfBoundsException if index<0
or index>=size


set
replaces value of Object parameter at the given
index
 size is not changed


remove
removes the element at the specified index
 throws IndexOutOfBoundsException if index<0
or index>=size
 size will be decreased by 1
 returns Object removed

ArrayList club = new
ArrayList();
club.add(“Spanky”);
club.add(“Darla”);
club.add(“Buckwheat”);
System.out.print(club);
Displays:
[Spanky, Darla, Buckwheat]
//using club from previous slide
club.set(1, “Mikey”);
System.out.print(club);
Displays:
[Spanky, Mikey, Buckwheat]
//using club from previous slide
club.add(0,
club.remove(club.size()-1));
System.out.print(club);
Displays:
[Buckwheat, Spanky, Mikey]
//ArrayLists only contain Objects!!
ArrayList odds = new ArrayList();
for(int i=1; i<10; i+=2)
odds.add(new Integer(i));
System.out.println(odds);
Displays:
[1, 3, 5, 7, 9]
//ArrayLists only contain Objects!!
ArrayList odds = new ArrayList();
for(int i=1; i<10; i+=2)
{ Integer x = new Integer(i);
odds.add(x);}
System.out.println(odds);
Displays:
[1, 3, 5, 7, 9]
//Casting when pulling out from ArrayList
ArrayList names = new ArrayList();
names.add("Clint");
names.add("John");
names.add("Robert");
names.add("Henry");
Object obj = names.get(2); //ok
System.out.println( obj.toString() );
String str1 = names.get(3); //syntax error
String str2 = (String)(names.get(4)); //ok
char c =
((String)(names.get(0))).charAt(0);
//Gack!!

iterator
returns an Iterator object
 Iterators allow all of the Objects in the list to be
accessed one by one, in order
 methods for an Iterator object

hasNext
 next
 remove



Returns true if the iteration has more
elements
Ex:
while(it.hasNext())
//do something



Returns the next element in the iteration
Each time this method is called the iterator
“moves”
Ex:
while(it.hasNext())
{
Object obj = it.next();
if( //obj meets some condition)
//do something
}
31


Removes from the collection the last
element returned by the iterator
Can be called only once per call to next
while(it.hasNext())
{
Object obj = it.next();
if( //obj meets some condition)
it.remove();
}
public void removeAllLength(ArrayList li, int len)
{
//pre: li contains only String objects
//post: all Strings of length = len removed
//right way
String temp;
for(int i = li.size()-1; i < 0; i--)
{
if( temp.length() == len )
li.remove(i);
}
}
What if the list contains ["hi", "ok", "the", "so", "do"] and len = 2?
public void removeAllLength(ArrayList li, int len)
{
//pre: li contains only String objects
//post: all Strings of length = len removed
//wrong way
String temp;
for(int i = 0; i < li.size(); i++)
{
temp = (String)li.get(i);
if( temp.length() == len )
li.remove(i);
}
}
Problem with this code:
Note that the index of each subsequent value changes
public void removeAllLength(ArrayList li, int len)
{
//pre: li contains only String objects
//post: all Strings of length = len removed
//right way using iterator
String temp;
iterator it = li.iterator();
while( it.hasNext() )
{
temp = (String)li.next();
if( temp.length() == len )
it.remove();
}
}
What if the list contains ["hi", "ok", "the", "so", "do"] and len = 2?

Linear search



begin with first item in a list
search sequentially until desired item found or reach
end of list
Binary search (of a sorted list)

look at middle element



if target value found, done
if target value is higher, look in middle of top half of list
if target value is lower, look in middle of lower half of
list
position = Arrays.binarySearch(myList, "Tim");

Recall that the array references a memory address




copy = myList still references the same memory
Any changes done to copy also changes myList
We can make a copy by populating element by
element
We can also make a copy by using the clone
method in the Arrays class
copy = myList.clone( );