The median of an array of integers is the value that would belong in the middle
ID: 3590501 • Letter: T
Question
The median of an array of integers is the value that would belong in the middle position of the array if the array were sorted. For example, consider the following array:
The median of this array is 15, because that value would end up in the middle position if the array were sorted:
If an array has an even number of elements, the median is the average of the elements that would belong in the middle two positions of the array if the array were sorted.
In the file Median.java, implement a program that finds the median of an array of integers by using the partitioning approach taken by quicksort. However, for the sake of efficiency, you should not sort a subarray if it could not contain the median.
In Median.java, we have given you the following:
copies of the swap() and partition() methods from our Sort class. The recursive method that you will write should call the partition() method to process the necessary portions of the array (see below). You should not need to change these methods.
the skeleton of a method named findMedian() that will serve as a “wrapper” method around your recursive median-finding method, just as the quickSort() method in our Sort class serves as a wrapper around the recursive qSort() method. To implement this wrapper method, all you need to do is add an appropriate initial call to your recursive method. You should not change the header of this method in any way.
a main() method that you should fill with code that tests your median-finding algorithm. We have included sample definitions of odd- and even-length arrays that you can use as you see fit. Make sure that your main() method calls the wrapper method, rather than calling the recursive method directly.
The recursive method that you write will be similar to the recursive qSort() method in our Sort class. However, you will need to modify the algorithm so that it allows you to put the median value or values in the appropriate positions without actually sorting the entire array. You are expected to only sort as much of the array as is necessary to determine the median value, and for full credit you must avoid calling partition() on subarrays that could not possibly contain the median value (see below).
Your recursive method only needs to succeed in getting the median value (or values, in the case of an even array) into the middle position (or positions, in the case of an even array). It does not need to return the median value; it may simply be a void method. Your main() method can then print the median value by looking at the value(s) in the middle position(s) of the array after your algorithm has finished.
Hints:
Your recursive method will be similar to our qSort() method. However, after you call partition(), you need to determine whether to make recursive call(s) to process just the left subarray, just the right subarray, or both subarrays, depending on whether each subarray could contain the median value (or, in the case of an even-length array, at least one of the two median values). When making this decision, remember that after a call to partition(), everything in the left subarray is less than or equal to everything in the right subarray. Given this fact, and given the location(s) where the median value(s) must ultimately end up, you should be able to determine whether you need to make a recursive call on a particular subarray. Tracing through some concrete examples may help you to discover the logic.
(Note: Rather than checking to see whether a given recursive call is needed, it is also possible to defer this checking to the start of the next invocation of the method. In other words, the recursive method could begin by checking to see if the current subarray could contain one or more of the median values, and, if it could not, the method could return without doing anything.)
You should be able to accomplish this task with only 4-10 lines worth of changes/additions to the standard quicksort algorithm. If your modifications to the code in qSort() are substantially longer than this, you are likely on the wrong track.
Explanation / Answer
Below is your code. I have also coded Sort class.
Median.java
public class Median {
/* partition - helper method for your recursive median-finding method */
private static int partition(int[] arr, int first, int last) {
int pivot = arr[(first + last)/2];
int i = first - 1; // index going left to right
int j = last + 1; // index going right to left
while (true) {
do {
i++;
} while (arr[i] < pivot);
do {
j--;
} while (arr[j] > pivot);
if (i < j)
Sort.swap(arr, i, j);
else
return j; // index of last element in the left subarray
}
}
/*
* findMedian - "wrapper" method for your recursive median-finding method.
* It just makes the initial call to that method, passing it
* whatever initial parameters make sense.
*/
public static void findMedian(int[] arr) {
fMedian(arr, 0, arr.length - 1);
// even and odd arrays
int median = arr[arr.length/2];
System.out.println("median value 1: " + median);
// if even array
if(arr.length % 2 == 0){
int median2 = arr[(arr.length/2)-1];
System.out.println("median value 2: " + median2);
}
}
/* fMedian - recursive method that does the work for findMedian */
private static void fMedian(int[] arr, int first, int last) {
int split = partition(arr, first, last);
// only process left sub-array if split >
if (first < split && split >= arr.length/2 - 1)
fMedian(arr, first, split);// left subarray
if (last > split + 1 && split <= arr.length/2 - 1)
fMedian(arr, split + 1, last); // right subarray
}
/*
* Put the definition of your recursive median-finding method below.
*/
public static void main(String[] args) {
// the median of this array is 15
int[] oddLength = {4, 18, 12, 34, 7, 42, 15, 22, 5};
// the median of this array is the average of 15 and 18 = 16.5
int[] evenLength = {4, 18, 12, 34, 7, 42, 15, 22, 5, 27};
System.out.println("*****************");
System.out.println("odd: ");
Sort.printArray(oddLength);
findMedian(oddLength);
Sort.printArray(oddLength);
System.out.println("*****************");
System.out.println("even: ");
Sort.printArray(evenLength);
findMedian(evenLength);
Sort.printArray(evenLength);
}
}
Sort.java
/**
* Sort - a class containing implementations of various array-sorting
* algorithms. Each method takes an array of ints. The methods assume that the
* array is full. They sort the array in place, altering the original array.
*/
public class Sort {
public static final int NUM_ELEMENTS = 20;
/*
* swap - swap the values of two variables. Used by several of the sorting
* algorithms below.
*/
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
/*
* indexSmallest - returns the index of the smallest element in the subarray
* from arr[lower] to arr[upper]. Used by selectionSort.
*/
private static int indexSmallest(int[] arr, int lower, int upper) {
int indexMin = lower;
for (int i = lower + 1; i <= upper; i++)
if (arr[i] < arr[indexMin])
indexMin = i;
return indexMin;
}
/** selectionSort */
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int j = indexSmallest(arr, i, arr.length - 1);
swap(arr, i, j);
}
}
/** insertionSort */
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
if (arr[i] < arr[i - 1]) {
// Save a copy of the element to be inserted.
int toInsert = arr[i];
// Shift right to make room for element.
int j = i;
do {
arr[j] = arr[j - 1];
j = j - 1;
} while (j > 0 && toInsert < arr[j - 1]);
// Put the element in place.
arr[j] = toInsert;
}
}
}
/** shellSort */
public static void shellSort(int[] arr) {
/*
* Find initial increment: one less than the largest power of 2 that is
* <= the number of objects.
*/
int incr = 1;
while (2 * incr <= arr.length)
incr = 2 * incr;
incr = incr - 1;
/* Do insertion sort for each increment. */
while (incr >= 1) {
for (int i = incr; i < arr.length; i++) {
if (arr[i] < arr[i - incr]) {
int toInsert = arr[i];
int j = i;
do {
arr[j] = arr[j - incr];
j = j - incr;
} while (j > incr - 1 && toInsert < arr[j - incr]);
arr[j] = toInsert;
}
}
// Calculate increment for next pass.
incr = incr / 2;
}
}
/** bubbleSort */
public static void bubbleSort(int[] arr) {
for (int i = arr.length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1])
swap(arr, j, j + 1);
}
}
}
/* partition - helper method for qSort */
private static int partition(int[] arr, int first, int last) {
int pivot = arr[(first + last) / 2];
int i = first - 1; // index going left to right
int j = last + 1; // index going right to left
while (true) {
do {
i++;
} while (arr[i] < pivot);
do {
j--;
} while (arr[j] > pivot);
if (i < j)
swap(arr, i, j);
else
return j; // index of last element in the left subarray
}
}
/* qSort - recursive method that does the work for quickSort */
private static void qSort(int[] arr, int first, int last) {
int split = partition(arr, first, last);
if (first < split)
qSort(arr, first, split); // left subarray
if (last > split + 1)
qSort(arr, split + 1, last); // right subarray
}
/** quicksort */
public static void quickSort(int[] arr) {
qSort(arr, 0, arr.length - 1);
}
/* merge - helper method for mergesort */
private static void merge(int[] arr, int[] tmp, int leftStart, int leftEnd, int rightStart, int rightEnd) {
int i = leftStart; // index into left subarray
int j = rightStart; // index into right subarray
int k = leftStart; // index into tmp
while (i <= leftEnd && j <= rightEnd) {
if (arr[i] < arr[j])
tmp[k++] = arr[i++];
else
tmp[k++] = arr[j++];
}
while (i <= leftEnd)
tmp[k++] = arr[i++];
while (j <= rightEnd)
tmp[k++] = arr[j++];
for (i = leftStart; i <= rightEnd; i++)
arr[i] = tmp[i];
}
/** mSort - recursive method for mergesort */
private static void mSort(int[] arr, int[] tmp, int start, int end) {
if (start >= end)
return;
int middle = (start + end) / 2;
mSort(arr, tmp, start, middle);
mSort(arr, tmp, middle + 1, end);
merge(arr, tmp, start, middle, middle + 1, end);
}
/** mergesort */
public static void mergeSort(int[] arr) {
int[] tmp = new int[arr.length];
mSort(arr, tmp, 0, arr.length - 1);
}
/**
* printArray - prints the specified array in the following form: { arr[0]
* arr[1] ... }
*/
public static void printArray(int[] arr) {
System.out.print("{ ");
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
System.out.println("}");
}
/**
* modeFinder
*/
public static int modeFinder(int[] arr) {
// merge sort the array
mergeSort(arr);
// init the mode
int mode = arr[0];
int modeFrequence = 0;
int tempFrequence = 0;
// go through all elements 1 time!
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] == arr[i + 1]) {
tempFrequence++;
} else if (tempFrequence > modeFrequence) {
modeFrequence = tempFrequence;
mode = arr[i];
tempFrequence = 0;
} else {
tempFrequence = 0;
}
}
return mode;
}
/**
* removeDups - Remove duplicates from an already sorted array eturn int
* number of unique values in the array
*/
private static Integer removeDups(int[] iSortedArr) {
// assume input is good
Integer nbUniqueValues = 1;
Integer position = 1;
// start at 1:
// the first element is at the good position
for (Integer i = 1; i < iSortedArr.length; i++) {
if (iSortedArr[i - 1] != iSortedArr[i]) {
iSortedArr[position] = iSortedArr[i];
position++;
nbUniqueValues++;
}
}
// fill the end of the array with 0s
for (Integer i = 0; i < iSortedArr.length - nbUniqueValues; i++) {
iSortedArr[nbUniqueValues + i] = 0;
}
return nbUniqueValues;
}
public static void main(String[] arr) {
int[] orig = new int[NUM_ELEMENTS];
for (int i = 0; i < NUM_ELEMENTS; i++) {
orig[i] = (int) (50 * Math.random());
}
printArray(orig);
int[] copy = new int[NUM_ELEMENTS];
/* selection sort */
System.arraycopy(orig, 0, copy, 0, orig.length);
selectionSort(copy);
System.out.print("selection sort: ");
printArray(copy);
/* insertion sort */
System.arraycopy(orig, 0, copy, 0, orig.length);
insertionSort(copy);
System.out.print("insertion sort: ");
printArray(copy);
/* Shell sort */
System.arraycopy(orig, 0, copy, 0, orig.length);
shellSort(copy);
System.out.print("Shell sort: ");
printArray(copy);
/* bubble sort */
System.arraycopy(orig, 0, copy, 0, orig.length);
bubbleSort(copy);
System.out.print("bubble sort: ");
printArray(copy);
/* quicksort */
System.arraycopy(orig, 0, copy, 0, orig.length);
quickSort(copy);
System.out.print("quicksort: ");
printArray(copy);
/* mergesort */
System.arraycopy(orig, 0, copy, 0, orig.length);
mergeSort(copy);
System.out.print("mergesort: ");
printArray(copy);
/* remove duplicates */
Integer nbUniques = removeDups(copy);
System.out.print(nbUniques + " uniques items, ");
System.out.print("remove duplicates: ");
printArray(copy);
/* mode finder */
System.arraycopy(orig, 0, copy, 0, orig.length);
int mode = modeFinder(copy);
System.out.print("mode: " + mode);
}
}
Output
*****************
odd:
{ 4 18 12 34 7 42 15 22 5 }
median value 1: 15
{ 4 5 7 12 15 18 34 22 42 }
*****************
even:
{ 4 18 12 34 7 42 15 22 5 27 }
median value 1: 18
median value 2: 15
{ 4 5 7 12 15 18 22 34 42 27 }