Sorting Algs
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();
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);
public class Insertion{
public static void main(String[] args){
int[] list = {16,3,26,617,261,51,126,6,23,2,16,1236};
for(int i = 0; i<list.length; i++){
System.out.print(list[i] + ", ");
}
System.out.println();
for(int index=1; index<list.length; index++){
for(int sorted_index = index; sorted_index>0; sorted_index--){
if(list[sorted_index]<list[sorted_index-1]){
int temp = list[sorted_index];
list[sorted_index] = list[sorted_index-1];
list[sorted_index-1] = temp;
}
}
}
for (int i = 0; i<list.length; i++){
System.out.print(list[i] + ", ");
}
}
}
Insertion.main(null);
public class Selection {
public static void main(String[] args){
int[] array = {236,16,3156,3325135,51,24567,12,3251,15};
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++){
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;
}
for (int i = 0; i<array.length; i++){
System.out.print(array[i] + ", ");
}
}
}
Selection.main(null);
big o analysis
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.
first for loop takes O(n) times
inner loop iterates over unsorted portion of the array (n-1)
complexity is O(n^2) the time complexity of the Selection Sort algorithm is O(n^2).
public class MergeSort {
public static void main(String[] args){
int[] arr = {12,126,51237,32635,164,236,126,26,714};
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];
}
}
}
Big O analysis
The big O time complexity of Merge Sort is O(n log n), where n is the number of elements in the array.
This is because Merge Sort recursively divides the input by half until each of the arrays only has one value. The reason for this is because Merge Sort algorthim uses linear time 0(n) to merge the subarrays into a sorted array where n is the total number of elements in both subarrays. By using this we find that the time complexity of Merge Sort is O(n log n).
import java.util.HashMap;
import java.lang.Integer;
import java.util.Scanner;
public class Hash {
public static void main(String[] args){
HashMap<Integer, Integer> numberhash = new HashMap<Integer, Integer>();
int[] list = new int[5000];
for (int i = 0; i < list.length; i++) {
Integer value = (int) (Math.random() * 5000);
numberhash.put(value, value);
list[i] = value;
}
for (int i = 0; i<12; i++) {
System.out.println("Run " + (i+1));
Integer target = (int) (Math.random() * 5000);
long lookUpTime = (lookUp(numberhash, target));
System.out.println("Look up time: " + lookUpTime + " nanoseconds");
long binarySearchTime = (binarySearchTime(list, target));
System.out.println("Binary search time: " + binarySearchTime + " nanoseconds");
}
}
public static long lookUp(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();
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);
}
}
Hash.main(null);