Sorts + Hashmaps
Java sorting algorithms and hashmaps
public class MergeSort {
public static void main(String[] args) {
// create an example array to be sorted
int[] arr = { 3, 7, 12, 18, 11, 6, 5, 8 };
// print the unsorted array to the console
System.out.println("-- Merge --");
System.out.println("Unsorted array:");
printArray(arr);
// sort the array using the mergeSort method
long startTime = System.nanoTime(); // start timer in nanoseconds by creating a set time
mergeSort(arr);
long endTime = System.nanoTime(); // end timer by creating an end time
long totalTime = endTime - startTime; // subtract start from end to get total time
// print the sorted array to the console
System.out.println();
System.out.println("Sorted array:");
printArray(arr);
System.out.println("");
System.out.println("Runtime: ");
System.out.println(totalTime + " nanoseconds");
System.out.println();
}
// mergeSort method takes an array of integers and sorts them using the merge sort algorithm
public static void mergeSort(int[] arr) {
// base case: if the array is empty or has only one element, it is already sorted
if (arr.length <= 1) {
return;
}
// find the midpoint of the array
int mid = arr.length / 2;
// create new arrays for the left and right halves of the original array
int[] left = new int[mid];
int[] right = new int[arr.length - mid];
// copy the left half of the original array into the left array
for (int i = 0; i < mid; i++) {
left[i] = arr[i];
}
// copy the right half of the original array into the right array
for (int i = mid; i < arr.length; i++) {
right[i - mid] = arr[i];
}
// recursively sort the left and right arrays
mergeSort(left);
mergeSort(right);
// merge the sorted left and right arrays back into the original array
merge(left, right, arr);
}
// merge method takes two sorted arrays and merges them into a new sorted array
public static void merge(int[] left, int[] right, int[] arr) {
// initialize variables for the left, right, and result array indexes
int i = 0;
int j = 0;
int k = 0;
// compare the elements of the left and right arrays, and add the smaller one to the result array
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
k++;
}
// add any remaining elements from the left array to the result array
while (i < left.length) {
arr[k] = left[i];
i++;
k++;
}
// add any remaining elements from the right array to the result array
while (j < right.length) {
arr[k] = right[j];
j++;
k++;
}
}
// printArray method takes an array of integers and prints it to the console
public static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
if (i < arr.length - 1) {
System.out.print(" ");
}
}
}
}
MergeSort.main(null);
public class BubbleSort{
public static void main(String[] args){
int[] list = {3, 11, 15, 5, 9, 2, 7}; // list
int tmp = 0;
int swaps = 0;
System.out.println();
System.out.println("-- Bubble --");
System.out.println("Unsorted:");
for(int i = 0; i < list.length; i++){
System.out.print(list[i] + " ");
}
System.out.println(" ");
long startTime = System.nanoTime(); // start timer in nanoseconds by creating a set time
for (int i = 0; i < list.length; i++){
for (int j = 1; j < (list.length - i); j++){ // O(n^2)
if (list[j - 1] > list[j]){
tmp = list[j-1];
list[j-1] = list[j];
list[j] = tmp;
swaps = swaps+1;
}
}
}
System.out.println("Sorted:");
for(int i = 0; i < list.length; i++){
System.out.print(list[i] + " ");
}
long endTime = System.nanoTime(); // end timer by creating an end time
long totalTime = endTime - startTime; // subtract start from end to get total time
System.out.println("");
System.out.println("Runtime: ");
System.out.println(totalTime + " nanoseconds");
System.out.println("Swaps:" + swaps);
}
}
BubbleSort.main(null);
public class SelectionSort{
public static void main(String[] args){
int[] list = {7, 11, 14, 10, 9, 4, 3};
int tmp = 0;
System.out.println();
System.out.println("-- Selection --");
System.out.println("Unsorted:");
for(int i = 0; i < list.length; i++){
System.out.print(list[i] + " ");
}
System.out.println(" ");
long startTime = System.nanoTime(); // start timer in nanoseconds by creating a set time
// Selection Sorting algorithm
for (int i = 0; i < list.length - 1; i++){
int index = i;
for (int j = i + 1; j < list.length; j++){ // O(n^2)
if (list[j] < list[index]){
index = j;
}
}
tmp = list[index];
list[index] = list[i];
list[i] = tmp;
}
// End of Selection Sorting algorithm
// Printing the sorted array
System.out.println("Sorted:");
for(int i = 0; i < list.length; i++){
System.out.print(list[i] + " ");
}
long endTime = System.nanoTime(); // end timer by creating an end time
long totalTime = endTime - startTime; // subtract start from end to get total time
System.out.println("");
System.out.println("Runtime: ");
System.out.println(totalTime + " nanoseconds");
}
}
SelectionSort.main(null);
public class InsertionSort{
public static void main(String[] args){
int[] list = {6, 12, 14, 0, 9, 2, 3};
int tmp = 0;
System.out.println();
System.out.println("-- Insertion --");
System.out.println("Unsorted:");
for(int i = 0; i < list.length; i++){
System.out.print(list[i] + " ");
}
System.out.println(" ");
long startTime = System.nanoTime(); // start timer in nanoseconds by creating a set time
// Insertion Sorting algorithm
for (int i = 1; i < list.length; i++){
int temp = list[i];
int j = i - 1;
while (j >= 0 && list[j] > temp){
list[j + 1] = list[j];
j = j - 1;
}
list[j + 1] = temp;
}
// End of Insertion Sorting algorithm
// Printing the sorted array
System.out.println("Sorted:");
for(int i = 0; i < list.length; i++){
System.out.print(list[i] + " ");
}
long endTime = System.nanoTime(); // end timer by creating an end time
long totalTime = endTime - startTime; // subtract start from end to get total time
System.out.println("");
System.out.println("Runtime: ");
System.out.println(totalTime + " nanoseconds");
}
}
InsertionSort.main(null);
MergeSort.main(null);
BubbleSort.main(null);
SelectionSort.main(null);
InsertionSort.main(null);
Big O analysis
- Fastest is merge sort
- 2nd fastest is selection sort
- 3rd fastest is insertion sort
- 4th fastest is bubble sort
Conclusion
- The fastest algorithm is merge sort
- Makes sense as it has a O(n*log(n)) time complexity
- Slowest is bubble sort
- Has a O(n^2) time complexity making it inefficient in comparison