Jka at 21:43, 26 April 2007

2007-04-26T21:43:43Z

New page

==Sequential Search==
* Suppose that we have an unsorted array of numbers
* We know that a particular number is in the array
* We want the position of that number
===Code===
<pre>
public int seqSearch(int[] a, int value, int index) {
int result;
if (index >= a.length) {
result = -1;
} else if (value == a[index]) {
result = index;
} else {
result = seqSearch(a, value, index + 1);
}
return result;
}
</pre>
==Binary Search==
* The binary search algorithm takes advantage of the fact that a set of values in an array are ordered
* We probe into the middle of the array and if we do not find the value that we are looking for, we throw 1/2 of the values away
===Code===
<pre>
public int binSearch(int[] a, int target, int first, int last) {
int result;
int middle;
middle = (first + last) / 2;
if (last < first) {
result = -1;
} else if (a[middle] == target) {
result = middle;
} else if (a[middle] < target) {
result = binSearch(a, target, middle + 1, last);
} else {
result = binSearch(a, target, first, middle - 1);
}
return result;
}
</pre>
===Problem===
* Note that binary search is fast
* ''But'', to use it we must have the values sorted and sorting can be expensive to do
* If we are only going to make one or two searches, it might not be worth sorting the values
* If we are going to make repeated searches (student records, bank records, inventory), sorting the values will have great benefit
==''for'' loop==
* The structure of a ''for'' loop is:
for (<init>; <bool expr>; <incre>)
<statement>;
===Which should you use?===
* Is the number of times you will perform some action fixed and will not change?
* Will you need to perform an action a variable number of times including possibly zero times?
* Will you need to perform an action a variable number of times including at least once?
==Selection Sort==
===Algorithm===
# For all positions, k, in the array from n down to one
# Find the largest element in the subarray 0..k
## Save k as the position of the largest so far
## For all values of j from k-1 down to 0
## If the element at j is bigger than the largest so far, save j as the position of the largest so far
# If the largest element is not in position k then switch the largest element with the one at position k
===Code===
<pre>
public void selectSort(int[] val) {
int k, j, indexOfMax, temp;
for (k=val.length-1; k>=1; k--) {
indexOfMax = k;
for (j=k-1; j>=0; j--) {
if (val[j] > val[indexOfMax]) {
indexOfMax = j;
}
}
if (indexOfMax != k) {
temp = val[k];
val[k] = val[indexOfMax];
val[indexOfMax] = temp;
}
}
}
</pre>
==Bubble Sort==
===Algorithm===
# Repeat
# For each pair of adjacent array elements do
## Initialize noExchanges to True
## For each pair of adjacent array elements do
# If the values of the pair are out of order then
## Exchange the values
## Set noExchanges to False
===Code===
<pre>
public void bubbleSort(int[] val) {
boolean noExchanges;
int first, pass, temp;
pass = 1;
do {
noExchanges = true;
for (first = 0; first <= val.length - 1 - pass; first++) {
if (val[first] > val[first + 1]) {
temp = val[first];
val[first] = val[first + 1];
val[first + 1] = temp;
noExchanges = false;
}
}
pass = pass + 1;
} while (! noExchanges);
}
</pre>
==[[CIS 3020 Part 9]]==

CIS 3020 Part 8 - Revision history

Jka at 21:43, 26 April 2007