//input an array length import java.util.*; public class Compareing { private static int[] arr; private static BubbleSort bubble = new BubbleSort(); private static InsertionSort insertion = new InsertionSort(); private static SelectionSort select = new SelectionSort(); private static QuickSort quick = new QuickSort(); private static RadixSort radix = new RadixSort(); public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.println("input an Array size:"); int size = input.nextInt(); arr = new int[size]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) (Math.random() * size); } //printArr(arr); insertion.setArr(arr); printInsertion(); select.setArr(arr); printSelect(); bubble.setArr(arr); printBubble(); quick.setArr(arr); printQuick(); radix.setArr(arr); printRadix(); } public static void printBubble() { int[] Arr; long startTime; long stopTime; System.out.println("\nbubbleSort"); startTime = System.currentTimeMillis(); bubble.sort(); stopTime = System.currentTimeMillis(); Arr = bubble.getArr(); // printArr(Arr); // System.out.println(isSorted(Arr)); System.out.println("milisec: " + (stopTime - startTime)); System.out.println("swaps: " + bubble.getSwaps()); System.out.println("arr accessed: " + bubble.getArrAccessed()); System.out.println("comparisons: " + bubble.getComparisons()); } public static void printInsertion() { int[] Arr; long startTime; long stopTime; System.out.println("\ninsertionSort"); startTime = System.currentTimeMillis(); insertion.sort(); stopTime = System.currentTimeMillis(); Arr = insertion.getArr(); // printArr(Arr); // System.out.println(isSorted(Arr)); System.out.println("milisec: " + (stopTime - startTime)); System.out.println("swaps: " + insertion.getSwaps()); System.out.println("arr accessed: " + insertion.getArrAccessed()); System.out.println("comparisons: " + insertion.getComparisons()); } public static void printSelect() { int[] Arr; long startTime; long stopTime; System.out.println("\nselectionSort"); startTime = System.currentTimeMillis(); select.sort(); stopTime = System.currentTimeMillis(); Arr = select.getArr(); // printArr(Arr); // System.out.println(isSorted(Arr)); System.out.println("milisec: " + (stopTime - startTime)); System.out.println("swaps: " + select.getSwaps()); System.out.println("arr accessed: " + select.getArrAccessed()); System.out.println("comparisons: " + select.getComparisons()); } public static void printQuick() { int[] Arr; long startTime; long stopTime; System.out.println("\nquickSort"); startTime = System.currentTimeMillis(); quick.sort(); stopTime = System.currentTimeMillis(); Arr = quick.getArr(); //printArr(Arr); //System.out.println(isSorted(Arr)); System.out.println("milisec: " + (stopTime - startTime)); System.out.println("swaps: " + quick.getSwaps()); System.out.println("arr accessed: " + quick.getArrAccessed()); System.out.println("comparisons: " + quick.getComparisons()); } public static void printRadix() { int[] Arr; long startTime; long stopTime; System.out.println("\nradixSort"); startTime = System.currentTimeMillis(); radix.sort(); stopTime = System.currentTimeMillis(); Arr = radix.getArr(); //printArr(Arr); //System.out.println(isSorted(Arr)); System.out.println("milisec: " + (stopTime - startTime)); System.out.println("swaps: " + radix.getSwaps()); System.out.println("arr accessed: " + radix.getArrAccessed()); System.out.println("comparisons: " + radix.getComparisons()); System.out.println("radixSort doesn't compare any of the elements with eachother and doesn't swap them, but sorts them in other arrays/lists and puts them back afterwards."); } public static boolean isSorted(int[] Arr) { for (int i = 0; i < Arr.length - 1; i++) { if (Arr[i] > Arr[i + 1]) { return false; } } return true; } public static void printArr(int[] Arr) { String result = ""; for (int i = 0; i < Arr.length; i++) { result += "" + Arr[i] + ", "; } System.out.println(result); } } public class BubbleSort { private int[] arr; private int comparisons = 0; private int arrAccessed = 0; private int swaps = 0; public void setArr(int[] Arr) { arr = Arrays.copyOf(Arr, Arr.length); } public void sort() { int length = arr.length; for (int j = 0; j < arr.length; j++) { for (int i = 0; i < length - 1; i++) { if (arr[i] > arr[i + 1]) { swap(i, i + 1); } comparisons++; arrAccessed += 2; } length--; } } public void swap(int index1, int index2) { int holder = arr[index1]; arr[index1] = arr[index2]; arr[index2] = holder; arrAccessed += 4; swaps++; } public int getComparisons() { return comparisons; } public int getArrAccessed() { return arrAccessed; } public int getSwaps() { return swaps; } public int[] getArr() { return arr; } } public class InsertionSort { private int[] arr; private int comparisons = 0; private int arrAccessed = 0; private int swaps = 0; public void setArr(int[] Arr) { arr = Arrays.copyOf(Arr, Arr.length); } public void sort() { int sorted = 1; while (sorted < arr.length) { int at = sorted; while (needToSwap(at - 1, at)) { swap(at - 1, at); arrAccessed += 4; swaps++; at--; } sorted++; } } public boolean needToSwap(int index1, int index2) { if (index1 >= 0 && index2 >= 0) { comparisons++; arrAccessed += 2; return (arr[index1] > arr[index2]); } else { return false; } } public void swap(int index1, int index2) { int holder = arr[index1]; arr[index1] = arr[index2]; arr[index2] = holder; } public int getComparisons() { return comparisons; } public int getArrAccessed() { return arrAccessed; } public int getSwaps() { return swaps; } public int[] getArr() { return arr; } } public class QuickSort { private int[] arr; private int comparisons = 0; private int arrAccessed = 0; private int swaps = 0; public void setArr(int[] Arr) { arr = Arrays.copyOf(Arr, Arr.length); } public void sort() { sortQuick(0, arr.length); } public void sortQuick(int index1, int index2){ if(index2 - index1 > 1){ int pivotIndex = index1; for(int i=index1+1;i= arr[i]){ int holder = arr[i]; arrAccessed++; for(int j=i;j>pivotIndex;j--){ arr[j] = arr[j-1]; arrAccessed += 2; swaps++; } arr[pivotIndex] = holder; arrAccessed++; pivotIndex++; } } sortQuick(index1, pivotIndex); sortQuick(pivotIndex+1, index2); } } public void swap(int index1, int index2) { int holder = arr[index1]; arr[index1] = arr[index2]; arr[index2] = holder; arrAccessed += 4; swaps++; } //not used since there is an easier way public int getComparisons() { return comparisons; } public int getArrAccessed() { return arrAccessed; } public int getSwaps() { return swaps; } public int[] getArr() { return arr; } } public class RadixSort { private int[] arr; private int comparisons = 0; private int arrAccessed = 0; private int swaps = 0; private ArrayList[] buckets = new ArrayList[10]; public RadixSort(){ for(int i=0; i<10; i++){ buckets[i] = new ArrayList(); } } public void setArr(int[] Arr) { arr = Arrays.copyOf(Arr, Arr.length); } public void sort() { int atDigit = 0; int longest = longestValue(); while(atDigit < longest){ for(int i=0;i arr[i]) { index = i; } comparisons++; arrAccessed += 2; } return index; } public void swap(int index1, int index2) { int holder = arr[index1]; arr[index1] = arr[index2]; arr[index2] = holder; arrAccessed += 4; swaps++; } public int getComparisons() { return comparisons; } public int getArrAccessed() { return arrAccessed; } public int getSwaps() { return swaps; } public int[] getArr() { return arr; } }

sorting Compared