<\/p>\n
Due: Thursday 6\/26\/14 @5:30pm via users.cs.umb.edu:cs210\/hw4<\/p>\n
Purpose:<\/strong>\u00a0To analyze an algorithm for computational cost with respect\u00a0to input size. To determine the best and worst case performance of an algorithm.<\/p>\n 1. Implement QuickSort and Insertion Sort in files QuickSort.java and InsertionSort.java with (at least) the following method:<\/p>\n 2. Write a class Eval that runs this method on three different types of inputs. Random input, Sorted input and Reversed input. Time how long each input takes on your Quicksort.sort, Arrays.sort, Insertion.sort (From slides) and output their runtime. Create your input arrays so that your code should run between 1 to 5 seconds total (To make it easy to grade).<\/p>\n 3. Write a memo.txt describing what you observe about the algorithms.<\/p>\n You can use this timing code:<\/p>\n To generate some random input you can use Math.random() like this:<\/p>\n Your code should output like this:<\/p>\n Grading (total 10 points):<\/strong><\/p>\n Turn in the following files: Quicksort.java, Insertion.java, Eval.java, and memo.txt<\/p>\n 2 points: QuickSort working<\/p>\n 2 points: Insertion Sort working<\/p>\n 3 points: Runtimes calculated correctly<\/p>\n 3 points: memo.txt, easy to grade, and runs between 1 and 5 seconds.<\/p>\n","protected":false},"excerpt":{"rendered":" Due: Thursday 6\/26\/14 @5:30pm via users.cs.umb.edu:cs210\/hw4 Purpose:\u00a0To analyze an algorithm for computational cost with respect\u00a0to input size. To determine the best and worst case performance of an algorithm. 1. Implement QuickSort and Insertion Sort in files QuickSort.java and InsertionSort.java with (at least) the following method: public void sort(Comparable[] arr); 2. Write a class Eval… Read more »<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"_links":{"self":[{"href":"https:\/\/josephpcohen.com\/teaching\/cs210\/wp-json\/wp\/v2\/posts\/363"}],"collection":[{"href":"https:\/\/josephpcohen.com\/teaching\/cs210\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/josephpcohen.com\/teaching\/cs210\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/josephpcohen.com\/teaching\/cs210\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/josephpcohen.com\/teaching\/cs210\/wp-json\/wp\/v2\/comments?post=363"}],"version-history":[{"count":0,"href":"https:\/\/josephpcohen.com\/teaching\/cs210\/wp-json\/wp\/v2\/posts\/363\/revisions"}],"wp:attachment":[{"href":"https:\/\/josephpcohen.com\/teaching\/cs210\/wp-json\/wp\/v2\/media?parent=363"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/josephpcohen.com\/teaching\/cs210\/wp-json\/wp\/v2\/categories?post=363"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/josephpcohen.com\/teaching\/cs210\/wp-json\/wp\/v2\/tags?post=363"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\npublic void sort(Comparable[] arr);\n<\/pre>\n
\nlong startTime = System.currentTimeMillis();\n\/\/ do something\nlong endTime = System.currentTimeMillis();\nlong duration = endTime - startTime;\nSystem.out.println(\"Time taken: \" + duration + \"ms\");\n<\/pre>\n
\nint N = 20;\nInteger[] arr = new Integer[N];\nfor (int i = 0; i < arr.length; i++) {\n\tarr[i] = (int)(Math.random()*999);\n}\nSystem.out.println(Arrays.toString(arr));\n<\/pre>\n\n$ java -cp . Eval\nCreating random input..\n Arrays.sort : __ ms\n Quicksort.sort : __ ms\n Insertion.sort : __ ms\nCreating ascending sorted input..\n Arrays.sort : __ ms\n Quicksort.sort : __ ms\n Insertion.sort : __ ms\nCreating descending sorted input..\n Arrays.sort : __ ms\n Quicksort.sort : __ ms\n Insertion.sort : __ ms\n<\/pre>\n