Chapter 14, Problem 4PP

Program Plan Intro

Quicksort

Program plan:

Filename: “Main.java”

• Include the header files
• Define “Main” class
  • Define the “main” method
    • Declare the variables and set the values.
    • Create an object for “StopWatch” class
    • Call the required methods
    • Check the “a” value as sorted or not
      • Display the elapsed time.
    • Call the required methods
    • Check the “a2” value as sorted or not
      • Display the elapsed time
    • Define the “checkSorted” method
      • Iterate the loop to check the array  values are sorted or unsorted
        • Return false
        • • Return true

Filename: “ArrayUtil.java”

• Include the header files
• Define “ArrayUtil” class
  • Create an object for “Random” class
  • Define the “randomIntArray” method
    • Declare the array variable
    • Iterate the loop until it reaches array length
      • Generate the random values
    • Return the value
  • Define the “swap” method
    • Swap the values

Filename: “QuickSorter.java”

• Define “QuickSorter” class
  • Define the “sort” method
    • Call the “sort” method
  • Define the “sort” method with the arguments
    • Check the condition.
      • Return the value
        • Call the required methods
  • Define the “partition” method
    • Declare and the set the values
    • Check “i” is less than “j”
      • Increment the “i” value
      • Check “a[i]” is less than “pivot”
        • Increment the “i” value
      • Decrement the “j” value
      • Check “a[j]” is greater than “pivot”
        • Decrement the “j” value
      • Check “i” is less than “j”
        • Call the “swap” method
        • • Return the value

Filename: “QuickSorter2.java”

• Define “QuickSorter2” class
  • Define the “med” method
    • Check “a” is less than “b”
      • Check “b” is less than “c”
        • Return the value
      • Otherwise, find the maximum value
      • Otherwise, check “c” is less than “b”
        • Return the value
    • Otherwise, find the maximum value
  • Define the “getPivot” method
    • Declare the variable and set the value
    • Check the “n” is less than or equal to 7
      • return the value
    • Check the “n” is less than or equal to 40
      • return the value
    • otherwise, declare the array
      • check the condition
        • set the value
  • Define the “sort” method
    • Call the “sort” method
  • Define the “sort” method with the arguments
    • Check the condition.
      • Return the value
    • Call the required methods
  • Define the “partition” method
    • Declare and the set the values
    • Check “i” is less than “j”
      • Increment the “i” value
      • Check “a[i]” is less than “pivot”
        • Increment the “i” value
      • Decrement the “j” value
      • Check “a[j]” is greater than “pivot”
        • Decrement the “j” value
      • Check “i” is less than “j”
        • Call the “swap” method
    • Return the value

Filename: “StopWatch.java”

• Define “StopWatch” class
  • Declare the required variables
  • Define the constructor
    • Call the “reset” method
  • Define the “start” method
    • Check the condition
      • Return the value
        • Set the values
  • Define the “stop” method
    • Check the condition
      • Return the value
        • Set the values
  • Define the “getElaspedTime” method
    • Check the condition
      • Set the value
      • Return the value
        • Otherwise, return the elapsed time
  • Define the “reset” method
    • Set the value.