Sorts
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);
//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);
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;
}
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);
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);
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);
//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);
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);
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);
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
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();
}
}))
}
}
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);
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);