Bubble Sort

We are switching each adjacent number. We have to go through the array length of array times.

Once a section is sorted, bubble sort will not touch those elements anymore.

https://leetcode.com/problems/minimum-swaps-to-arrange-a-binary-grid/description/

The worst-case time complexity of Bubble Sort is O(n^2) where n is the number of elements in the array.

In the given code, the outer while loop runs until the first time where no swaps happen, which means that the array is sorted. This loop can run at most n-1 times, where n is the length of the array.

Within the while loop, the for loop iterates over the array n-1 times. For each iteration, it compares adjacent elements and swaps them if they are in the wrong order.

The worst-case scenario occurs when the array is sorted in reverse order, and every element must be swapped with its adjacent element. In this case, the number of swaps is equal to the sum of the first n-1 positive integers, which is (n-1)(n-2)/2. Therefore, the total number of comparisons and swaps is (n-1)(n-2)/2, which is O(n^2).

Therefore, the time complexity of the Bubble Sort algorithm implemented in the given code is O(n^2).

public class BubbleSort{ 
    public static void main(String[] args)
    {
        int[] bubble_arr = {23,56,21,34,678,2,4,7,2235,996,446,999,6574,87,67,902,8754};
        System.out.print("Original: ");
        for(int index=0; index<bubble_arr.length; index++){
            System.out.print(bubble_arr[index] + ", ");
        }
        System.out.println();

        /* run continuously until the first time where no swaps happen */
        boolean swap = true;
        while(swap)
        {
            swap = false;
            for(int i=0; i<bubble_arr.length-1; i++){
                if (bubble_arr[i]>bubble_arr[i+1]){
                    swap = true;
                    int temp = bubble_arr[i];
                    bubble_arr[i] = bubble_arr[i+1];
                    bubble_arr[i+1] = temp;
                }
            }
        }
        System.out.print("Sorted: ");
        for(int index=0; index<bubble_arr.length; index++){
            System.out.print(bubble_arr[index] + ", ");
        }

        }
    
}

BubbleSort.main(null);
Original: 23, 56, 21, 34, 678, 2, 4, 7, 2235, 996, 446, 999, 6574, 87, 67, 902, 8754, 
Sorted: 2, 4, 7, 21, 23, 34, 56, 67, 87, 446, 678, 902, 996, 999, 2235, 6574, 8754, 
//running with a nested while loop

public class BubbleSort{
    public static void main(String[] args)
    {
        int[] bubble_arr = {23,56,21,34,678,2,4,7,2235,996,446,999,6574,87,67,902,8754};
        System.out.print("Original: ");
        for(int index=0; index<bubble_arr.length; index++){
            System.out.print(bubble_arr[index] + ", ");
        }
        System.out.println();

        /* run continuously until the first time where no swaps happen */
       
        for(int passes=1; passes<bubble_arr.length-1; passes++){ // you need to run passes for 1 through length-1 times
          
            for(int i=0; i<bubble_arr.length-1; i++){
                if (bubble_arr[i]>bubble_arr[i+1]){
                    int temp = bubble_arr[i];
                    bubble_arr[i] = bubble_arr[i+1];
                    bubble_arr[i+1] = temp;
                }
            }
        }
        
        System.out.print("Sorted: ");
        for(int index=0; index<bubble_arr.length; index++){
            System.out.print(bubble_arr[index] + ", ");
        }

        }
    
}

BubbleSort.main(null);
Original: 23, 56, 21, 34, 678, 2, 4, 7, 2235, 996, 446, 999, 6574, 87, 67, 902, 8754, 
Sorted: 2, 4, 7, 21, 23, 34, 56, 67, 87, 446, 678, 902, 996, 999, 2235, 6574, 8754, 

Practice

public PalindromeicNumbers(int numPalindrome, int start){
    list = new int[numPalindrome];
    int position = 0;
    int values = start
    while(position<numPalindrome){
        if (isPalindromic(values)){
            list[position] = values;
            position++;
        }
        values++;
    
    }
}

