This code implements the Selection Sort algorithm to sort an array in ascending order. It does so by iterating over the array n-1 times, each time finding the smallest element in the unsorted portion of the array and swapping it with the first element in the unsorted portion of the array. The algorithm has a time complexity of O(n^2) and is generally less efficient than other sorting algorithms, such as the Merge Sort and Quick Sort. However, it can be useful in certain situations, such as when memory usage is a concern.
import java.util.Arrays;
public class SelectionSort {
public static void main(int[] arr) {
// Get the length of the array
int n = arr.length;
// Iterate over the array n-1 times
for (int i = 0; i < n - 1; i++) {
// Print out the array at the beginning of each iteration
//System.out.println(Arrays.toString(arr));
// Set the minimum index to the current index
int minIndex = i;
// Find the index of the smallest element in the unsorted portion of the array
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the smallest element with the first element in the unsorted portion of the array
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
// Print out the sorted array
//System.out.println(Arrays.toString(arr));
}
}
// Call the SelectionSorting.main() method to run the program
int[] arr = {32,96, 7, 3, 68};
SelectionSort.main(arr);
This code implements the Insertion Sort algorithm to sort an array in ascending order. It does so by iterating over the array and inserting each element into its correct position in the sorted portion of the array. The algorithm has a time complexity of O(n^2) but can be more efficient than other O(n^2) algorithms, such as the Selection Sort and Bubble Sort, for small arrays or partially sorted arrays. Since each swap takes constant time, the total time complexity of the algorithm becomes O(n^2).
import java.util.Arrays;
public class InsertionSort {
public static void main(int[] arr) {
// Iterate over the array starting from the second element
for (int i = 1; i < arr.length; i++) {
// Print out the array at the beginning of each iteration
//System.out.println(Arrays.toString(arr));
// Assign the current element to a temporary variable 'key'
int key = arr[i];
// Set j to the index of the element immediately to the left of the current element
int j = i - 1;
// Shift any elements to the right of 'key' that are greater than 'key'
// to the right, until we find the correct position for 'key'
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
// Insert 'key' into the correct position in the sorted portion of the array
arr[j + 1] = key;
}
// Print out the sorted array
//System.out.println(Arrays.toString(arr));
}
}
// Call the InsertionSort.main() method to run the program
int[] arr = {32, 96, 7, 3, 68};
InsertionSort.main(arr);
Merge Sort is a divide-and-conquer algorithm that sorts an array by recursively dividing it into two halves, sorting the two halves, and then merging the two sorted halves. The mergeSort method is used to divide the array into subarrays and sort them, while the merge method is used to merge the two sorted subarrays back into the original array. The algorithm has a time complexity of O(n log n) and is a popular choice for sorting large data sets.
import java.util.Arrays;
public class MergeSort {
public static void main(int[] arr) {
//System.out.println(Arrays.toString(arr));
mergeSort(arr, 0, arr.length - 1);
//System.out.println(Arrays.toString(arr));
}
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
// Find the middle point of the array
int middle = (left + right) / 2;
// Sort the left half of the array recursively
mergeSort(arr, left, middle);
// Sort the right half of the array recursively
mergeSort(arr, middle + 1, right);
// Merge the two sorted halves of the array
merge(arr, left, middle, right);
}
}
public static void merge(int[] arr, int left, int middle, int right) {
// Find the lengths of the two subarrays
int n1 = middle - left + 1;
int n2 = right - middle;
// Create temporary arrays to store the two subarrays
int[] leftArr = new int[n1];
int[] rightArr = new int[n2];
// Copy the elements of the left subarray into the leftArr array
for (int i = 0; i < n1; i++) {
leftArr[i] = arr[left + i];
}
// Copy the elements of the right subarray into the rightArr array
for (int j = 0; j < n2; j++) {
rightArr[j] = arr[middle + 1 + j];
}
// Merge the two subarrays
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
}
k++;
}
// Copy the remaining elements of the left subarray into the merged array
while (i < n1) {
arr[k] = leftArr[i];
i++;
k++;
}
// Copy the remaining elements of the right subarray into the merged array
while (j < n2) {
arr[k] = rightArr[j];
j++;
k++;
}
}
}
// Call the MergeSort.main() method to run the program
int[] arr = {32, 96, 7, 3, 68};
MergeSort.main(arr);
This Java program demonstrates the Bubble Sort algorithm for sorting an array of integers in ascending order. The program declares an array of integers, initializes it with values, and then uses a nested while and for loop to iterate over the array and compare adjacent elements. If the current element is less than the previous element, the two elements are swapped. This process continues until no more swaps are necessary, at which point the sorted array is printed to the console. The program also includes comments to explain each section of the code.
import java.util.Arrays;
public class BubbleSort {
public static void main(int[] arr) {
boolean swap = true;
while(swap){
swap = false;
for (int i = 1; i < arr.length; i++) {
// Print out the array at the beginning of each iteration
//System.out.println(Arrays.toString(arr));
int temp = 0;
if (arr[i] < arr[i-1]){
swap = true;
temp = arr[i];
arr[i] = arr[i-1];
arr[i-1] = temp;
}
}
}
//System.out.println(Arrays.toString(arr));
}
}
// Call the BubbleSort.main() method to run the program
int[] arr = {32, 96, 7, 3, 68};
BubbleSort.main(arr);
public class TimeAnalysis {
public static void main(String[] arg) {
long totaltime1 = 0;
long totaltime2 = 0;
long totaltime3 = 0;
long totaltime4 = 0;
int repeat = 100;
int[] arr1 = new int[5000];
int[] arr2 = null;
int[] arr3 = null;
int[] arr4 = null;
for(int j = 0; j < repeat; j++){
// making a 5000 int array
for (int i = 0; i < arr1.length; i++) {
arr1[i] = (int) (Math.random() * 10000);
}
// assign the value of arr1 to arr2, arr3, and arr4
arr2 = Arrays.copyOf(arr1, arr1.length);
arr3 = Arrays.copyOf(arr1, arr1.length);
arr4 = Arrays.copyOf(arr1, arr1.length);
// time output selection
long start1 = System.nanoTime();
SelectionSort.main(arr1);
long end1 = System.nanoTime();
long time1 = end1 - start1;
totaltime1 += (time1);
// time output insertion
long start2 = System.nanoTime();
InsertionSort.main(arr2);
long end2 = System.nanoTime();
long time2 = end2 - start2;
totaltime2 += (time2);
// time output Merge
long start3 = System.nanoTime();
MergeSort.main(arr3);
long end3 = System.nanoTime();
long time3 = end3 - start3;
totaltime3 += (time3);
// time output Bubble
long start4 = System.nanoTime();
BubbleSort.main(arr4);
long end4 = System.nanoTime();
long time4 = end4 - start4;
totaltime4 += (time4);
}
// create a map that maps each sorting algorithm to its corresponding time
Map<String, Long> timeMap = new HashMap<>();
timeMap.put("Selection Sort", totaltime1 / repeat);
timeMap.put("Insertion Sort", totaltime2 / repeat);
timeMap.put("Merge Sort", totaltime3 / repeat);
timeMap.put("Bubble Sort", totaltime4 / repeat);
// sort the map by values
List<Map.Entry<String, Long>> sortedList = new ArrayList<>(timeMap.entrySet());
Collections.sort(sortedList, Map.Entry.comparingByValue());
// print the sorted map
for (Map.Entry<String, Long> entry : sortedList) {
System.out.println(entry.getKey() + " Average: " + entry.getValue());
}
}
}
// Call the TimeAnalysis.main() method to run the program
TimeAnalysis.main(null);
After running it many times, the order of the four to sort the array is: Merge, Insertion, Selection, Bubble from least amount of time the most amount of time.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
public class Hash {
public static void main(String[] args) {
// Creating a new HashMap object to store key-value pairs
HashMap<Integer, Integer> hashmap = new HashMap<Integer, Integer>();
// Creating a new integer array with size 5000
int[] list = new int[5000];
// Creating two ArrayLists to store lookup and binary search times
ArrayList<Long> lookUpTimes = new ArrayList<>();
ArrayList<Long> binarySearchTimes = new ArrayList<>();
// Looping 100 times
for (int j = 0; j < 1000; j++) {
// Looping through the list and adding random integer values to the HashMap
for (int i = 0; i < list.length; i++) {
int value = (int) (Math.random() * 5000);
hashmap.put(value, value);
list[i] = value;
}
// Calculating the lookup time for the HashMap and adding it to the lookUpTimes ArrayList
long lookUpTime = lookUp(hashmap, (int) (Math.random() * 5000));
lookUpTimes.add(lookUpTime);
// Calculating the binary search time for the integer array and adding it to the binarySearchTimes ArrayList
long binarySearchTime = binarySearchTime(list, (int) (Math.random() * 5000));
binarySearchTimes.add(binarySearchTime);
// Clearing the HashMap for the next iteration
hashmap.clear();
}
// Calculating the average, mean, median, mode, max, and min of the lookUpTimes and binarySearchTimes ArrayLists
double avgLookUpTime = Statistics.average(lookUpTimes);
double sdLookUpTime = Statistics.standardDeviation(lookUpTimes);
long medianLookUpTime = Statistics.median(lookUpTimes);
long modeLookUpTime = Statistics.mode(lookUpTimes);
long minLookUpTime = Statistics.minimum(lookUpTimes);
long maxLookUpTime = Statistics.maximum(lookUpTimes);
double avgBinarySearchTime = Statistics.average(binarySearchTimes);
double sdBinarySearchTime = Statistics.standardDeviation(binarySearchTimes);
long medianBinarySearchTime = Statistics.median(binarySearchTimes);
long modeBinarySearchTime = Statistics.mode(binarySearchTimes);
long minBinarySearchTime = Statistics.minimum(binarySearchTimes);
long maxBinarySearchTime = Statistics.maximum(binarySearchTimes);
// Printing out the results to the console
System.out.println("Lookup Times:");
System.out.println("Average: " + avgLookUpTime + " nanoseconds");
System.out.println("Standard Deviation: " + sdLookUpTime + " nanoseconds");
System.out.println("Median: " + medianLookUpTime + " nanoseconds");
System.out.println("Mode: " + modeLookUpTime + " nanoseconds");
System.out.println("Max: " + maxLookUpTime + " nanoseconds");
System.out.println("Min: " + minLookUpTime + " nanoseconds");
System.out.println();
System.out.println("Binary Search Times:");
System.out.println("Average: " + avgBinarySearchTime + " nanoseconds");
System.out.println("Standard Deviation: " + sdBinarySearchTime + " nanoseconds");
System.out.println("Median: " + medianBinarySearchTime + " nanoseconds");
System.out.println("Mode: " + modeBinarySearchTime + " nanoseconds");
System.out.println("Max: " + maxBinarySearchTime + " nanoseconds");
System.out.println("Min: " + minBinarySearchTime + " nanoseconds");
}
// Method to calculate the lookup time for the HashMap
public static long lookUp(HashMap<Integer, Integer> hashmap, Integer value) {
long start = System.nanoTime(); // Get the current system time in nanoseconds
hashmap.containsKey(value); // Check if the HashMap contains the specified key
long end = System.nanoTime(); // Get the current system time in nanoseconds
return (end - start); // Return the difference between the start and end times
}
// Method to calculate the binary search time for the integer array
public static long binarySearchTime(int[] list, Integer value) {
long start = System.nanoTime(); // Get the current system time in nanoseconds
int low = 0; // Initialize the lowest index to 0
int high = list.length - 1; // Initialize the highest index to the length of the list - 1
int middle = (low + high) / 2; // Calculate the middle index
// Loop through the array until the value is found or the low index is greater than the high index
while (low <= high) {
if (list[middle] < value) {
low = middle + 1; // If the value at the middle index is less than the specified value, adjust the lowest index
} else if (list[middle] == value) {
break; // If the value at the middle index is equal to the specified value, break out of the loop
} else {
high = middle - 1; // If the value at the middle index is greater than the specified value, adjust the highest index
}
middle = (low + high) / 2; // Recalculate the middle index
}
long end = System.nanoTime(); // Get the current system time in nanoseconds
return (end - start); // Return the difference
}
}
Hash.main(null);
Considering the search time of 70.726 nanoseconds and the binary search time of 175.89 nanoseconds, we can see that the binary search algorithm is slower than the linear search algorithm for this particular use case. However, it is worth noting that the standard deviation of the binary search times is smaller than the standard deviation for the lookup times, indicating that the binary search algorithm can be more accurate in its implementation. The median and mode values of both algorithms are very close to their averages, indicating that the data are fairly evenly distributed. However, the maximum search time of 2126 nanoseconds and the maximum dual search time of 1681 nanoseconds suggest that there may be some anomalies in the data that result in long search times things are coming. It’s worth examining these outliers to see if there are any patterns or factors that are contributing to their long-term search.
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
public class Statistics {
// Method to calculate the average of an ArrayList
public static double average(ArrayList<Long> list) {
long sum = 0;
for (long num : list) {
sum += num;
}
return (double) sum / list.size();
}
// Method to calculate the median of an ArrayList
public static long median(ArrayList<Long> list) {
Collections.sort(list);
int middle = list.size() / 2;
if (list.size() % 2 == 0) {
long left = list.get(middle - 1);
long right = list.get(middle);
return (left + right) / 2;
} else {
return list.get(middle);
}
}
// Method to calculate the mode of an ArrayList
public static long mode(ArrayList<Long> list) {
HashMap<Long, Integer> frequencies = new HashMap<Long, Integer>();
for (long num : list) {
if (frequencies.containsKey(num)) {
frequencies.put(num, frequencies.get(num) + 1);
} else {
frequencies.put(num, 1);
}
}
long mode = 0;
int maxFrequency = 0;
for (long num : frequencies.keySet()) {
int frequency = frequencies.get(num);
if (frequency > maxFrequency) {
mode = num;
maxFrequency = frequency;
}
}
return mode;
}
// Method to calculate the minimum of an ArrayList
public static long minimum(ArrayList<Long> list) {
long min = Long.MAX_VALUE;
for (long num : list) {
if (num < min) {
min = num;
}
}
return min;
}
// Method to calculate the maximum of an ArrayList
public static long maximum(ArrayList<Long> list) {
long max = Long.MIN_VALUE;
for (long num : list) {
if (num > max) {
max = num;
}
}
return max;
}
// Method to calculate the standard deviation of an ArrayList
public static double standardDeviation(ArrayList<Long> list) {
double mean = average(list);
double sumOfSquaredDifferences = 0;
for (long num : list) {
double difference = num - mean;
double squaredDifference = difference * difference;
sumOfSquaredDifferences += squaredDifference;
}
double variance = sumOfSquaredDifferences / list.size();
double sds = Math.round(Math.sqrt(variance) * 100.0) / 100.0;
return sds;
}
}