Courses‎ > ‎APCS - Term 1‎ > ‎Konstantinovich‎ > ‎

### 2019-03-19

posted Mar 19, 2019, 6:04 AM by Konstantinovich Samuel   [ updated Mar 19, 2019, 10:40 AM ]
 Goal: Quicksort + MergeSort improvementSubgoal:Write a version of insertion sort that works on a sub-array, similar to merge and quicksort.e.g.`void ``insertionsort``(int[] data, int lo,int hi)  `The insertion sort is n^2, but has a low constant.Improve both your quicksort and your mergesort by using the insertion sort when you sub-array is sufficiently small.You can determine the best size to switch to insertion sort by experimentation.So when your mergesort or quicksort is called on an array of size <= k , you use your insertion sort. (This is a replacement to the base case)I will run your merge + quick again after you improve them.Improvements are ONLY improvements if all test cases passed. Here is a way to test a variety of array types:`Run these tests on your sorts (both merge and quick)``You can be clever and add a new argument for which sort to test.`` import java.util.Arrays;`` ```` //Sort testing code private static final int INCREASE = 0; private static final int DECREASE = 1; private static final int STANDARD = 2; private static final int SMALL_RANGE = 3; private static String name(int i){ if(i==INCREASE)return "Increassing"; if(i==DECREASE)return "Decreassing"; if(i==STANDARD)return "Normal Random"; if(i==SMALL_RANGE)return "Random with Few Values"; return "Error categorizing array"; } `````` private static int create(int min, int max){ return min + (int)(Math.random()*(max-min)); } `````` private static int[]makeArray(int size,int type){ int[]ans =new int[size]; if(type == STANDARD){ for(int i = 0; i < size; i++){ ans[i]= create(-1000000,1000000); } } else if(type == INCREASE){ int current = -5 * size; for(int i = 0; i < size; i++){ ans[i]= create(current,current + 10); current += 10; } } else if(type == DECREASE){ int current = 5 * size; for(int i = 0; i < size; i++){ ans[i]= create(current,current + 10); current -= 10; } } else if(type == SMALL_RANGE){ for(int i = 0; i < size; i++){ ans[i]= create(-5,5); } } else{ ans = new int;//empty is default } return ans; } `````` public static void main(String[]args){ if(args.length < 2)return; int size = Integer.parseInt(args); int type = Integer.parseInt(args); int [] start = makeArray(size,type); int [] result = Arrays.copyOf(start,start.length); Arrays.sort(result); long startTime = System.currentTimeMillis(); /* * Test your sort here //yoursort(start); * Add code to switch which sort is tested by changing one of the args!     */ long elapsedTime = System.currentTimeMillis() - startTime; if(Arrays.equals(start,result)){ System.out.println("PASS Case "+name(type)+"\t array, size:"+start.length+"\t"+elapsedTime/1000.0+"sec "); }else{ System.out.println("FAIL ! ERROR ! "+name(type)+" array, size:"+size+" ERROR!"); } }```