Created
January 4, 2023 07:26
-
-
Save seanboe/cf7fd2d94e8bd0e6c6b390a59e57beda to your computer and use it in GitHub Desktop.
Sorting Algorithms homework
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class runner { | |
public static void main(String[] args) { | |
// Create an array of length 50 | |
int[] arr = new int[9000]; | |
// Fill arr with random numbers in the range 0-99: | |
for (int x = 0; x < arr.length; x++) { | |
arr[x] = (int)(Math.random() * 100); | |
} | |
printArray(arr); | |
long start = System.currentTimeMillis(); | |
printArray(insertionSort(arr)); | |
long insertionTime = System.currentTimeMillis() - start; | |
printArray(selectionSort(arr)); | |
long selectionTime = System.currentTimeMillis() - insertionTime - start; | |
printArray(mergeSort(arr)); | |
long mergeTime = System.currentTimeMillis() - selectionTime - insertionTime - start; | |
System.out.println("Times:"); | |
System.out.println("Insertion: " + insertionTime + " Selection: " + selectionTime + " Merge: " + mergeTime); | |
} | |
public static int[] mergeSort(int input[]) { | |
mergeSortRecursiveInit(input, 0, input.length - 1); | |
return input; | |
} | |
public static void mergeSortRecursiveInit(int arr[], int l, int r) { | |
if (l < r) { | |
// Find the middle point | |
int m = l + (r - l) / 2; | |
// Sort first and second halves | |
mergeSortRecursiveInit(arr, l, m); | |
mergeSortRecursiveInit(arr, m + 1, r); | |
// Merge the sorted halves | |
mergeSortRecursive(arr, l, m, r); | |
} | |
} | |
public static void mergeSortRecursive(int arr[], int l, int m, int r) { | |
// Find sizes of two subarrays to be merged | |
int n1 = m - l + 1; | |
int n2 = r - m; | |
/* Create temp arrays */ | |
int L[] = new int[n1]; | |
int R[] = new int[n2]; | |
/*Copy data to temp arrays*/ | |
for (int i = 0; i < n1; ++i) | |
L[i] = arr[l + i]; | |
for (int j = 0; j < n2; ++j) | |
R[j] = arr[m + 1 + j]; | |
/* Merge the temp arrays */ | |
// Initial indexes of first and second subarrays | |
int i = 0, j = 0; | |
// Initial index of merged subarray array | |
int k = l; | |
while (i < n1 && j < n2) { | |
if (L[i] <= R[j]) { | |
arr[k] = L[i]; | |
i++; | |
} | |
else { | |
arr[k] = R[j]; | |
j++; | |
} | |
k++; | |
} | |
/* Copy remaining elements of L[] if any */ | |
while (i < n1) { | |
arr[k] = L[i]; | |
i++; | |
k++; | |
} | |
/* Copy remaining elements of R[] if any */ | |
while (j < n2) { | |
arr[k] = R[j]; | |
j++; | |
k++; | |
} | |
} | |
public static int[] insertionSort(int input[]) { | |
int n = input.length; | |
for (int i = 1; i < n; ++i) { | |
int key = input[i]; | |
int j = i - 1; | |
/* Move elements of arr[0..i-1], that are | |
greater than key, to one position ahead | |
of their current position */ | |
while (j >= 0 && input[j] > key) { | |
input[j + 1] = input[j]; | |
j = j - 1; | |
} | |
input[j + 1] = key; | |
} | |
return input; | |
} | |
public static int[] selectionSort(int input[]) { | |
int n = input.length; | |
// One by one move boundary of unsorted subarray | |
for (int i = 0; i < n-1; i++) | |
{ | |
// Find the minimum element in unsorted array | |
int min_idx = i; | |
for (int j = i+1; j < n; j++) | |
if (input[j] < input[min_idx]) | |
min_idx = j; | |
// Swap the found minimum element with the first | |
// element | |
int temp = input[min_idx]; | |
input[min_idx] = input[i]; | |
input[i] = temp; | |
} | |
return input; | |
} | |
public static void printArray(int arr[]) { | |
String output = "["; | |
for (int x : arr) { | |
output += x + ","; | |
} | |
output = output.substring(0, output.length() - 1); | |
output += "]"; | |
System.out.println(output); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment