Hacks

CB wants you to work with Bubble Sort, Selection Sort, Insertion Sort and Merge Sort. The material on these sorts is prevelant on the Internet and ChatGPT.

Build into this Jupyter Notebook(s) for Bubble Sort, Selection Sort, Insertion Sort and Merge Sort.
Build into this Jupyter Notebooks Tester methods that runs each Sort
Commit to GitHub Repository often, try to use GitHub commits to show iterations on work
Note, build your sorts into Generic T Queue using toString and compareTo to compare keys.

Methods we used:

Print array - .toString()

int[] myArray = {1,2,3,4,5};

for (int i = 0; i < myArray.length; i++){
    System.out.print(Arrays.toString(myArray));
}

compareTo()

The compareTo() method is a method provided by the Java programming language that is used to compare two objects(wrapper class, include Integer, String, etc...).
if it is a String object - compare alphabetically, return 0 if String is equal to its String input and return a value greater 0 if String is greater than the String it compare to, and return a value less than 0 if String is less than the String it compare to.
ex. guess1.compareTo(guess2)>0, if String guess1 is greater than guess2

Build into this Jupyter Notebook(s) for Bubble Sort, Selection Sort, Insertion Sort and Merge Sort.

Bubble Sort

All that happens is that adjacent partners swap if they are in the wrong slot until the algorithm is complete. Notice they have to do a final pass before they can decide that it really is "all sorted".

public class BubbleSort{  
    static void bubbleSort(int[] arr) {   
        int temp = 0;  
        for(int i=0; i < arr.length; i++){  
            for(int j=1; j < (arr.length-i); j++){  
                if(arr[j-1] > arr[j]){   
                    temp = arr[j-1];  
                    arr[j-1] = arr[j];  
                    arr[j] = temp;  
                }  
            }  
        }  
  
    }  
    public static void main(String[] args) {  
        int arr[] ={1,5,4,3,2};         
        bubbleSort(arr); 
        for(int i=0; i < arr.length; i++){  
                System.out.print(arr[i] + " ");  
            }
        }  
}  
BubbleSort.main(null);

1 2 3 4 5

Selection Sort

Selection sort is a linear sort algorithm as it moves from index [0] to [n-1]. In the inner loop which is a second linear loop it compares two elements (like seen in the visual below) and notes which is smallest, after cycling to the end it swaps the smallest number to beginning position in the round.

private void swapItems(int firstIndex, int secondIndex, Object[] arrayOfStuff){
    Object thirdHand = arrayOfStuff[firstIndex];
    arrayOfStuff[firstIndex] = arrayOfStuff[secondIndex];
    arrayOfStuff[secondIndex] = thirdHand;
}

Integer[] Array = {1,5,4,3,2};

for (int outerLoop = 0; outerLoop < Array.length; outerLoop++){
    int minIndex = outerLoop;
    for (int inner = outerLoop +1; inner < Array.length; inner++){
        if (Array[inner].compareTo(Array[minIndex]) < 0){
            minIndex = inner;
        }
    }

    if (minIndex != outerLoop){
        swapItems(minIndex, outerLoop, Array);
    }
}

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

1 2 3 4 5

Insertion Sort

The insertion sort is characterized by building a sorted structure as it proceeds. It inserts each value it finds at the appropriate location in the data structure. This is often accomplished by using a while loop as the inner loop.

ArrayList<Integer> tester = new ArrayList<Integer>();
tester.add(1);
tester.add(5);
tester.add(4);
tester.add(3);
tester.add(2);

for (int outerLoop = 1; outerLoop < tester.size(); outerLoop++){
    Integer tested = tester.get(outerLoop);
    int inner = outerLoop -1 ;
    while (inner >= 0 && tested.compareTo(tester.get(inner)) < 0){
        tester.set(inner + 1, tester.get(inner));
        inner--;
    }
    tester.set(inner + 1, tested);
}

for (int i = 0; i < tester.size(); i++){
    System.out.print(tester.get(i) + " ");
}

1 2 3 4 5

Merge Sort

This algorithm uses a divide and conquer algorithm, versus linear algorithm of insertion or selection sort. Looking at it can be complicated, but it is more simple than it looks. It divides the array into two different groups recursively, until it gets only two to compare, swaps if necessary. Then it pops out of the recursion, observe the cascading and then the inverted assembly in illustration, after pop it puts each split group back together using a sorted comparison.

public static void merge(int[] a, int[] l, int[] r, int left, int right) {
 
    int i = 0, j = 0, k = 0;
    while (i < left && j < right) {
        if (l[i] <= r[j]) {
            a[k++] = l[i++];
        }
        else {
            a[k++] = r[j++];
        }
    }
    while (i < left) {
        a[k++] = l[i++];
    }
    while (j < right) {
        a[k++] = r[j++];
    }
}

public static void mergeSort(int[]myArray, int index){
        if (index < 2){
            return;
        }
    
        int middle = (index)/2;
        int[] leftArray = new int[middle];
        int[] rightArray = new int[index - middle];
    
        for (int i = 0; i < middle; i++) {
            leftArray[i] = myArray[i];
        }
        for (int i = middle; i < index; i++) {
            rightArray[i - middle] = myArray[i];
        }
        mergeSort(leftArray, middle);
        mergeSort(rightArray, index - middle);
        merge(myArray, leftArray, rightArray, middle, index-middle);
}

int[] tester = { 1,5,4,3,2 };
mergeSort(tester, tester.length);
for (int i = 0; i < tester.length; i++){
    System.out.print(tester[i] + " ");
}

1 2 3 4 5