Sorts and Algo Rhythmic Part 1
Explaining Code + Problems I had
- Learning About the different Sorts -- Bubble
- Hack 1 -- Bubble Sort
- Learning About the Different Sorts -- Selection
- Hack 2 -- Selection Sort
- Learning About the Different Sorts -- Insertion
- Hack 3 -- Insertion Sort
- Learning About the Different Sorts -- Merge
- Hack 4 -- Merge Sort
- Actual Hack 1: Testing Out The Sorts
- Big O Notation Notes
- Extra Sort Notes
- Hashmap Practice
Learning About the different Sorts -- Bubble
- Bubble Sort: allows you to sort items in an array in ascending order. Each value checks with the one to its right and sees if it's less than, greater than, or equal. If the value is less than or equal to the one to its right, no change will occur. However, if it's greater than the value to its right, a swap occurs.
Hack 1 -- Bubble Sort
public class BubbleSort {
//method to sort an array using Bubble sort
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
//loop through unsorted portion of array
for (int j = 0; j < n - i - 1; j++) {
//If current element is greater than next element, swap
if (arr[j] > arr[j + 1]) {
// swap
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// Main method to test BubbleSort class
public static void main(String[] args) {
int[] arr = {5, 2, 9, 1, 5, 6};
System.out.println("Array before sorting:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
bubbleSort(arr);
System.out.println("\nArray after sorting:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
BubbleSort.main(null);
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
// Find the minimum element in unsorted part of array
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum element with the first element
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
// Printing out the sorted and unsorted arrays
public static void main(String[] args) {
int[] arr = {5, 2, 9, 1, 5, 6};
System.out.println("Array before sorting:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
selectionSort(arr);
System.out.println("\nArray after sorting:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
SelectionSort.main(null);
Learning About the Different Sorts -- Insertion
- Insertion Sort: Compares the value with the value to its right. If it's greater, the two swap positions. However, if the number on right is less than the one on the left and all the ones behind it, the value gets moved to the back.
Hack 3 -- Insertion Sort
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[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 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
//Testing InsertionSort
public static void main(String[] args) {
int[] arr = {5, 2, 9, 1, 5, 6};
System.out.println("Array before sorting:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
insertionSort(arr);
System.out.println("\nArray after sorting:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
InsertionSort.main(null);
public class Merge{
public static void mergeSort(int[] arr) {
// base case: array has 1 or 0 elements
if (arr.length <= 1) {
return;
}
// divide the array into two halves
int mid = arr.length / 2;
int[] left = Arrays.copyOfRange(arr, 0, mid);
int[] right = Arrays.copyOfRange(arr, mid, arr.length);
// recursively sort each half
mergeSort(left);
mergeSort(right);
// merge the two sorted halves
int i = 0;
int j = 0;
int k = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
k++;
}
while (i < left.length) {
arr[k] = left[i];
i++;
k++;
}
while (j < right.length) {
arr[k] = right[j];
j++;
k++;
}
}
public static void main(String[] args) {
int[] array = {7, 8, 2, 4, 5, 3};
// sort the array using merge sort
System.out.println("Unsorted array: " + Arrays.toString(array));
mergeSort(array);
System.out.println("Sorted array: " + Arrays.toString(array));
}
}
Merge.main(null);
public class SortAnalysis {
// generate array of 5000 integers
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[5000];
int[] arr3 = new int[5000];
int[] arr4 = new int[5000];
System.arraycopy(arr1, 0, arr2, 0, 5000);
System.arraycopy(arr1, 0, arr3, 0, 5000);
System.arraycopy(arr1, 0, arr4, 0, 5000);
float[] times = new float[4];
String str = "";
// sort the array
long start = System.nanoTime();
bubbleSort(arr1);
long end = System.nanoTime();
// print the time it took
str += ((end - start) + "ns | ");
times [0] = (end - start);
start = System.nanoTime();
mergeSort(arr2);
end = System.nanoTime();
// print the time it took
str += ((end - start) + "ns | ");
times [1] = (end - start);
start = System.nanoTime();
selectionSort(arr3);
end = System.nanoTime();
// print the time it took
str += ((end - start) + "ns | ");
times [2] = (end - start);
start = System.nanoTime();
insertionSort(arr4);
end = System.nanoTime();
// print the time it took
str += ((end - start) + "ns");
times [3] = (end - start);
System.out.println(str);
return times;
}
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// instertionsort from before
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[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 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// selectionsort from before
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
// Find the minimum element in unsorted part of array
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum element with the first element
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
// mergesort from previous lesson
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);
}
}
// lefthalf function for mergesort
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;
}
// righthalf function for mergesotr
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] + "ns | " + means[1] + "ns | " + means[2] + "ns | " + means[3] + "ns");
Big O Notation Notes
Merge Sort:
- Time Complexity: O(n log n)
- Number of Comparisons: O(n log n)
- Number of Swaps: O(n log n) ##### Insertion Sort:
- Time Complexity: O(n^2)
- Number of Comparisons: O(n^2)
- Number of Swaps: O(n^2) ##### Bubble Sort:
- Time Complexity: O(n^2)
- Number of Comparisons: O(n^2)
- Number of Swaps: O(n^2) ##### Selection Sort:
- Time Complexity: O(n^2)
- Number of Comparisons: O(n^2)
- Number of Swaps: O(n)
Extra Sort Notes
- Quick Sort: This algorithm divides the list into two smaller sub-lists around a pivot element and recursively sorts each sub-list. The time complexity of Quick Sort is O(n log n) on average, which means that it can sort a list of n elements in roughly log n recursive steps, with each step taking O(n) time.
- This algorithm transforms the list into a heap data structure, where each element is larger than its children (for a max heap). It then repeatedly removes the largest element from the heap and places it at the end of the list. The time complexity of Heap Sort is also O(n log n), because it needs to perform log n heapify operations for each of the n elements.
import java.util.HashMap;
public class HashTester {
public static void main(String[] args) {
Map<String, String> hashMap = new HashMap<String, String>();
for (int i = 0; i < 5000; i++) {
hashMap.put("key" + i, "value" + i);
}
// List<Integer> key = new ArrayList<Integer>();
// for (int i = 0, i < 100; i++){
// key.add(i);
// }
List<String> keys = new ArrayList<String>(hashMap.keySet());
Collections.shuffle(keys);
Collections.sort(keys);
long startTime = System.nanoTime();
for (int i = 0; i < 100; i++) {
// int index = Collections.binarySearch(keys, key);
int index = Collections.binarySearch(keys, "key" + i);
if (index >= 0) {
System.out.println("Found key: " + keys.get(index) + " with value: " + hashMap.get(keys.get(index)));
}
}
long elapsedTime = System.nanoTime() - startTime;
long startTime2 = System.nanoTime();
for (int i = 0; i < 100; i++) {
String key = "key" + i;
if (hashMap.containsKey(key)) {
System.out.println("Found key: " + key + " with value: " + hashMap.get(key));
}
}
long elapsedTime2 = System.nanoTime() - startTime2;
System.out.println("Time it took to complete Binary Search in milliseconds: " + elapsedTime/1000000);
System.out.println("Time it took to complete Hash Search in milliseconds: " + elapsedTime2/1000000);
}
}
HashTester.main(null);