public int sum(){
    int sum = 0;
    for(int i=0; i<list.length; <i++){
        sum = sum + list[i];
    }
    return sum; 
}
|   public PalindromeicNumbers(int numPalindrome, int start){
'.class' expected

Insertion Sort

  • Insertion sort has two different sections: a sorted one and an unsorted one.
  • It starts with the second element, or index 1, and decides where it belongs in the sorted section.
  • It inserts each index depending on hierarchy.
  • inserts to the left.
  • Big O notation is O(n) in the best case.
  • in the worst case, the notation is O(n^2)

The given code implements the Insertion Sort algorithm for sorting an array of integers. The worst-case time complexity of Insertion Sort is O(n^2) where n is the number of elements in the array.

The first for loop prints the original array, which takes O(n) time, where n is the number of elements in the array.

The second for loop iterates over the array n-1 times, where n is the length of the array. For each iteration, the inner loop iterates from the current index to the beginning of the array, checking whether the current element is smaller than the previous element. If so, it swaps the two elements. The inner loop may iterate up to i times, where i is the current index in the outer loop.

The worst-case scenario occurs when the array is sorted in reverse order, and every element must be moved to the beginning of the array. In this case, the total number of comparisons and swaps is equal to the sum of the first n-1 positive integers, which is (n-1)*(n-2)/2. Therefore, the total time complexity of the algorithm is O(n^2).

Therefore, the time complexity of the Insertion Sort algorithm implemented in the given code is O(n^2).

public class Insertion{
    public static void main(String[] args){
      int[] array = {3,2,5,1,0,10,43,2353,32,75,12,33};
      
      for(int i = 0; i<array.length; i++){
          System.out.print(array[i] + ", ");
      }
      System.out.println();

      
      for(int index=1; index<array.length; index++){
        for(int sorted_index = index; sorted_index>0; sorted_index--){
            if(array[sorted_index]<array[sorted_index-1]){
                int temp = array[sorted_index];
                array[sorted_index] = array[sorted_index-1];
                array[sorted_index-1] = temp;
            }
        }
      }
      
      for (int i = 0; i<array.length; i++){
        System.out.print(array[i] + ", ");
      }
    
    }
  }
  
  
  
  Insertion.main(null);
3, 2, 5, 1, 0, 10, 43, 2353, 32, 75, 12, 33, 
0, 1, 2, 3, 5, 10, 12, 32, 33, 43, 75, 2353, 
public class InsertionSort {
    public static void insertionSort(int[] x) {
        for (int i = 1; i < x.length; i++) {
            int temp = x[i];
            int j = i - 1;
            while (j >= 0 && x[j] > temp) {
                x[j + 1] = x[j];
                j--;
            }
            x[j + 1] = temp;
        }
    }

    public static void main(String[] args) {
        final int TIMES = 12;
        final int SIZE = 5000;
        double sum = 0; //double b/c int might be too short
        double time = 0;

        for (int i = 0; i < TIMES; i++) {
            int[] data = new int[SIZE];
            for (int j = 0; j < data.length; j++) {
                data[j] = (int) (Math.random() * SIZE);
            }
            double startTime = System.nanoTime();
            insertionSort(data);
            double endTime = System.nanoTime();
            sum += calculateSum(data);
            time += endTime - startTime;
        }
        System.out.println("Average: " + sum / (TIMES * SIZE));
        System.out.println("Total Seconds: " + time / 1000000000.0);
    }

    private static double calculateSum(int[] data) {
        double sum = 0;
        for (int j = 0; j < data.length; j++) {
            sum += data[j];
        }
        return sum;
    }
}

InsertionSort.main(null);
Average: 2504.3166666666666
Total Seconds: 0.066990999

Selection Sort

  • If we have a set of numbers that are unsorted, we most the lowest number to the end.
  • We keep taking the lowest number from the unsorted section, and adding it to the right of the sorted section.
  • In place sorting algorithm takes constant amount of memory.

The given code implements the Selection Sort algorithm for sorting an array of integers. The worst-case time complexity of Selection Sort is O(n^2) where n is the number of elements in the array.

The first for loop prints the original array, which takes O(n) time, where n is the number of elements in the array.

The second for loop iterates over the array n-1 times, where n is the length of the array. For each iteration, it finds the minimum element in the remaining unsorted portion of the array, and swaps it with the first element of the unsorted portion. The inner loop iterates over the remaining unsorted portion of the array, which can be at most n-1 elements.

The worst-case scenario occurs when the array is sorted in reverse order, and every element must be moved to the beginning of the array. In this case, the total number of comparisons and swaps is equal to the sum of the first n-1 positive integers, which is (n-1)*(n-2)/2. Therefore, the total time complexity of the algorithm is O(n^2).

Therefore, the time complexity of the Selection Sort algorithm implemented in the given code is O(n^2)

//Method 1: PLacing all the lowest integers to the right, or the end of the array. 

public class Selection {
    public static void main(String[] args){
        int[] array = {23,12,57,335,5433,24567,64,25,66};
        for (int i = 0; i<array.length; i++){
            System.out.print(array[i] + ", ");
          }
          System.out.println();
        int times = array.length;
        for (int outer=times; outer>0; outer--){
            int min = 0xFFFFFF;
            int min_idx = 0;
            for(int i=0; i<outer; i++){// finding the min 
                if(array[i] < min){
                    min = array[i];
                    min_idx = i;
                }
            }
            for (int j = min_idx+1; j < array.length; j++){ // move everything to the left once
                 array[j-1]=array[j];
            }
            array[array.length-1] = min;
        }
        for (int i = 0; i<array.length; i++){
            System.out.print(array[i] + ", ");
          }
    }
}

Selection.main(null);
23, 12, 57, 335, 5433, 24567, 64, 25, 66, 
12, 23, 25, 57, 64, 66, 335, 5433, 24567, 
//Method 2: PLacing all the lowest integers to the right, or the end of the array. 

public class Selection2 {
    public static void main(String[] args){
        int[] array = {23,12,57,335,5433,24567,64,25,66};
        for (int i = 0; i<array.length; i++){
            System.out.print(array[i] + ", ");
          }
          System.out.println();


        boolean sorted = false;
        int count=0;
        for(int i=0; i<array.length-1; i++){
            if(array[i]< array[i+1]){
                count = count+1;
            }
            if(count==array.length-1){
                sorted=true;
            }
        }
        
       
        int times = array.length;
        while(times>0){
            int min = 0xFFFFFF; //max int possible
            int min_idx = 0;
            for(int i=0; i<times; i++){
                if (array[i] == min){
                    break;
                }
                if(array[i] < min){
                    min = array[i];
                    min_idx = i;
                    
                }
            }





            for (int j = min_idx+1; j < array.length; j++){
                        array[j-1]=array[j];
            }
            array[array.length-1] = min;
            times = times-1;
        }


        
        for (int i = 0; i<array.length; i++){
            System.out.print(array[i] + ", ");
          }
    }
}

Selection2.main(null);
23, 12, 57, 335, 5433, 24567, 64, 25, 66, 
12, 23, 25, 57, 64, 66, 335, 5433, 24567, 
public class SelectionSort{
    public static void selectionSort(int[] numbers)
    {
        for(int i = 0; i < numbers.length - 1; i++)
        {
            int position = i;
            for(int k = i + 1; k < numbers.length; k++)
            {
                if (numbers[k] < numbers [position])
                {
                    position = k;
                }
            }
            int temp = numbers[i];
            numbers[i] = numbers[position];
            numbers[position] = temp;
        }
    }
    public static void main(String[] args) {
        final int TIMES = 12;
        final int SIZE = 5000;
        double sum = 0; //double b/c int might be too short
        double time = 0;

        for (int i = 0; i < TIMES; i++) {
            int[] data = new int[SIZE];
            for (int j = 0; j < data.length; j++) {
                data[j] = (int) (Math.random() * SIZE);
            }
            double startTime = System.nanoTime();
            selectionSort(data);
            double endTime = System.nanoTime();
            sum += calculateSum(data);
            time += endTime - startTime;
        }
        System.out.println("Average random: " + sum / (TIMES * SIZE));
        System.out.println("Total Seconds: " + time / 1000000000.0);
    }

    private static double calculateSum(int[] data) {
        double sum = 0;
        for (int j = 0; j < data.length; j++) {
            sum += data[j];
        }
        return sum;
    }
}

SelectionSort.main(null);
Average random: 2489.0466333333334
Total Seconds: 0.160089821

Conclusion on fastest sort: Merge Sort

Merge Sort is O(n log n), where n is the number of elements in the array.

The reason for this is that Merge Sort recursively divides the input array into halves until each subarray has only one element. The merge operation then takes linear time O(n) to merge two subarrays into a sorted array, where n is the total number of elements in both subarrays. Since each level of recursion takes O(n) time to merge the subarrays, and the recursion depth is O(log n), the overall time complexity of Merge Sort is O(n log n).

The space complexity of Merge Sort is O(n) because the temporary array temp used in the merge function requires O(n) space to store the merged subarrays. However, Merge Sort is a stable sorting algorithm, which means it maintains the relative order of equal elements in the input array, and this property is important in certain applications.

public class MergeSort {
    public static void main(String[] args){
        int[] arr = {23,12,57,335,5433,24567,64,25,66};
        mergeSort(arr, 0, arr.length-1);
        for(int i=0; i<arr.length; i++){
            System.out.print(arr[i] + ", ");
        }
    }

    public static void mergeSort(int[] arr, int left, int right){
        if(left < right){
            int mid = (left+right)/2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid+1, right);
            merge(arr, left, mid, right);
        }
    }

    public static void merge(int[] arr, int left, int mid, int right){
        int[] temp = new int[right-left+1];
        int i = left;
        int j = mid+1;
        int k = 0;

        while(i <= mid && j <= right){
            if(arr[i] < arr[j]){
                temp[k] = arr[i];
                k++;
                i++;
            }
            else{
                temp[k] = arr[j];
                k++;
                j++;
            }
        }

        while(i <= mid){
            temp[k] = arr[i];
            k++;
            i++;
        }

        while(j <= right){
            temp[k] = arr[j];
            k++;
            j++;
        }

        for(int x=0; x<temp.length; x++){
            arr[left+x] = temp[x];
        }
    }
}
public class MergeSort {
    public static void mergeSort(int[] x) {
        int[] temp = new int[x.length];
        mergeSortHelper(x, 0, x.length - 1, temp);
    }

