Java - Data structures P3 (35 points) The median of a collection of values is th
ID: 3816449 • Letter: J
Question
Java - Data structures
P3 (35 points)
The median of a collection of values is the middle value. One way to find the median is to sort the data and take the value at the center. But sorting does more than necessary to find the median. You need to find only the kth smallest entry in the collection for an appropriate value of k. To find the median of n items, you would take k as n/2 rounded up
You can use the partitioning strategy of quick sort to find the kth smallest entry in an array. After choosing a pivot and forming the subarrays Smaller and Larger, you can draw one of the following conclusions:
If Smaller contains k or more entries, it must contain the kth smallest entry
If Smaller contains k-1 entries, the kth smallest entry is the pivot.
If Smaller contains fewer than k-1 entries, the kth smallest entry is in Larger.
Implement the recursive method
public satic int findKSmallest(int[] a, int k)
that finds the kth smallest entry in an unsorted array a.
Use the method findKSmallest to implement the method
public static int findMedian(int[] a)
that finds the median in an array a.
Java - Data Structures
public class ArraySort
{
public static <T extends Comparable<? super T>>
void mergeSort(T[] a, int n) {
mergeSort(a, 0, n - 1);
}
public static <T extends Comparable<? super T>>
void mergeSort(T[] a, int first, int last) {
@SuppressWarnings("unchecked")
T[] tempArray = (T[])new Comparable<?>[a.length];
mergeSort(a, tempArray, first, last);
}
private static <T extends Comparable<? super T>>
void mergeSort(T[] a, T[] tempArray, int first, int last)
{
if (first < last) { // sort each half
int mid = (first + last) / 2;// index of midpoint
mergeSort(a, first, mid); // sort left half array[first..mid]
mergeSort(a, mid + 1, last); // sort right half array[mid+1..last]
if (a[mid].compareTo(a[mid + 1]) > 0)
merge(a, tempArray, first, mid, last); // merge the two halves
// else skip merge step
}
}
private static <T extends Comparable<? super T>>
void merge(T[] a, T[] tempArray, int first, int mid, int last)
{
// Two adjacent subarrays are a[beginHalf1..endHalf1] and a[beginHalf2..endHalf2].
int beginHalf1 = first;
int endHalf1 = mid;
int beginHalf2 = mid + 1;
int endHalf2 = last;
// while both subarrays are not empty, copy the
// smaller item into the temporary array
int index = beginHalf1; // next available location in
// tempArray
for (; (beginHalf1 <= endHalf1) && (beginHalf2 <= endHalf2); index++) {
if (a[beginHalf1].compareTo(a[beginHalf2]) < 0) {
tempArray[index] = a[beginHalf1];
beginHalf1++;
}
else {
tempArray[index] = a[beginHalf2];
beginHalf2++;
}
}
// finish off the nonempty subarray
// finish off the first subarray, if necessary
for (; beginHalf1 <= endHalf1; beginHalf1++, index++)
tempArray[index] = a[beginHalf1];
// finish off the second subarray, if necessary
for (; beginHalf2 <= endHalf2; beginHalf2++, index++)
tempArray[index] = a[beginHalf2];
// copy the result back into the original array
for (index = first; index <= last; index++)
a[index] = tempArray[index];
}
// Quick Sort
// Median-of-three privot selection
// Sort by comparison
private static <T extends Comparable<? super T>>
void sortFirstMiddleLast(T[] a, int first, int mid, int last)
{
// Note similarity to bubble sort
order(a, first, mid); // make a[first] <= a[mid]
order(a, mid, last); // make a[mid] <= a[last]
order(a, first, mid); // make a[first] <= a[mid]
}
private static <T extends Comparable<? super T>>
void order(T[] a, int i, int j)
{
if (a[i].compareTo(a[j]) > 0)
swap(a, i, j);
}
private static void swap(Object[] array, int i, int j)
{
Object temp = array[i];
array[i] = array[j];
array[j] = temp;
}
// Partitioning
private static <T extends Comparable<? super T>>
int partition(T[] a, int first, int last)
{
int mid = (first + last)/2;
sortFirstMiddleLast(a, first, mid, last);
// move pivot to next-to-last position in array
swap(a, mid, last - 1);
int pivotIndex = last - 1;
T pivot = a[pivotIndex];
// determine subarrays Smaller = a[first..endSmaller]
// and Larger = a[endSmaller+1..last-1]
// such that entries in Smaller are <= pivot and
// entries in Larger are >= pivot; initially, these subarrays are empty
int indexFromLeft = first + 1;
int indexFromRight = last - 2;
boolean done = false;
while (!done) {
// starting at beginning of array, leave entries that are < pivot;
// locate first entry that is >= pivot; you will find one,
// since last entry is >= pivot
while (a[indexFromLeft].compareTo(pivot) < 0)
indexFromLeft++;
// starting at end of array, leave entries that are > pivot;
// locate first entry that is <= pivot; you will find one,
// since first entry is <= pivot
while (a[indexFromRight].compareTo(pivot) > 0)
indexFromRight--;
if (indexFromLeft < indexFromRight)
{
swap(a, indexFromLeft, indexFromRight);
indexFromLeft++;
indexFromRight--;
}
else
done = true;
} // end while
// place pivot between Smaller and Larger subarrays
swap(a, pivotIndex, indexFromLeft);
pivotIndex = indexFromLeft;
return pivotIndex;
}
public static <T extends Comparable<? super T>>
void quickSort(T[] a, int n) {
quickSort(a, 0, n - 1);
}
public static <T extends Comparable<? super T>>
void quickSort(T[] a, int first, int last) {
// perform recursive step if 2 or more elements
if(first < last) {
// create the partition: Smaller | Pivot | Larger
int pivotIndex = partition(a, first, last);
// sort subarrays Smaller and Larger
quickSort(a, first, pivotIndex - 1);
quickSort(a, pivotIndex + 1, last);
}
}
}
Explanation / Answer
HI, Please find my implementation.
Please let me know in case of any issue.
/*
The idea is, not to do complete quicksort, but stop at the point where pivot itself is k’th smallest element.
Also, not to recur for both left and right sides of pivot, but recur for one of them according to the position of pivot.
The worst case time complexity of this method is O(n2), but it works in O(n) on average.
*/
public class KSmallest {
public static int findKSmallest(int[] a, int k){
return kthSmallestHelper(a, 0, a.length-1, k);
}
// This function returns k'th smallest element in arr[l..r] using
// QuickSort based method. ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT
private static int kthSmallestHelper(int arr[], int l, int r, int k)
{
// If k is smaller than number of elements in array
if (k > 0 && k <= r - l + 1)
{
// Partition the array around last element and get
// position of pivot element in sorted array
int pos = partition(arr, l, r);
// If position is same as k
if (pos-l == k-1)
return arr[pos];
if (pos-l > k-1) // If position is more, recur for left subarray
return kthSmallestHelper(arr, l, pos-1, k);
// Else recur for right subarray
return kthSmallestHelper(arr, pos+1, r, k-pos+l-1);
}
// If k is more than number of elements in array
return Integer.MIN_VALUE;
}
// Standard partition process of QuickSort(). It considers the last
// element as pivot and moves all smaller element to left of it
// and greater elements to right
private static int partition(int arr[], int l, int r)
{
int x = arr[r], i = l;
for (int j = l; j <= r - 1; j++)
{
if (arr[j] <= x)
{
swap(arr, i, j);
i++;
}
}
swap(arr, i, r);
return i;
}
private static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static int findMedian(int[] a){
int mid = a.length/2+1; // median is 4th element
int median = findKSmallest(a, mid);
return median;
}
public static void main(String[] args) {
int arr[] = {12, 3, 5, 7, 4, 19, 26};
int median = findMedian(arr);
System.out.println("Median: "+median);
}
}
/*
Sample run:
Median: 7
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.