AIT 512 Quick Sort

A05-PA1 Quick SortT

ask 1: Code Setup

  • 11. Create a package “hw” (under src folder), if not already created.
  • 12. Create a sub-package “a05” under the package “hw”, if not already created.
  • 13. Create a sub-package “a051” under the package “a05”, if not already created.
  • 14. In the sub-package “a051” copy your last version of the following classes: ArrayUtilitty, Stopwatch, TimeAnalysis, Bag, FixedBagCapacity

Task 2: Understand How Quick Sort and Partitioning Works

  • 21. Watch the videos and read the materials related to how the quick sort and partitioning works.
  • 22. Create a table showing how the partitioning operations modify the array in sequential order – consider the pivot to be the leftmost element in the area to be partitioned (include the table in your PDF answer as text):
    • 25, 16, 21, 14, 26, 18, 23, 11, 20, 15, 22, 13, 17, 24, 12, 19
  • 23. Pick a random array of 10 elements and create a merge table (include the table in your PDF answer as text) – do not pick a trivial array (e.g. 1, 2, 3… or 9, 8, 7, …)

Task 3: Quick Sort Method

  • 31. In the “a051” package, create a public class named QuickSort and a public class named QuickSortTest
  • 32. In the class QuickSort create a private static method named partition that receives an array of integers, a start index and an end index and partition the subarray from start index to end index (inclusive) considering the first element as a pivot.
  • 33. In the class QuickSort create a private recursive static method sort that will sort a sub-array of the original array using quick sort method. It receives the array containing the sub-array to be sorted, the start index of the sub-array (inclusive) and the end index of the elements to be sorted. For empty and singleton sub-arrays do nothing, for all the other cases, partition calling the previous method, and based on the received pivot index, sort recursively the left sub-array and right sub-array of the pivot.
  • 34. In the class QuickSort create a public static method sort that will sort an array using quick sort method. It receives the array to be sorted and calls the recursive quick sort for the entire array.
  • 35. In the class QuickSortTest, create a static method named sortTest that will perform and print the result of a single test for the method sort from QuickSort class. It receives the name of the test, the array to be sorted and the expected result. It prints the received input, the result obtained by calling sort on the input, the expected result and if the test was succesful (the result is identical with the expected result). Returns true if they are identical.
  • 36. In the class QuickSortTest, create a static method named sortAllTests that will perform all the tests for sort method from class QuickSort. It must call the previous method for testing arrays each with the length of 0, 1, 2 (sorted), 2 (unsorted), 3 (sorted), 3 (decreasing), 7 (random) and 10 (random). The values in the array must be random (do not use arrays like: 1, 2, 3, … ). Do not use the same range for the arrays. The method must print at the end if all tests were successful or not.
  • 37. In the class QuickSortTest, create the main method and call the previous method.
  • 38. Check your resullts. Test and debug until your examples work well. Include a text with the obtained correct results in your submission.

Task 4 Experimental Time Analysis

  • 41. In the “a051” package, create a public class named QuickSortAnalysis
  • 42. In the class QuickSortAnalysis create a private static method meanTime (similar with previous mean time methods). It receives the name of the test, number of random executions and the length of the array. It returns a time analysis object containing the time analysis of the performed executions.
  • 43. In the class QuickSortAnalysis create a private static method, printMeanExecutionTimeGrowthTable. It receives the number of random executions per length, the starting length, the increment from one tested length to the next one and the endding length. It prints the growth table. Similar with previous growth tables.
  • 44. In the class QuickSortAnalysis, create the main method and call the previous method. Call for 10 big numbers, that will generate over 10ms execution time. Include a text with the obtained analysis in your PDF submission.
  • 45. Execute the program QuickSortAnalysis. Include a text with the obtained analysis in your PDF submission.

Task 5: Analyze the execution time and memory needs for the top-down merge sort.

  • 51. Explain in your own words which is the theoretical order of growth for the method. Explain why. (1-2 paragraphs)
  • 52. Draw a graph for the values obtained in the previous task.
  • 53. Explain if the graph confirms or not the theoretical order of growth above. (1-2 paragraphs)
  • 54. How the graphs compares with the graphs for the previous sorts? Is the result expected (1-2 paragraphs)
  • 55. Analyze the memory needs for this sort method. Are they relevant? Why? (1-2 paragraphs)

Grading: 0.90 points (see grading rubric for details)

Global Submission Instruction:

  • You must follow the instructions described in the folder: “512 All Modules”, subfolder “A00 Global Instructions”, item “Programming Assignment Submission” (if not otherwise specified)

Submission:

  • A ZIP file containing all Java files in the package a051 (the package must contain all the code to execute – do not call methods from other packages – except Java predefined packages)
  • A PDF file with the new source code that you wrote included as text (not screenshots).
  • A PDF file with the execution of tasks included as text (not screenshots)
  • A PDF file with the answers to the enclosed questions



A05-PA2 Optimized Quick Sort

Task 1: Code Setup

  • 11. Create a package “hw” (under src folder), if not already created.
  • 12. Create a sub-package “a05” under the package “hw”, if not already created.
  • 13. Create a sub-package “a052” under the package “a05”, if not already created.
  • 14. In the sub-package “a052” copy your last version of the classes from package a051: ArrayUtilitty, Bag, FixedBagCapacity, Stopwatch, TimeAnalysis, QuickSort, QuickSortTest and QuickSortAnalysis
  • 15. In the sub-package “a052” rename the following classes:
    • QuickSort rename to OptimizedQuickSort
    • QuickSortTest rename to OptimizedQuickSortTest
    • QuickSortAnalysis rename to OptimizedQuickSortAnalysis