    public static void mergeSortHelper(int[] x, int lowIndex, int highIndex, int[] temp) {
        if (lowIndex < highIndex) {
            int mid = (lowIndex + highIndex) / 2;
            mergeSortHelper(x, lowIndex, mid, temp);
            mergeSortHelper(x, mid + 1, highIndex, temp);
            merge(x, lowIndex, mid, highIndex, temp);
        }
    }

    public static void merge(int[] x, int lowIndex, int mid, int highIndex, int[] temp) {
        int l = lowIndex;
        int m = mid + 1;
        int n = lowIndex;

        while (l <= mid && m <= highIndex) {
            if (x[l] < x[m]) {
                temp[n] = x[l];
                l++;
            } else {
                temp[n] = x[m];
                m++;
            }
            n++;
        }

        while (l <= mid) {
            temp[n] = x[l];
            l++;
            n++;
        }

        while (m <= highIndex) {
            temp[n] = x[m];
            m++;
            n++;
        }

        for (n = lowIndex; n <= highIndex; n++) {
            x[n] = temp[n];
        }
    }

    public static void main(String[] args) {
        final int TIMES = 12;
        final int SIZE = 5000;
        double sum = 0;
        double time = 0;

        for (int i = 0; i < TIMES; i++) {
            int[] data = new int[SIZE];
            for (int j = 0; j < data.length; j++) {
                data[j] = (int) (Math.random() * 100000);
            }
            double startTime = System.nanoTime();
            mergeSort(data);
            double endTime = System.nanoTime();
            sum += getSum(data);
            time += endTime - startTime;
        }
        System.out.println("Average: " + sum / (TIMES * SIZE));
        System.out.println("Total Seconds: " + time / 1000000000.0);
    }

