Arrays -- Examples

Sort

There are many kinds of sort programs. These are examples showing some common ways of writing two simple sorts: selection sort, and bubble sort. NOTE: You should rarely, if ever, write your own sort. Good sorts are available in the Java library in the java.util.Arrays.sort(...) and java.util.Collections.sort(...) methods.

Here are some questions that you should be able to answer about the sort algorithms.

1. Does this sort from low to high, or high to low?
2. How can you change it to sort in the other direction.
3. How can you change this to sort doubles?
4. How can you change this to sort Strings?
5. How many comparisons and exchanges are made?
6. How much work does it do if the array is already sorted?
7. [an error occurred while processing this directive] How much work does it do if the array is already sorted backwards?
8. After each pass, where are the sorted numbers?

Median

This method computes the median (middle) value of an array. The array must be sorted before calling this method. It returns the middle element, or the average of the two middle elements if there are an even number of elements. Actually, the entire array doesn't need to be sorted, only up to and including the middle element(s).

//================================================== median

// Precondition: Array must be sorted

public static double median(double[] m) {

int middle = m.length/2; // subscript of middle element

if (m.length%2 == 1) {

// Odd number of elements -- return the middle one.

return m[middle];

} else {

// Even number -- return average of middle two

// Must cast the numbers to double before dividing.

return (m[middle-1] + m[middle]) / 2.0;

}

}//end method median

Question: Does it matter if the array is sorted in ascending or descending order?

Fill an array with random values

Puts a random integer into each element in the array. Math.random() returns a double in the range 0.0-1.0, therefore we have to change the range, and cast to int.

//=============================================== fillRandom

public static void fillRandom(int[] a, int min, int max) {

int range = max-min;

for (int i=0; i <>

a[i] = min + (int)(Math.random()*range);

}

}//endmethod fillRandom