Computer Science 15-100 (Sections T & U), Spring 2008
Class Notes: Using Arrays (part 2)
Logistics
Topic Outline:
public class MoreArraysSamples {
// Sieve of Eratosthenes
// Searching:
// Linear Search + Binary Search
// Sorting:
// Selection, Insertion, Bubble sorts
public static java.util.Scanner scanner = new java.util.Scanner(System.in);
public static java.util.Random random = new java.util.Random();
public static void example00_sieve_of_eratosthenes() {
System.out.print("Find all primes up to what value: ");
int max = scanner.nextInt();
int[] primes = findPrimes(max);
printArray(primes);
}
// uses the "Sieve of Eratosthenes" to compute all
// primes between 2 and max, inclusive
public static int[] findPrimes(int max) {
boolean[] isComposite = new boolean[max+1]; // ignore 0 and 1
int primeCount = 0;
for (int prime=2; prime<=max; prime++) {
if (!isComposite[prime]) {
primeCount++;
// remove multiples of this prime from the sieve
for (int multiple=2*prime; multiple<=max; multiple += prime)
isComposite[multiple] = true;
}
}
int[] primes = new int[primeCount];
int i = 0;
for (int prime=2; prime<= max; prime++)
if (!isComposite[prime]) primes[i++] = prime;
return primes;
}
public static void example01_linear_search() {
System.out.print("Check for primes primes up to what value: ");
int max = scanner.nextInt();
int[] primes = findPrimes(max);
int n;
while (true) {
System.out.print("Enter a number [<=0 to exit]: ");
n = scanner.nextInt();
if (n <= 0)
break;
else if (n > max)
System.out.println("Too big -- only checking up to " + max);
else {
int index = linearSearch(primes,n);
if (index < 0)
System.out.println(n + " is not prime");
else
System.out.println(n + " is the " + (index+1) + "th prime");
}
}
}
// returns the index where n occurs in a[], or -1 if it does not
public static int linearSearch(int[] a, int n) {
for (int i=0; i<a.length; i++)
if (a[i] == n)
return i;
return -1;
}
public static void example02_binary_search() {
System.out.print("Check for primes primes up to what value: ");
int max = scanner.nextInt();
int[] primes = findPrimes(max);
int n;
while (true) {
System.out.print("\nEnter a number [<=0 to exit]: ");
n = scanner.nextInt();
if (n <= 0)
break;
else if (n > max)
System.out.println("Too big -- only checking up to " + max);
else {
int index = binarySearch(primes,n);
if (index < 0)
System.out.println(n + " is not prime");
else
System.out.println(n + " is the " + (index+1) + "th prime");
}
}
}
// returns the index where n occurs in a[], or -1 if it does not
public static int binarySearch(int[] a, int n) {
int guesses = 0; // just for accounting
System.out.println("Binary search in array of size " + a.length);
System.out.print("Guesses: ");
int lo, mid, hi;
lo = 0;
hi = a.length-1;
while (lo <= hi) {
mid = (lo + hi)/2;
guesses++;
if (guesses > 1) System.out.print(", ");
System.out.print("a[" + mid + "]=" + a[mid]);
if (a[mid] == n) {
System.out.println("\nFound it in " + guesses + " guesses.");
return mid;
}
else if (n > a[mid])
lo = mid+1;
else
hi = mid-1;
}
System.out.println("\nDid not find it in " + guesses + " guesses.");
return -1;
}
public static void example03_one_pass_of_bubblesort() {
int[] a = makeArray(4);
boolean changed;
printArray(a);
changed = bubblesortPass(a);
if (changed) {
System.out.print("New array: ");
printArray(a);
}
else
System.out.println("No change -- it is sorted!");
}
public static boolean bubblesortPass(int[] a) {
boolean changed = false;
for (int i=1; i<a.length; i++)
if (a[i] < a[i-1]) {
swap(a,i,i-1);
changed = true;
}
return changed;
}
public static void example04_bubblesort() {
int[] a = makeArray(8);
boolean changed;
do {
printArray(a);
changed = bubblesortPass(a);
} while (changed);
}
public static void example05_traditional_bubblesort() {
int[] a = makeArray(8);
printArray(a);
bubblesort(a);
printArray(a);
}
public static void bubblesort(int[] a) {
boolean changed;
do {
changed = false;
for (int i=1; i<a.length; i++)
if (a[i] < a[i-1]) {
swap(a,i,i-1);
changed = true;
}
} while (changed);
}
public static void example06_insertionsort() {
int[] a = makeArray(8);
printArray(a);
insertionsort(a);
printArray(a);
}
public static void insertionsort(int[] a) {
for (int i=1; i<a.length; i++) {
// insert a[i] into the sorted list a[0],a[1],...,a[i-1]
for (int j=i; ((j > 0) && (a[j] < a[j-1])); j--)
swap(a,j,j-1);
}
}
public static void example07_selectionsort() {
int[] a = makeArray(8);
printArray(a);
selectionsort(a);
printArray(a);
}
public static void selectionsort(int[] a) {
for (int i=0; i<a.length-1; i++) {
int minIndex = getIndexOfMin(a,i);
swap(a,i,minIndex);
}
}
public static int getIndexOfMin(int[] a, int fromIndex) {
if ((a == null) || (a.length == 0))
return -1;
int i, minIndex = fromIndex;
for (i=fromIndex+1; i<a.length; i++)
if (a[i] < a[minIndex])
minIndex = i;
return minIndex;
}
///////////////////
// from last time (ArraysSamples.java)
///////////////////
public static void printArray(int[] a) {
System.out.print("a[] = {");
int i;
for (i=0; i<a.length; i++) {
if (i > 0) System.out.print(", ");
System.out.print(a[i]);
}
System.out.println("}");
}
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static int[] makeArray(int size) {
int[] result = new int[size];
loadArray(result);
return result;
}
public static void loadArray(int[] a) {
// load the array
int i;
for (i=0; i<a.length; i++) // a.length equals 10 here
a[i] = random.nextInt(100);
}
////////////////////////////////
// Helper code
////////////////////////////////
public static void main(String[] args) {
java.util.ArrayList<String> examples = new java.util.ArrayList<String>();
try {
Class c = Class.forName("MoreArraysSamples");
java.lang.reflect.Method[] methods = c.getMethods();
for (java.lang.reflect.Method method : methods) {
if (method.getName().startsWith("example"))
examples.add(method.getName());
}
java.util.Collections.sort(examples);
}
catch (Exception e) {
e.printStackTrace();
}
while (true) {
System.out.println("\n--------------------------");
System.out.println("Choose from these examples:");
for (int i=0;i<examples.size();i++)
System.out.println(" " + examples.get(i));
System.out.print("\nWhich example: [<0 to exit] ");
int choice = scanner.nextInt();
System.out.println("\n--------------------------");
if (choice < 0) break;
else if (choice >= examples.size())
System.out.println("No such example");
else try {
Class c = Class.forName("MoreArraysSamples");
java.lang.reflect.Method m = c.getMethod(examples.get(choice));
m.invoke(null);
}
catch (Exception e) {
e.printStackTrace();
}
}
}
}
carpe diem - carpe diem - carpe diem - carpe diem - carpe diem - carpe diem - carpe diem - carpe diem - carpe diem