Chapter 14, Problem 3PP

Program Plan Intro

To compare performance of algorithms

Program plan:

• In the file “StopWatch.java”, create a class “StopWatch”,
  • Declare private variable.
  • Define the constructor to construct a stopwatch that is in the stopped state and has no time accumulated.
  • Define the method “start()” to start the stopwatch, and time starts accumulating now.
  • Define the method “stop()” to stop the stopwatch, and time stops accumulating and is added to the elapsed time.
  • Define the method “getElapsedTime()” to return the total elapsed time.
  • Define the method “reset()” to stop the watch and resets the elapsed time to 0.
• In the file “MedianFinder.java”, create a class “MedianFinder”,
  • Define the method “median()” to compute the median of the elements in the data array using the recursive algorithm.
  • Define the method “select()” to find the k-largest element of an array.
  • Define the method “partition()” to partition an array into three regions.
  • Define the method “swap()” to swap two elements of an array at the specified positions.
• In the file “MedianFinderDemo.java”, import necessary packages, and create a class “MedianFinderDemo”,
  • Define the “main()” method,
    • Create an object for “Scanner”.
    • Create an “ArrayList”.
    • Get the file name from the user.
    • Execute loop till there is a record,
      • Read array from the file.
    • Declare an array.
    • Execute a loop,
      • Fill the array.
    • Create an object for “StopWatch”.
    • Declare necessary variables.
    • Call the method “start()” to start the timer.
    • Call the method “median()” to compute median.
    • Call the method “stop()” to stop.
    • Print the output obtained by using fast median algorithm.
    • Call the method “start()” to start the timer.
    • Call the method “sort()” to sort the array.
    • Check if the array length is even,
      • Compute median.
    • Call the method “stop()” to stop.
    • Print the output obtained by using naive median algorithm.