Hacks for DS Sorts
Sort analysis and building hashmaps
public class SortAnalysis {
public static int[] generateArray() {
int[] arr = new int[5000];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 10000);
}
return arr;
}
public static float[] main(String[] args) {
System.out.println("-------------------------------");
// create an array with 5000 elements
int[] arr1 = generateArray();
int[] arr2 = new int[7000];
int[] arr3 = new int[7000];
int[] arr4 = new int[7000];
System.arraycopy(arr1, 0, arr2, 0, 500);
System.arraycopy(arr1, 0, arr3, 0, 500);
System.arraycopy(arr1, 0, arr4, 0, 500);
float[] times = new float[4];
String str = "";
// sort the array
long start = System.currentTimeMillis();
bubbleSort(arr1);
long end = System.currentTimeMillis();
// print the time it took
str += ((end - start) + "ms | ");
times [0] = (end - start);
start = System.currentTimeMillis();
mergeSort(arr2);
end = System.currentTimeMillis();
// print the time it took
str += ((end - start) + "ms | ");
times [1] = (end - start);
start = System.currentTimeMillis();
selectionSort(arr3);
end = System.currentTimeMillis();
// print the time it took
str += ((end - start) + "ms | ");
times [2] = (end - start);
start = System.currentTimeMillis();
insertionSort(arr4);
end = System.currentTimeMillis();
// print the time it took
str += ((end - start) + "ms");
times [3] = (end - start);
System.out.println(str);
return times;
}
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int current = arr[i];
int j = i - 1;
while (j >= 0 && current < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
}
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
public static void mergeSort(int[] arr) {
if (arr.length > 1) {
int[] left = leftHalf(arr);
int[] right = rightHalf(arr);
mergeSort(left);
mergeSort(right);
merge(arr, left, right);
}
}
public static int[] leftHalf(int[] arr) {
int size1 = arr.length / 2;
int[] left = new int[size1];
for (int i = 0; i < size1; i++) {
left[i] = arr[i];
}
return left;
}
public static int[] rightHalf(int[] arr) {
int size1 = arr.length / 2;
int size2 = arr.length - size1;
int[] right = new int[size2];
for (int i = 0; i < size2; i++) {
right[i] = arr[i + size1];
}
return right;
}
public static int[] merge(int[] result, int[] left, int[] right) {
int i1 = 0;
int i2 = 0;
for (int i = 0; i < result.length; i++) {
if (i2 >= right.length || (i1 < left.length && left[i1] <= right[i2])) {
result[i] = left[i1];
i1++;
} else {
result[i] = right[i2];
i2++;
}
}
return result;
}
}
System.out.println("Bubble | Merge | Selection | Insertion");
float[] means = new float[4];
for (int i = 0; i < 12; i++) {
float[] a = SortAnalysis.main(null);
for (int j = 0; j < 4; j++) {
means[j] += a[j];
}
}
for (int i = 0; i < 4; i++) {
means[i] /= 12;
means[i] = Math.round(means[i] * 1000) / 1000;
}
System.out.println("-------------------------------");
System.out.println("Average: " + means[0] + "ms | " + means[1] + "ms | " + means[2] + "ms | " + means[3] + "ms");
import java.util.HashMap;
import java.lang.Integer;
public class HashTester {
public static void main(String[] args) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int[] arr = new int[10000];
for (int i = 0; i < 10000; i++) {
Integer value = (int) (Math.random() * 10000);
map.put(value, value);
arr[i] = value;
}
System.out.println("LookUp | BinarySearch");
for (int i = 0; i < 12; i++) {
int[] arra = new int[10000];
String str = "";
long lut = (lookUp(map, i));
str += (lut + "ms | ");
System.arraycopy(arr, 0, arra, 0, arr.length);
long bst = (binarySearchTime(arra, i));
str += (bst + "ms | ");
System.out.println(str);
}
}
public static long lookUp(HashMap<Integer, Integer> map, Integer value) {
long start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
map.containsKey(i);
}
long end = System.currentTimeMillis();
return (end - start);
}
public static long binarySearchTime(int[] arr, Integer value) {
long start = System.currentTimeMillis();
// binary search
int low = 0;
int high = arr.length - 1;
int mid = (low + high) / 2;
while (low <= high) {
if (arr[mid] < value) {
low = mid + 1;
} else if (arr[mid] == value) {
break;
} else {
high = mid - 1;
}
mid = (low + high) / 2;
}
long end = System.currentTimeMillis();
return (end - start);
}
}
HashTester.main(null);