Driver.java (5005B)
1 package lab9; 2 3 /* 4 * Purpose: Data Structure and Algorithms Lab 9 Problem 1 5 * Status: Complete and thoroughly tested 6 * Last update: 01/31/18 7 * Submitted: 02/01/18 8 * Comment: test suite and sample run attached 9 * @author: John Kubach 10 * @version: 2018.01.31 11 */ 12 13 import java.util.Scanner; 14 15 public class Driver { 16 Scanner in = new Scanner(System.in); 17 public static void main(String[] args) { 18 int[] items; 19 Driver ui = new Driver(); 20 21 items = ui.getArray(); 22 23 /* Uncomment to select sorting algorithm */ 24 25 //ui.bubbleSort(items); 26 //ui.improvedBubbleSort(items); 27 //ui.selectionSort(items); 28 ui.improvedSelectionSort(items); 29 //ui.insertionSort(items); 30 } 31 32 public void bubbleSort(int items[]) { 33 System.out.println("BUBBLE SORT"); 34 int temp; 35 int compare = 0; 36 int swap = 0; 37 for (int i = 0; i < items.length - 1; i++) { 38 for (int j = 0; j < items.length - 1 - i; j++) { 39 compare++; 40 if (items[j] > items[j+1]) { 41 temp = items[j]; 42 items[j] = items[j+1]; 43 items[j+1] = temp; 44 swap++; 45 } 46 } 47 } 48 printOperations(compare, swap); 49 printArray(items); 50 } 51 52 public void improvedBubbleSort(int items[]) { 53 System.out.println("\n IMPROVED BUBBLE SORT \n"); 54 boolean sorted = true; 55 int temp; 56 int compare = 0; 57 int swap = 0; 58 for (int i = 0; i < items.length - 1 && sorted; i++) { 59 60 sorted = false; 61 for (int j = 0; j < items.length - 1 - i; j++) { 62 compare++; 63 if (items[j] > items[j+1]) { 64 temp = items[j]; 65 items[j] = items[j+1]; 66 items[j+1] = temp; 67 swap++; 68 sorted = true; 69 } 70 } 71 } 72 printOperations(compare, swap); 73 printArray(items); 74 } 75 76 public void selectionSort(int[] items){ 77 System.out.println("\n SELECTION SORT \n"); 78 int temp; 79 int min; 80 int swap = 0; 81 int compare = 0; 82 83 for (int i = 0; i < items.length - 1; i++) { 84 min = i; 85 printArray(items); 86 for ( int j = (i+1); j < items.length; j++) { 87 compare++; 88 if (items[j] < items[min]) { 89 min = j; 90 } 91 printArray(items); 92 } 93 if (i != min){ 94 temp = items[i]; 95 items[i]=items[min]; 96 items[min] = temp; 97 swap++; 98 } 99 } 100 printOperations(compare, swap); 101 printArray(items); 102 } 103 104 public void improvedSelectionSort(int[] items) { 105 System.out.println("\n IMPROVED SELECTION SORT \n"); 106 int temp; 107 int min; 108 int swap = 0; 109 int compare = 0; 110 boolean setMin = true; 111 for (int i = 0; i < items.length - 1 && setMin; i++) { 112 min = i; 113 setMin = false; 114 for ( int j = (i+1); j < items.length; j++) { 115 compare++; 116 if (items[j] < items[min]) { 117 min = j; 118 } 119 } 120 if (i != min) { 121 temp = items[i]; 122 items[i]=items[min]; 123 items[min] = temp; 124 swap++; 125 setMin = true; 126 } 127 } 128 printOperations(compare, swap); 129 printArray(items); 130 } 131 132 133 public void insertionSort(int items[]) { 134 System.out.println("\n INSERTION SORT \n"); 135 int swap = 0; 136 int compare = 0; 137 for (int i = 1; i < items.length; i++) { 138 int j; 139 int current = items[i]; 140 compare++; 141 142 for (j = i - 1; j >= 0 && items[j] > current; j--) { 143 items[j+1] = items[j]; 144 swap++; 145 } 146 items[j+1] = current; 147 } 148 printOperations(compare, swap); 149 printArray(items); 150 } 151 152 public int[] getArray() { 153 int size; 154 int element; 155 System.out.print("Enter number of integers: "); 156 size = Integer.parseInt(in.nextLine()); 157 int newArray[] = new int[size]; 158 for (int i = 0; i < newArray.length; i++) { 159 System.out.print("Enter integer " + (i+1) + ": "); 160 element = Integer.parseInt(in.nextLine()); 161 newArray[i] = element; 162 } 163 return newArray; 164 } 165 166 public void printOperations(int compare, int swap) { 167 System.out.println("Number of comparisons: " + compare); 168 System.out.println("Number of swaps: " + swap); 169 } 170 171 public void printArray(int items[]) { 172 for (int i = 0; i < items.length; i++) { 173 System.out.print(items[i] + " "); 174 } 175 System.out.println(); 176 } 177 }