    public static double getSum(int[] data) {
        double sum = 0;
        for (int i = 0; i < data.length; i++) {
            sum += data[i];
        }
        return sum;
    }
}

MergeSort.main(null);
Average: 49943.166816666664
Total Seconds: 0.010133108

Hashmaps

Hash maps are data structures that store data in key-value pairs. They allow for fast retrieval of data based on a given key. In a hash map, the key is run through a hash function that converts it into an index within an array. The value associated with that key is then stored in the array at the corresponding index.

The use of hash functions allows for constant-time access to the value associated with a given key, making hash maps very efficient for data retrieval. Hash maps are widely used in computer science and programming for tasks such as caching, database indexing, and implementing associative arrays.

We are using a binary search tree to sort through the values. Then , once we find the value, then we associate the value. Caluclate the time, and return it.

import java.util.HashMap;
import java.lang.Integer;
import java.util.Scanner;

public class HashMapSortByValue {
    public static void main(String[] args){
        HashMap<Integer, Integer> hashmap = new HashMap<Integer, Integer>();
        int[] list = new int[5000];

        for (int i = 0; i < list.length; i++) {
            Integer value = (int) (Math.random() * 5000);
            hashmap.put(value, value);
            list[i] = value;
        }

        long HM_time = (hash(hashmap, 12));
        System.out.println("Average time using sort with Hashmap " + HM_time + " nanoseconds");
        long BS_time = (binarySearchTime(list, 12));
        System.out.println("Average time using binary search " + BS_time + " nanoseconds"); 
        
    }

