Notes

package SearchAndSort;

public class searchAndSort {

public static void fillArray (int[] myArray) {
for (int i = 0; i < myArray.length; i ++)
myArray[i] = (int) (Math.random() * 100 + 1);
}

public static void printArray(int[] myArray) {
for (int i = 0; i < myArray.length; i ++)
System.out.print(myArray[i] + " ");
System.out.println();
}

public static int linearSearch (int[] numbers, int searchValue) {
int loc = 0;
while ( loc < numbers.length && numbers[loc] != searchValue ) {
loc++;
}
if (loc == numbers.length) { //Not found
return -1;
} else {
return loc; //Found, return the position
}
}

public static int linSearch(int[] data, int searchKey) {
// loop through array sequentially
for (int index = 0; index < data.length; index++)
if (data[index] == searchKey)
return index; // return index of integer
return -1; // integer was not found
} // end method linearSearch


// N + N-1 + N-2 + N-3 + ... + 2 + 1 = (1 + N) * N / 2 = (N^2 + N ) / 2
public static int binarySearch (int[] number, int searchValue) {
int low = 0,
high = number.length - 1,
mid = (low + high) / 2;

while (low <= high && number[mid] != searchValue) {
if (number[mid] < searchValue) {
low = mid + 1;
} else { //number[mid] > searchValue
high = mid - 1;
}
mid = (low + high) / 2;
}
if (low > high) {
mid = -1;
}
return mid;
}

public static void selectionSort(int[] number) {

int minIndex, length, temp;
length = number.length;

for (int startIndex = 0; startIndex <= length-2; startIndex++){
minIndex = startIndex;
for (int i = startIndex+1; i <= length-1; i++) {
if (number[i] < number[minIndex])
minIndex = i;
}

//exchange number[startIndex] and number[minIndex]
temp = number[startIndex];
number[startIndex] = number[minIndex];
number[minIndex] = temp;

assert minStart(number, startIndex):
"Error: " + number[startIndex] + " at position " + startIndex +
" is not the smallest.";
}

assert isSorted(number): "Error: the final is not sorted";
}

private static boolean minStart(int[] number, int startIndex) {
for (int i = startIndex+1; i < number.length; i++) {
if (number[startIndex] > number[i]) {
return false;
}
}
return true;
}

private static boolean isSorted(int[] number) {
for (int i = 0; i < number.length-1; i++) {
if (number[i] > number[i+1]) {
return false;
}
}
return true;
}


public static void bubbleSort(int[] number) {

int temp, bottom;
boolean exchanged = true;
bottom = number.length - 2;

while (exchanged) {
exchanged = false;
for (int i = 0; i <= bottom; i++) {
if (number[i] > number[i+1]) {
temp = number[i]; //exchange
number[i] = number[i+1];
number[i+1] = temp;

exchanged = true; //exchange is made
}
}
assert maxBottom(number, bottom): "Error: " + number[bottom] +
" at position " + bottom + " is not the largest.";

bottom--;
}
assert isSorted(number): "Error: the final is not sorted";
}

private static boolean maxBottom(int[] number, int lastIndex) {
for (int i = 0; i < lastIndex; i++) {
if (number[lastIndex] < number[i]) {
return false;
}
}
return true;
}
}