Transcript Sorting - Temple University

Sorting - CIS 1068
Program Design and Abstraction
Zhen Jiang
CIS Dept.
Temple University
SERC 347, Main Campus
Email: [email protected]
4/13/2016
1
Table of Contents



Introduction to sorting in Java
Types of things you can sort
Exercise
4/13/2016
2
Mechanics of Sorting in Java

Java has built-in ways to sort arrays and
ArrayLists:
Arrays.sort(myArray);
Collections.sort(myArrayList);

Note that these are static methods in the
Arrays and Collections classes, NOT
instance methods!
NOT: myArray.sort();
NOT: myArrayList.sort();

temperatureArray:
51.7

33.9
21.6
62.1
59.0
44.5
After
Arrays.sort(temperatureArray):
21.6
33.9
44.5
51.7
59.0
62.1

temperatureArrayList:
51.7

33.9
21.6
62.1
59.0
44.5
After
Collections.sort(temperatureArrayList):
21.6
33.9
44.5
51.7
59.0
62.1
Types of things you can sort

The Arrays.sort() method applies to
arrays, but arrays have types.


E.g., int[], double[], Object[], Point[]
Arrays.sort() can sort:


any primitive array type
any Object array type that implements the
Comparable<T> interface.

The Collections.sort() method applies
to ArrayLists, but ArrayLists have types.


E.g., ArrayList<Integer>,
ArrayList<Object>,
ArrayList<String []>
Likewise, Collections.sort() can sort:

ArrayList<T>, if T implements the
Comparable<T> interface
Exercise

Insertion sorting and its implementation


http://www.cis.temple.edu/~jiang/1068practice14.pdf
Partial insertion sorting and its implementation

2nd prize?
4/13/2016
8
public static int SecondPrize (int [ ] x){
int p1, p2;
if (x.length<2)return-1;
if(x[0]<x[1]) {p1=1; p2=0;}
else {p1 = 0; p2=1;}
for (int i = 2; i<x.length; i++){
int v = x[i];
if (v>x[p1]){
p2 = p1; p1 = i;}
else if (v>x[p2]){
p2 = i;}
}
return p2;
}
4/13/2016
9

Partial insertion sorting and its implementation

3rd prize?
4/13/2016
10