Task 2: Optimized Quick Sort Method

  • 21. In the class OptimizedQuickSort, create a private class variable named MAX INSERTION SIZE, the will keep the default maximum array (or subarray size for which we apply insertion sort).
  • 22. In the class OptimizedQuickSort, create a private class method named median3 that computes the median of the values of the provided indexes and exchange the median with the first index.
    • Hint: Use nested if’s considering all possible orders between the 3 variables. For each case return the value in the middle.
  • 23. In the class OptimizedQuickSort modify the method named partition to compute the pivot as the median of the following 3 numbers: startIndex, endIndex and the middle between them.
    • Hint: Call the median for the 3 values. To compute the middle index use the formula (left+right)/2
  • 24. In the class OptimizedQuickSort modify the recursive method sort by adding a new parameter, maxInsert, that you indicate under which size to apply the insertion sort. Test the size of the array and apply insertion sort for smaller sub-arrays.
  • 25. In the class OptimizedQuickSort create a public static method sort that will sort an array using quick sort method. It receives the array to be sorted and the maximum size to which applies insertion sort, and calls the recursive quick sort for the entire array with same parameters..
  • 26. In the class OptimizedQuickSort, modify the sort(int[]) method to call the recursive sort with the default constant defined in step 21.
  • 27. Execute the program OptimizedQuickSortTest. Check your resullts. Test and debug until your examples work well. Include a text with the obtained correct results in your submission.

Task 3 Experimental Time Analysis

  • 31. In the class OptimizedQuickSortAnalysis check the method meanTime to call the OptimizedQuickSort.
  • 32. Execute the program OptimizedQuickSortAnalysis. Include a text with the obtained analysis in your PDF submission.
  • 33. Repeat the steps for 5 insertion sizes (e.g. 10, 20, 30, 40, 50).
  • 34. How the execution time changes? Which insertion size is the best in your case?

Task 4: Analyze the execution time and memory needs for the top-down merge sort.

  • 41. Explain in your own words which is the theoretical order of growth for the method. Explain why. (1-2 paragraphs)
  • 42. Draw a graph for the best values obtained in the previous task.
  • 43. Explain if the graph confirms or not the theoretical order of growth above. (1-2 paragraphs)
  • 44. How the graphs compares with the graphs for the previous sorts? Is the result expected (1-2 paragraphs)
  • 45. Analyze the memory needs for this sort method. Are they relevant? Why? (1-2 paragraphs)

Grading: 0.90 points (see grading rubric for details)

Global Submission Instruction:

  • You must follow the instructions described in the folder: “512 All Modules”, subfolder “A00 Global Instructions”, item “Programming Assignment Submission” (if not otherwise specified)

Submission:

  • A ZIP file containing all Java files in the package a051 (the package must contain all the code to execute – do not call methods from other packages – except Java predefined packages)
  • A PDF file with the new source code that you wrote included as text (not screenshots).
  • A PDF file with the execution of tasks included as text (not screenshots)
  • A PDF file with the answers to the enclosed questions



A05-PA3 Best Insertion Size

Task 1: Code Setup

  • 11. Create a package “hw” (under src folder), if not already created.
  • 12. Create a sub-package “a05” under the package “hw”, if not already created.
  • 13. Create a sub-package “a053” under the package “a05”, if not already created.
  • 14. In the sub-package “a053” copy your last version of the classes from package a051: ArrayUtilitty, Bag, FixedBagCapacity, Stopwatch, TimeAnalysis, QuickSort, and OptimizedQuickSortTest

Task 2: Compare Insertion Size for Quick Sort Method

  • 21. In the package “a053”, create a class named CompareInsertionSize, in which we will write the code to compare various insertion sizes for random arrays sorted using the optimized quick sort.
  • 22. In the class CompareInsertionSize, create a private class method named meanTimeComparison, that will run experiments for various insertion size for a given array length. The method will compare the mean time execution of quick sort for various insertion sizes. They all will use the same randomly generated arrays for time measuring. ]The sizes are generated starting with a provided startSize and incrementing with the incrementSize for the given number of times. The method will receive the number of executions to compute the mean (sample size, number of random arrays generated and tested), and the length of the generated random arrays. It will return an array of time analysis elements (with length number of sizes +1).
  • 23. In the class CompareInsertionSize, create a private method named printComparisonTable, that will print comparisons for various lengthes of the sorted array, starting with a minimum size, ending with a maximum size and incrementing with a given value. The method will also receive the information related to the insertion sizes tested and will call the previous method.
  • 24. In the class CompareInsertionSize create the main method, in which call the print comparison table method for a sample size of 21, with array length from 1000000 to 10000000 incrementing by 1000000 and forsizes starting from 0 and incrementing by 25, for 10 times.
  • 25. Execute the program and include the results in the corresponding PDF.

Task 3: Analyze Insertion Size

  • 31. Analyze the results obtained above and identify where the best size might be. How it compares with the textbook recommendation? Why?
    • Hint. Based on my table, the minimum execution time seems to be between 75-125.
  • 32. Design and run an experiment to better identify the insertion size.
    • Hint: I will change the sample size to 31, in order to have more precise values. I will change the considered insertion sizes to go from 50 to 150 in 10 increment. Be ready for some waiting.
  • 33. Refine one more the experiment
    • Hint: Change the values as above to make the results even more accurate toward the best size.
  • 34. Which is the value that you decide to pick as the default value? Explain your reasoning.

Place this order or similar order and get an amazing discount. USE Discount code “GET20” for 20% discount

Posted in Uncategorized