Locating peaks in array of data PART#1: write a program that scans through an ar
ID: 2849458 • Letter: L
Question
Locating peaks in array of data
PART#1: write a program that scans through an array of data, finds the peaks based on the criterion defined above, and sorts them into non-descending order.
0.2000 0.5000 0.1000 0.1500 0.2000 0.1300 0.3000 0.2500 0.3000 0.3000
0.7000 0.2000 0.4500 0.1500 0.2000 0.8500 0.3000 0.6500 0.2000 0.1000
Print the elements of x[], 10 on each line.
Then locate the peaks in x[], place them in an array peaks[]
Print the index and data for each peak, in the sorted order
A sample run:
unixlab% java FindPeaks
Data array:
0.2000 0.5000 0.1000 0.1500 0.2000 0.1300 0.3000 0.2500 0.3000 0.3000
0.7000 0.2000 0.4500 0.1500 0.2000 0.8500 0.3000 0.6500 0.2000 0.1000
5 peaks found:
1 0.5
10 0.7
12 0.45
15 0.85
17 0.65
unixlab%
PART#2: Hence, in non-decreasing order, the peaks would be listed as x[12], x[1], x[17], x[10], x[15].
Once we’ve built the array containing the peaks, there are several ways to sort the peaks. You can obviously use java.util.Arrays.sort(); This is easy, but you won’t be able to report the index of each peak.
Another way is to just copy the selection sort code we saw in class. You do have to make some small changes so you remember what indices the peaks came from.
A sample run:
Data array:
0.2000 0.5000 0.1000 0.1500 0.2000 0.1300 0.3000 0.2500 0.3000 0.3000
0.7000 0.2000 0.4500 0.1500 0.2000 0.8500 0.3000 0.6500 0.2000 0.1000
5 peaks found:
1 0.5
10 0.7
12 0.45
15 0.85
17 0.65
Sorted peaks:
12 0.45
1 0.5
17 0.65
10 0.7
15 0.85
unixlab%
Explanation / Answer
// A divide and conquer solution to find a peak element element
class Peak{
// A binary search based function that returns index of a peak element
double findPeakUtil(double arr[], double low, double high, double n)
{
// Find index of middle element
int mid = low + (high - low)/2; /* (low + high)/2 */
// Compare middle element with its neighbours (if neighbours exist)
if ((mid == 0 || arr[mid-1] <= arr[mid]) &&
(mid == n-1 || arr[mid+1] <= arr[mid])){
System.out.println(mid);
return mid;
}
// If middle element is not peak and its left neighbor is greater than it
// then left half must have a peak element
else if (mid > 0 && arr[mid-1] > arr[mid]){
System.out.println(mid);
return findPeakUtil(arr, low, (mid -1), n);}
// If middle element is not peak and its right neighbor is greater than it
// then right half must have a peak element
else {
System.out.prdoubleln(mid);
return findPeakUtil(arr, (mid + 1), high, n);}
}
// A wrapper over recursive function findPeakUtil()
double findPeak(double arr[], double n)
{
return findPeakUtil(arr, 0, n-1, n);
}
}
public class Welcome {
public static void main(String[] args) {
double arr[] = {0.2000,0.5000,0.1000,0.1500,0.2000,0.1300,0.3000,0.2500,0.3000,0.3000
,0.7000,0.2000,0.4500,0.1500,0.2000,0.8500,0.3000,0.6500,0.2000,0.1000};
double n = arr.length;
Peak p=new Peak();
p.findPeak(arr, n);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.