A. Write a method to measure sortedness of an array. Themethod header is:
public static double sortedness(Comparable[] array)
B. Write an iterative method to measure sortedness of acollection of linked nodes. The method header is:
public static double sortednessIterative(Node<Comparable> node)
C. Write a recursive method to measure sortedness of acollection of linked nodes.
For full extra credit points, use only one recursivepass through the chain. (Hint: you might need to consider adifferent approach to recursion than the one we’ve used in ourclass!)
The method header is:
public static double sortednessIterative(Node<Comparable> node)
There are different ways to measure the degree of sortedness.For the task, compare neighbor elements. The degree of sortednessis the percentage of neighbor-matches that are in sorted order.(This is often described using the term inversions, whichis two elements such that the index of element1 is < the indexof element2, but element1 is greater than element2.)
For our purposes, we are considering only ascending order(smallest to largest) as being sorted.
- Example: [2, 2, 4, 6, 7] has a 100% sortedness factor- allneighbor pairs of numbers are sorted
- Example: [2, 2, 6, 4, 7] has a 75% sortedness factor- the 6-4neighbor pair is not sorted, but all other neighbor pairs (2-2,2-6, and 4-7) are sorted
- Example: [7, 6, 4, 2, 1] has a 0% sortedness factor- noneighbor pairs are sorted in ascending order.
Expert Answer
. . .