Bubble Sort
- iterates through starting at the first index, compare the first and second elements
- if the first element if greater than the second element then they are swapped otherwise they are not swaped and the iteration ends
- then compare the second and third elements and swap if they are not in order
- this process continues until the last element for this specific element
- the remaining iterations do the same thing until the largest element is placed at the end
- in each iteration the comparsion takes place up to the last unsorted element
import java.util.*;
import java.lang.*;
class SortManager<Integer extends Comparable<Integer>> {
private final String name;
private Integer temp;
private ArrayList<Integer> lefty = new ArrayList<Integer>();
private ArrayList<Integer> righty = new ArrayList<Integer>();
public ArrayList<Integer> arr1 = new ArrayList<Integer>(); // Creates arraylist to be implemented into the different sort methods
public ArrayList<Integer> arr2 = new ArrayList<Integer>();
public ArrayList<Integer> arr3 = new ArrayList<Integer>();
public ArrayList<Integer> arr4 = new ArrayList<Integer>();
public SortManager(String name) {
this.name = name;
}
public SortManager(String name, Integer[] list) {
this.name = name;
this.addList(list);
}
public void addList(Integer[] list) {
// for (Integer[] objects: seriesOfObjects)
for (Integer data: list) {
this.arr1.add(data);
this.arr2.add(data);
this.arr3.add(data);
this.arr4.add(data);
}
}
public void bubbleSort(ArrayList<Integer> array) {
int n = array.size(); // find the length of the arraylist
for (int i = 0; i < n - 1; i++) { // iterates through every element in the arraylist
for (int j = 0; j < n - i - 1; j++) { // makes sure that the current index is less than the length and does not repeat iteration over the elements that are already "locked" in their place
Integer x = array.get(j);
Integer y = array.get(j+1);
if (x.compareTo(y) > 0) { // if the first element is greater than second element then they are swapped otherwise the position of that element is locked and it moves to the next element
// only happens if the swap occurs
// when implemented into the queue, this is where the compare to method would be used
this.temp = x;
array.set(j, y);
array.set(j + 1, this.temp); // easy swap function
System.out.println("Swapped " + x + " with " + y + " for index " + j);
}
else{
System.out.println("No swap needed for " + x + " at index " + j);
}
}
System.out.println(array);
}
}
public void selectionSort(ArrayList<Integer> array) {
int n = array.size();
for (int i = 0; i < n-1;i++) {
int minimumIndex = i; // setting the minimum to the first value in the array before iterating to find the true minimum value
for (int j = i + 1; j < n; j++){
if (array.get(j).compareTo(array.get(minimumIndex)) < 0) {
minimumIndex = j;
System.out.println("The minimum value in the array is now " + j); // finds the true minimum of the array
}
}
this.temp = array.get(minimumIndex);
array.set(minimumIndex, array.get(i));
array.set(i, this.temp); // easy swap function
System.out.println("Swapped " + array.get(i) + " with " + array.get(minimumIndex) + " for index " + i);
System.out.println(array);
}
}
public void insertionSort(ArrayList<Integer> array) {
int n = array.size();
for (int i = 0; i < n-1;i++) {
Integer current = array.get(i); // takes the second element in the array
int j = i - 1;
while (j >= 0 && (array.get(j).compareTo(current) > 0)) { // the swap only executes if j is greater than 0 meaning that there are still values in front of j and that the element in front of the current one is greater tan the current
array.set(j + 1, array.get(j));
System.out.println("Swapped " + current + " with " + array.get(j) + " for index " + i);
j = j - 1;
}
array.set(j+1, current);
System.out.println(array);
}
}
public void middlePart(ArrayList<Integer> array, int left, int right) {
if (left < right) {
int middle = left + ((right-1) / 2);
middlePart(array, left, middle);
middlePart(array, middle + 1, right);
mergeSort(array, left, middle, right);
}
}
public void mergeSort(ArrayList<Integer> array, int left, int middle, int right) {
int n = middle - left + 1;
int n2 = right - middle;
for (int i=0; i<n; i++){
lefty.add(i,array.get(left + i));
}
for (int j=0; j<n2; j++){
righty.add(j,array.get(middle+1+j));
}
int i = 0, j = 0;
int k = left;
while ( i < n && j < n2) {
if (lefty.get(i).compareTo(righty.get(j)) < 0) {
array.set(k, lefty.get(i));
i++;
}
else {
array.set(k, righty.get(j));
j++;
}
k++;
}
while (i<n) {
array.set(k, lefty.get(i));
i++;
k++;
}
while (j <n2) {
array.set(k, righty.get(j));
j++;
k++;
}
}
public void printQueue() {
System.out.println("Original List: ");
for (Integer data : arr1)
System.out.print(data + " ");
System.out.println();
System.out.println("Bubble Sorted List: ");
bubbleSort(arr1);
System.out.print(arr1);
System.out.println();
System.out.println();
System.out.println("Selection Sorted List: ");
selectionSort(arr2);
System.out.print(arr2);
System.out.println();
System.out.println();
System.out.println("Insertion Sorted List: ");
insertionSort(arr3);
System.out.print(arr3);
System.out.println();
System.out.println();
System.out.println("Merge Sorted List: ");
System.out.print(arr4);
System.out.println();
System.out.println();
}
}
class SortTester {
public static void main(String[] args) {
Integer[] sortdata = new Integer[] { 5, 1, 4, 2, 8 };
Integer[] sortdata2 = new Integer[] { 64, 34, 25, 12, 22, 11, 90 };
SortManager test = new SortManager("Int", sortdata);
test.printQueue();
SortManager test2 = new SortManager("Int", sortdata2);
test2.printQueue();
}
}
SortTester.main(null);
import java.util.*;
import java.lang.*;
class SortManager<Integer extends Comparable<Integer>> {
private final String name;
private Integer temp;
private ArrayList<Integer> lefty = new ArrayList<Integer>();
private ArrayList<Integer> righty = new ArrayList<Integer>();
public ArrayList<Integer> arr4 = new ArrayList<Integer>();
public SortManager(String name) {
this.name = name;
}
public SortManager(String name, Integer[] list) {
this.name = name;
this.addList(list);
}
public void addList(Integer[] list) {
// for (Integer[] objects: seriesOfObjects)
for (Integer data: list) {
this.arr4.add(data);
}
}
public void middlePart(ArrayList<Integer> array, int left, int right) {
if (left < right) {
int middle = left + ((right-1) / 2);
middlePart(array, left, middle);
middlePart(array, middle + 1, right);
mergeSort(array, left, middle, right);
}
}
public void mergeSort(ArrayList<Integer> array, int left, int middle, int right) {
int n = middle - left + 1;
int n2 = right - middle;
for (int i=0; i<n; i++){
lefty.add(i,array.get(left + i));
}
for (int j=0; j<n2; j++){
righty.add(j,array.get(middle+1+j));
}
int i = 0, j = 0;
int k = left;
while ( i < n && j < n2) {
if (lefty.get(i).compareTo(righty.get(j)) < 0) {
array.set(k, lefty.get(i));
i++;
}
else {
array.set(k, righty.get(j));
j++;
}
k++;
}
while (i<n) {
array.set(k, lefty.get(i));
i++;
k++;
}
while (j <n2) {
array.set(k, righty.get(j));
j++;
k++;
}
}
public void printQueue() {
System.out.println();
System.out.println();
System.out.println("Merge Sorted List: ");
middlePart(arr4, 0, arr4.size() - 1);
System.out.print(arr4);
System.out.println();
System.out.println();
}
}
class SortTester {
public static void main(String[] args) {
Integer[] sortdata = new Integer[] { 5, 1, 4, 2, 8 };
Integer[] sortdata2 = new Integer[] { 64, 34, 25, 12, 22, 11, 90 };
SortManager test = new SortManager("Int", sortdata);
test.printQueue();
SortManager test = new SortManager("Int", sortdata);
test.printQueue();
}
}
SortTester.main(null);
// Java program for implementation of Bubble Sort
import java.util.*;
class BubbleSort {
void bubbleSort(int arr[])
{
int n = arr.length;
int count = 0;
int count2 = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
count++;
if (arr[j] > arr[j + 1]) {
// swap arr[j+1] and arr[j]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
count2++;
}
}
}
System.out.println("Number of Comparison " + count);
System.out.println("Number of Swaps " + count2);
}
/* Prints the array */
void printArray(int arr[])
{
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver method to test above
public static void main(String args[])
{
BubbleSort ob = new BubbleSort();
Random rd = new Random(); // creating Random object
int[] arr = new int[5000];
for (int i = 0; i < arr.length; i++) {
arr[i] = rd.nextInt(10);
}
ob.printArray(arr);
ob.bubbleSort(arr);
System.out.println("Sorted array");
ob.printArray(arr);
}
}
BubbleSort.main(null);
Bubble Sort
| Number of Data | Time | Number of Comparisons | Number of Swaps |
|---|---|---|---|
| 20 | 0.4 s | 190 | 63 |
| 20 | 0.5 s | 190 | 100 |
| 20 | 0.3 s | 190 | 82 |
| 50 | 0.5 s | 1225 | 537 |
| 50 | 0.4 s | 1225 | 582 |
| 50 | 0.5 s | 1225 | 507 |
| 100 | 0.6 s | 4950 | 2243 |
| 100 | 0.6 s | 4950 | 2723 |
| 100 | 0.7 s | 4950 | 2030 |
| 500 | 1.3 s | 124750 | 52315 |
| 500 | 1.0 s | 124750 | 56154 |
| 500 | 0.6 s | 124750 | 58842 |
| 1000 | 1.5 s | 499500 | 222638 |
| 1000 | 1.7 s | 499500 | 232023 |
| 1000 | 1.3 s | 499500 | 226050 |
| 5000 | 7.1 s | 12497500 | 5657897 |
| 5000 | 7.3 s | 12497500 | 5642181 |
| 5000 | 7.7 | 12497500 | 5575902 |
// Java program for implementation of Selection Sort
import java.io.*;
public class SelectionSort
{
void sort(int arr[])
{
int n = arr.length;
int count = 0;
int count2 = 0;
// One by one move boundary of unsorted subarray
for (int i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
int min_idx = i;
for (int j = i+1; j < n; j++) {
count++;
if (arr[j] < arr[min_idx])
min_idx = j;
// Swap the found minimum element with the first
// element
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
count2++;
}
}
System.out.println("Number of Comparison " + count);
System.out.println("Number of Swaps " + count2);
}
// Prints the array
void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
// Driver code to test above
public static void main(String args[])
{
SelectionSort ob = new SelectionSort();
Random rd = new Random(); // creating Random object
int[] arr = new int[5000];
for (int i = 0; i < arr.length; i++) {
arr[i] = rd.nextInt(10);
}
ob.printArray(arr);
ob.sort(arr);
System.out.println("Sorted array");
ob.printArray(arr);
}
}
SelectionSort.main(null);
| Number of Data | Time | Number of Comparisons | Number of Swaps |
|---|---|---|---|
| 20 | 0.4 s | 190 | 190 |
| 20 | 0.4 s | 190 | 190 |
| 20 | 0.3 s | 190 | 190 |
| 50 | 0.2 s | 1225 | 1225 |
| 50 | 0.5 s | 1225 | 1225 |
| 50 | 0.7 s | 1225 | 1225 |
| 100 | 0.5 s | 4950 | 4950 |
| 100 | 0.5 s | 4950 | 4950 |
| 100 | 0.5 s | 4950 | 4950 |
| 500 | 4.0 s | 124750 | 124750 |
| 500 | 1.4 s | 124750 | 124750 |
| 500 | 1.5 s | 124750 | 124750 |
| 1000 | 2.0 s | 499500 | 499500 |
| 1000 | 1.6 s | 499500 | 499500 |
| 1000 | 1.3 s | 499500 | 499500 |
| 5000 | 8.0 s | 12497500 | 12497500 |
| 5000 | 7.0 s | 12497500 | 12497500 |
| 5000 | 6.1 s | 12497500 | 12497500 |
// Java program for implementation of Insertion Sort
public class InsertionSort {
/*Function to sort array using insertion sort*/
void sort(int arr[])
{
int n = arr.length;
int count = 0;
int count2 = 0;
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) {
count++;
arr[j + 1] = arr[j];
j = j - 1;
count2++;
}
arr[j + 1] = key;
}
System.out.println("Number of Comparison " + count);
System.out.println("Number of Swaps " + count2);
}
/* A utility function to print array of size n*/
static void printArray(int arr[])
{
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver method
public static void main(String args[])
{
InsertionSort ob = new InsertionSort();
Random rd = new Random(); // creating Random object
int[] arr = new int[5000];
for (int i = 0; i < arr.length; i++) {
arr[i] = rd.nextInt(10);
}
ob.printArray(arr);
ob.sort(arr);
System.out.println("Sorted array");
ob.printArray(arr);
}
};
InsertionSort.main(null);
| Number of Data | Time | Number of Comparisons | Number of Swaps |
|---|---|---|---|
| 20 | 0.3 s | 92 | 92 |
| 20 | 0.5 s | 92 | 92 |
| 20 | 0.3 s | 92 | 92 |
| 50 | 0.4 s | 511 | 511 |
| 50 | 0.5 s | 511 | 511 |
| 50 | 0.5 s | 511 | 511 |
| 100 | 0.5 s | 1970 | 1970 |
| 100 | 0.3 s | 2333 | 2333 |
| 100 | 0.5 s | 2296 | 2296 |
| 500 | 0.8 s | 53808 | 53808 |
| 500 | 0.6 s | 56663 | 56663 |
| 500 | 0.8 s | 54318 | 54318 |
| 1000 | 2.2 s | 213082 | 213082 |
| 1000 | 1.6 s | 219507 | 219507 |
| 1000 | 2.0 s | 226161 | 226161 |
| 5000 | 9.5 s | 5560675 | 5560675 |
| 5000 | 6.2 s | 5616655 | 5616655 |
| 5000 | 11.9 s | 5714100 | 5714100 |
/* Java program for Merge Sort */
class MergeSort {
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
public int count = 0;
public int count2 = 0;
void merge(int arr[], int l, int m, int r)
{
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
int L[] = new int[n1];
int R[] = new int[n2];
/*Copy data to temp arrays*/
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarray array
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
count++;
count2++;
}
else {
arr[k] = R[j];
j++;
count++;
count2++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
count++;
}
/* Copy remaining elements of R[] if any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
count++;
}
}
// Main function that sorts arr[l..r] using
// merge()
void sort(int arr[], int l, int r)
{
if (l < r) {
// Find the middle point
int m = l + (r - l) / 2;
// Sort first and second halves
sort(arr, l, m);
sort(arr, m + 1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
System.out.println("Number of Comparison " + count);
System.out.println("Number of Swaps " + count2);
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver code
public static void main(String args[])
{
MergeSort ob = new MergeSort();
Random rd = new Random(); // creating Random object
int[] arr = new int[5000];
for (int i = 0; i < arr.length; i++) {
arr[i] = rd.nextInt(10);
}
ob.printArray(arr);
ob.sort(arr, 0, arr.length - 1);
System.out.println("Sorted array");
ob.printArray(arr);
}
}
MergeSort.main(null);
| Number of Data | Time | Number of Comparisons | Number of Swaps |
|---|---|---|---|
| 20 | 0.3 s | 88 | 63 |
| 20 | 0.3 s | 88 | 61 |
| 20 | 0.3 s | 88 | 60 |
| 50 | 0.3 s | 286 | 223 |
| 50 | 0.3 s | 286 | 219 |
| 50 | 0.3 s | 286 | 216 |
| 100 | 0.8 s | 672 | 542 |
| 100 | 0.3 s | 672 | 528 |
| 100 | 0.4 s | 672 | 536 |
| 500 | 1.7 s | 4488 | 3770 |
| 500 | 2.2 s | 4488 | 3770 |
| 500 | 3.5 s | 4488 | 3786 |
| 1000 | 4.8 s | 9976 | 8530 |
| 1000 | 4.5 s | 9976 | 8528 |
| 1000 | 4.1 s | 9976 | 8502 |
| 5000 | 7.9 s | 5560675 | 5560675 |
| 5000 | 8.8 s | 5616655 | 5616655 |
| 5000 | 6.6 s | 5714100 | 5714100 |
Big O Noation:
- used to analyze how efficient an algorithm is from the amount of time, storage, and other resources ittakes to run
- it also takes into account a change in the input size
- it tells us how well an algorithm will perform
- how much time is takes to run is the time complexity
- memory that is uses is the space complexity
- running time does not directly equate to regular time
- time is thought of as the number of operations or steps it takes to complete a problem of size n
- big o tracks how quickly the runtime grows relative to the size of the input ### 0(1) -> Constant time
- This means that it takes a constant time to run the algorithm regardless of the size input
- some ex: math operations, accessing an array via the index, accessing a hash via the key, pushing and popping on a stack, insertion and removal from a queue ### O(n) -> Linear time
- the run time increases at the same pace (linear) as the input
- ex: like reading a book: if it takes 3 minutes to read 3 pages, then it should take 30 minutes to read 30 pages of a book that is the same print and size
- code ex: traversing an array
- loops are generally an indicator that the code has a runtime of O(n) ### O(n^2) -> Quadratic time
- this means that the run time is in quadratic meaning that the squared sum of the input data is propotional to the time
- ex: bubble sort, insertion sort, selection sort
- seeing two neseted loops is generally a good indicator that the code has a runtime of O(n^2)
- ex: n = 4, means that there will be 16 operations total ### O(log n) -> Logarithmic time
- the running time grows in prportion to the logarithm of the input size
- this means that the run time barely increases as you exponentially increase the input
- ex: binary search, very little searching and the time gets cut in half each time ### O(nlog n) -> combination of linear and logarithmic
- ex: merge sort, timsort, heapsort