Data Sorting
public class BubbleSort {
public static Object[] bubbleSort(int[] arr) {
int n = arr.length;
int compare = 0;
int swap = 0;
// iterate through each element in the array
for (int i = 0; i < n-1; i++) {
// compare adjacent elements in the array
for (int j = 0; j < n-i-1; j++) {
// if the element on the left is greater than the element on the right
compare ++;
if (arr[j] > arr[j+1]) {
// swap the two elements
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
swap ++;
}
}
}
Object[] result = { arr, swap, compare };
return result;
// System.out.println("Number of compares: " + compare);
// System.out.println("Number of swaps: " + swap);
}
public static void main(String[] args) {
// create an array of integers
int[] arr = new int[50]; // initialize array with size 20
int[] arr2 = new int[50];
for (int j = 0; j < 50; j++) {
arr[j] = (int) (Math.random() * 1000); // generate a random integer between 0 and 999
}
Object[] result = bubbleSort(arr);
long startTime = System.nanoTime();
bubbleSort(arr);
long endTime = System.nanoTime();
long duration = (endTime - startTime);
long totalTime = 0;
for (int i = 0; i < 5000; i++) {
long startTime2 = System.nanoTime();
for (int j = 0; j < 50; j++) {
arr2[j] = (int) (Math.random() * 1000); // generate a random integer between 0 and 999
}
bubbleSort(arr2);
long endTime2 = System.nanoTime();
totalTime += (endTime2 - startTime2);
}
long avgTime = totalTime / 5000;
// print out the sorted array
System.out.println("Sorted array:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr2[i] + " ");
}
System.out.println("");
System.out.println("Number of swaps: " + result[1]);
System.out.println("Number of compares: " + result[2]);
System.out.println("Time taken for one run: " + duration + " nanoseconds");
System.out.println("Average time taken for 5000 runs: " + avgTime + " nanoseconds");
}
}
BubbleSort.main(null);
public class SelectionSort {
public static Object[] selectionSort(int[] arr) {
int n = arr.length;
int compare = 0;
int swap = 0;
// iterate through each element in the array
for (int i = 0; i < n-1; i++) {
// find the minimum element in the unsorted part of the array
int minIndex = i;
for (int j = i+1; j < n; j++) {
compare ++;
if (arr[j] < arr[minIndex]) {
minIndex = j;
swap ++;
}
}
// swap the minimum element with the first element in the unsorted part of the array
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
Object[] result = { arr, swap, compare };
return result;
}
public static void main(String[] args) {
// create an array of integers
int[] arr = new int[50]; // initialize array with size 20
int[] arr2 = new int[50];
for (int j = 0; j < 50; j++) {
arr[j] = (int) (Math.random() * 1000); // generate a random integer between 0 and 999
}
Object[] result = selectionSort(arr);
long startTime = System.nanoTime();
selectionSort(arr);
long endTime = System.nanoTime();
long duration = (endTime - startTime);
long totalTime = 0;
for (int i = 0; i < 5000; i++) {
long startTime2 = System.nanoTime();
for (int j = 0; j < 50; j++) {
arr2[j] = (int) (Math.random() * 1000); // generate a random integer between 0 and 999
}
selectionSort(arr2);
long endTime2 = System.nanoTime();
totalTime += (endTime2 - startTime2);
}
long avgTime = totalTime / 5000;
// print out the sorted array
System.out.println("Sorted array:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr2[i] + " ");
}
System.out.println("");
System.out.println("Number of swaps: " + result[1]);
System.out.println("Number of compares: " + result[2]);
System.out.println("Time taken for one run: " + duration + " nanoseconds");
System.out.println("Average time taken for 5000 runs: " + avgTime + " nanoseconds");
}
}
SelectionSort.main(null);
public class InsertionSort {
public static Object[] insertionSort(int[] arr) {
int n = arr.length;
int compare = 0;
int swap = 0;
// iterate through each element in the array
for (int i = 1; i < n; i++) {
// insert the i-th element into the correct position in the sorted part of the array
int key = arr[i];
int j = i - 1;
compare ++;
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j--;
swap ++;
}
arr[j+1] = key;
}
Object[] result = { arr, swap, compare };
return result;
}
public static void main(String[] args) {
// create an array of integers
int[] arr = new int[50]; // initialize array with size 20
int[] arr2 = new int[50];
// sort the array using the insertionSort function
for (int j = 0; j < 50; j++) {
arr[j] = (int) (Math.random() * 1000); // generate a random integer between 0 and 999
}
Object[] result = insertionSort(arr);
long startTime = System.nanoTime();
insertionSort(arr);
long endTime = System.nanoTime();
long duration = (endTime - startTime);
long totalTime = 0;
for (int i = 0; i < 5000; i++) {
long startTime2 = System.nanoTime();
for (int j = 0; j < 50; j++) {
arr2[j] = (int) (Math.random() * 1000); // generate a random integer between 0 and 999
}
insertionSort(arr2);
long endTime2 = System.nanoTime();
totalTime += (endTime2 - startTime2);
}
long avgTime = totalTime / 5000;
// print out the sorted array
System.out.println("Sorted array:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr2[i] + " ");
}
System.out.println("");
System.out.println("Number of swaps: " + result[1]);
System.out.println("Number of compares: " + result[2]);
System.out.println("Time taken for one run: " + duration + " nanoseconds");
System.out.println("Average time taken for 5000 runs: " + avgTime + " nanoseconds");
}
}
InsertionSort.main(null);
Insertion Sort
- starts with second element
- compares element with left and if smaller then swaps and if not stays
- then takes next element and if smaller than first element, but bigger than the next, it will insert itself between the two elements
- once again has a O(n^2) complexity but it is still faster than the bubble and selection sorts because there isn't as many swaps and comparisons
public class MergeSort {
private static int compare = 0;
private static int swap = 0;
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
// find the middle point
int middle = (left + right) / 2;
// recursively sort the left and right subarrays
mergeSort(arr, left, middle);
mergeSort(arr, middle + 1, right);
// merge the sorted subarrays
merge(arr, left, middle, right);
}
}
public static void merge(int[] arr, int left, int middle, int right) {
// find the sizes of the two subarrays
int n1 = middle - left + 1;
int n2 = right - middle;
// create temporary arrays for the left and right subarrays
int[] leftArray = new int[n1];
int[] rightArray = new int[n2];
// copy the elements of the left and right subarrays into the temporary arrays
for (int i = 0; i < n1; ++i) {
leftArray[i] = arr[left + i];
}
for (int j = 0; j < n2; ++j) {
rightArray[j] = arr[middle + 1 + j];
}
// merge the two temporary arrays back into the original array
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
compare ++;
if (leftArray[i] <= rightArray[j]) {
arr[k] = leftArray[i];
i++;
} else {
arr[k] = rightArray[j];
j++;
}
k++;
swap ++;
}
// copy any remaining elements from the left and right subarrays into the original array
while (i < n1) {
arr[k] = leftArray[i];
i++;
k++;
swap ++;
}
while (j < n2) {
arr[k] = rightArray[j];
j++;
k++;
swap ++;
}
}
public static void main(String[] args) {
// create an array of integers
int[] arr = new int[50]; // initialize array with size 20
int[] arr2 = new int[50];
int n = arr.length;
for (int j = 0; j < 50; j++) {
arr[j] = (int) (Math.random() * 1000); // generate a random integer between 0 and 999
}
// sort the array using the mergeSort function
mergeSort(arr, 0, n - 1);
long startTime = System.nanoTime();
mergeSort(arr, 0, n - 1);
long endTime = System.nanoTime();
long duration = (endTime - startTime);
// print out the sorted array
System.out.println("Sorted array:");
for (int i = 0; i < n; ++i) {
System.out.print(arr[i] + " ");
}
System.out.println("");
System.out.println("Time taken for one run: " + duration + " nanoseconds");
// measure the time it takes to sort the array using the mergeSort function 5000 times
long totalDuration = 0;
for (int i = 0; i < 5000; i++) {
long startTime2 = System.nanoTime();
for (int j = 0; j < 50; j++) {
arr2[j] = (int) (Math.random() * 1000); // generate a random integer between 0 and 999
}
mergeSort(arr2, 0, n - 1);
long endTime2 = System.nanoTime();
totalDuration += (endTime2 - startTime2);
}
// calculate the average time it takes to sort the array and print it out
long avgDuration = totalDuration / 5000;
System.out.println("Number of swaps: " + swap);
System.out.println("Number of compares: " + compare);
System.out.println("Average time taken for 5000 runs: " + avgDuration + " nanoseconds");
}
}
MergeSort.main(null);
import java.util.HashMap;
import java.util.Random;
public class Search {
public static void main(String[] args) {
HashMap<Integer, Integer> hashmap = new HashMap<Integer, Integer>();
int[] list = new int[5000];
Random rand = new Random();
// Add random integer values between 0 and 5000 to the 'hashmap' and 'list'.
for (int i = 0; i < list.length; i++) {
Integer value = rand.nextInt(5000);
hashmap.put(value, value);
list[i] = value;
}
long hashTotalTime = 0;
long binaryTotalTime = 0;
// Search for a new random value 5000 times using hashmap and binary search.
for (int i = 0; i < 5000; i++) {
int searchValue = rand.nextInt(5000);
// Measure the time it takes to look up the search value in the 'hashmap' using the 'lookUp' method.
long hashTime = lookUp(hashmap, searchValue);
hashTotalTime += hashTime;
// Measure the time it takes to search for the search value in the 'list' using the binary search algorithm
// implemented in the 'binarySearchTime' method.
long binaryTime = binarySearchTime(list, searchValue);
binaryTotalTime += binaryTime;
}
// Calculate the average time taken for each search operation using hashmap and binary search.
double hashAvgTime = (double) hashTotalTime / 5000;
double binaryAvgTime = (double) binaryTotalTime / 5000;
System.out.println("Hashmap search average time: " + hashAvgTime + " nanoseconds");
System.out.println("Binary search average time: " + binaryAvgTime + " nanoseconds");
}
// This method takes a HashMap<Integer, Integer> object and an Integer value as parameters,
// and measures the time it takes to check if the HashMap contains the given value.
public static long lookUp(HashMap<Integer, Integer> hashmap, Integer value) {
long start = System.nanoTime();
hashmap.containsKey(value); // Check if the HashMap contains the given value.
long end = System.nanoTime();
return (end - start);
}
public static long binarySearchTime(int[] list, Integer value) {
long start = System.nanoTime();
int low = 0;
int high = list.length - 1;
int middle = (low + high) / 2;
while (low <= high) {
if (list[middle] < value) { // If the middle element is less than the target value:
low = middle + 1; // Discard the lower half of the array.
} else if (list[middle] == value) { // If the middle element is equal to the target value:
break; // The target value has been found.
} else { // If the middle element is greater than the target value:
high = middle - 1; // Discard the upper half of the array.
}
middle = (low + high) / 2; // Update the middle index to the midpoint of the remaining search space.
}
long end = System.nanoTime();
return (end - start);
}
}
Search.main(null);
| Pros | Cons | |
|---|---|---|
| Hash maps | O(1) lookup time for key-value pairs (on average) | Can result in collisions, leading to slower lookup times |
| Can handle a large amount of data efficiently | Hash maps are not sorted, so sorting or iterating over keys can be slower than in other data structures | |
| Can be used for both read and write operations | Hash maps can take up more memory than other data structures due to the need for the hash table | |
| Binary searches | O(log n) lookup time, which is faster than linear search | Binary searches require that the data be sorted, which can take time to do if the data changes frequently |
| Can be used on sorted arrays or lists | Binary searches are not efficient for insertions and deletions, since the entire array may need to be shifted | |
| Can be used to find the nearest value to a given value | Binary searches do not work well with non-unique values, since they only return the index of the first occurrence | |
| Can be used to find ranges of values that meet a certain condition |