    public static long hash(HashMap<Integer, Integer> hashmap, Integer value) {
        long start = System.nanoTime();
        hashmap.containsKey(value);
        long end = System.nanoTime();
        return (end - start);
      
    }

    public static long binarySearchTime(int[] list, Integer value) {
        long start = System.nanoTime();
        /*
        *  Binary Search is repeatedly dividing in half the portion of the list that could contain the item, 
        *  until you've narrowed down the possible locations to just one.
        */
        int low = 0;
        int high = list.length - 1;
        int middle = (low + high) / 2;
        while (low <= high) {
            if (list[middle] < value) {
                low = middle + 1;
            } else if (list[middle] == value) {
                break;
            } else {
                high = middle - 1;
            }
            middle = (low + high) / 2;
        }
        long end = System.nanoTime();
        return (end - start);
    }
    
    


}
HashMapSortByValue.main(null);

// The binary search time is supposed to be significantly higher than the sort using hashmap
Average time using sort with Hashmap  8221 nanoseconds
Average time using binary search 23456543 nanoseconds
public class Hashmap_explore{
    public static void main(String[] args){
        HashMap<Integer, Integer> hashmap = new HashMap<Integer, Integer>();
        int[] list = new int[5000];

        for (int i = 0; i < list.length; i++) {
            Integer value = (int) (Math.random() * 5000);
            hashmap.put(value, value);
            list[i] = value;
        }
//learning a different method on how to do the sorting. Here, we are overiding the compare method method, and returning the 
// hashmap in asscending order. The time complexity is the same for this. 

        Collections.sort(list, new  Comparator<Map.Entry<Integer, Integer>>({
            public int compare(Map.Entry<Integer, Integer> int1, Map.Entry<Integer, Integer> int2){
                return int1.getValue()- int2.getValue();
            }
        }))
    }

    
}

Extras on Iteration, Add and Delete For Hashmaps

import java.util.*;
 

class Iterate_Hash {

    public static void main(String[] args)
    {
 
        // Creating an Hashmap of string-integer pairs
        // It contains student name and their marks
        HashMap<String, Integer> hm
            = new HashMap<String, Integer>();
 
        // Adding mappings to above HashMap
        // using put() method
        hm.put("Aadya", 16);
        hm.put("Avanthika", 14);
        hm.put("Pranavi", 16);
 
        // Printing all elements of HashMap
        System.out.println("Created hashmap is" + hm);
 
        Iterator hmIterator = hm.entrySet().iterator();
 
     
        System.out.println(
            "HashMap after adding bonus marks:");
 
        // Iterating through Hashmap and
        // adding 10 to age
        while (hmIterator.hasNext()) {
 
            Map.Entry mapElement
                = (Map.Entry)hmIterator.next();
            int marks = ((int)mapElement.getValue() + 10);
 
            // Printing new map
            System.out.println(mapElement.getKey() + " : "
                               + marks);
        }
    }
}

Iterate_Hash.main(null);
Created hashmap is{Pranavi=16, Avanthika=14, Aadya=16}
HashMap after adding bonus marks:
Pranavi : 26
Avanthika : 24
Aadya : 26
import java.util.*;
 
public class Delete_hashmap {
public static void main(String[] args) {
         
    // Creating an empty HashMap
    HashMap<Integer, String> hash_map = new HashMap<Integer, String>();
 
    // adding values to thhe hash map
    hash_map.put(1, "English");
    hash_map.put(2, "CSA");
    hash_map.put(3, "Engineering");
    hash_map.put(4, "Physics");
    hash_map.put(5, "Calc");
 
    // Displaying the HashMap
    System.out.println("Initial Mappings are: " + hash_map);
 
    // Removing the existing key mapping
    String returned_value = (String)hash_map.remove(1);
 

    System.out.println("Returned value is: "+ returned_value);
 
    // pringting the new map
    System.out.println("New map is: "+ hash_map);
}
}
Delete_hashmap.main(null);
Initial Mappings are: {1=English, 2=CSA, 3=Engineering, 4=Physics, 5=Calc}
Returned value is: English
New map is: {2=CSA, 3=Engineering, 4=Physics, 5=Calc}