CSA

CSA Week 0 Week 1 Week 2 Week 3 Final Week 5 Week 6 Study
Week 7

Week 3 - Ticket

Table of Contents

(TPT) Study Group Challenge 3

Objective 1: Build all of these into your data structures.

Objective 2: Perform analysis on all of these sorts using 5,000 random pieces of data.

Tri 3: Tech Talk 3: Sorts

Objective 1: Perform analysis on all of these sorts using 5,000 random pieces of data.

Objective 2 (optional): Blow me away for auto 100% on all Data Structures work, caveat for calculator.

Additional Resources Used

Challenge #0: Time and Sample Size

SortTester.java

public class SortTester {
    public void tester(ITemplateSort genericSort) {
        TestDataGenerator testDataGenerator = new TestDataGenerator(5000);
        int minimum = 0;
        int maximum = 0;
        int totalTime = 0;

        for (int i = 0; i < 12; i++) {
            int[] testArray = testDataGenerator.getTestData();
            System.out.println("Initial Array: " + Arrays.toString(testArray));

            Instant start = Instant.now();  // time capture -- start
            genericSort.sort(testArray);
            Instant end = Instant.now();    // time capture -- end
            Duration timeElapsed = Duration.between(start, end);

            minimum = Math.min(minimum, timeElapsed.getNano());
            maximum = Math.max(timeElapsed.getNano(), maximum);
            totalTime += timeElapsed.getNano();

            System.out.println("Sorted Array: " + Arrays.toString(testArray));
            System.out.println("Time: " + timeElapsed);
            System.out.println();
        }
        int averageTime = (totalTime - minimum - maximum) / 10;
        double averageTimeInSeconds = averageTime / 1_000_000_000.0;
        System.out.println("Average Time (in seconds): " + averageTimeInSeconds);
    }
}

Getting the time of the sort (directly):

Instant end = Instant.now();
-
Instant start = Instant.now();
=
Duration timeElapsed = Duration.between(start, end);

System.out.println("Time: " + timeElapsed);

Getting the average time of all 12 sorts (excluding minimum and maximum):

minimum = Math.min(minimum, timeElapsed.getNano());
maximum = Math.max(timeElapsed.getNano(), maximum);
totalTime += timeElapsed.getNano();

int averageTime = (totalTime - minimum - maximum) / 10;
double averageTimeInSeconds = averageTime / 1_000_000_000.0;
System.out.println("Average Time (in seconds): " + averageTimeInSeconds);

Sample size of 12 - 2:

for (int i = 0; i < 12; i++) {
}
int averageTime = (totalTime - minimum - maximum) / 10;

5000 random pieces of data:

TestDataGenerator testDataGenerator = new TestDataGenerator(5000);

TestDataGenerator.java

public class TestDataGenerator {
    int size;
    public TestDataGenerator(int size) {
        this.size = size;
    }

    public int[] getTestData() {
        int[] intArray = new int[size];
        for (int i = 0; i < size; i++) {
            // If size is 5000, it chooses a number between 0 and 5000
            intArray[i] = (int)(Math.random() * (size + 1));
        }
        return intArray;
    }
}

Challenge #1: Bubble Sort Objective 1

BubbleSort.java

Code:

// The amount of iterations is equal to the elements in the array, to account for the worst case scenario.
for (int j = 1; j < intArray.length; j++) {
    // The sort itself will check each consecutive element and swap them if they are out of order.
    // This results in the largest value being bubbled to the top.
    // the "- j" prevents the bubble sort from resorting bubbled values.
    for (int i = 0; i < intArray.length - j; i++) {
        if (intArray[i] > intArray[i + 1]) {
            // Swap the two values
            int temp = intArray[i];
            intArray[i] = intArray[i + 1];
            intArray[i + 1] = temp;
        }
    }
}

Challenge #2: Insertion Sort Objective 1

InsertionSort.java - The Prequel

Code:

// My old garbage reverse bubble sort:
for (int i = 1; i < intArray.length; i++) {
    int j = i;
    while (j > 0) {
        if (intArray[j] < intArray[j - 1]) {
            // If the current is less than the value before it, swap 'em.
            int temp = intArray[j];
            intArray[j] = intArray[j - 1];
            intArray[j - 1] = temp;
        }
        j--;
    }
}

InsertionSort.java - The Sequel to the Prequel

Code:

// My actual Insertion Sort, but using swappers
for (int i = 1; i < intArray.length; i++) {
    int j = i;
    while (j > 0 && intArray[j] < intArray[j - 1]) {
        // If the current is less than the value before it, swap 'em.
        int temp = intArray[j];
        intArray[j] = intArray[j - 1];
        intArray[j - 1] = temp;
        j--;
    }
}

InsertionSort.java - Turing Planet

Code:

// Someone else's slightly more efficient code?
for(int i = 1; i < intArray.length; i++) {
    int cur = intArray[i];
    int j = i - 1;
    while(j >= 0 && intArray[j] > cur) {
        intArray[j + 1] = intArray[j];
        j--;
    }
    intArray[j + 1] = cur;
}

InsertionSort.java - FINAL VERSION

Code:

// Woah! Much faster than the code I copied from, after a few modifications! No more swappers too!
for (int i = 1; i < intArray.length; i++) {
    int j = i;
    // "value" holds the current value, we'll hold this value in memory in case we need to move it back.
    int value = intArray[j];
    while (j > 0 && value < intArray[j - 1]) {
        // Move all values up one until we find the place to insert "value".
        intArray[j] = intArray[j - 1];
        j--;
    }
    intArray[j] = value;
}

Challenge #3: Selection Sort Objective 1

SelectionSort.java - FINAL VERSION

Code:

for (int i = 0; i < intArray.length; i++) {
    // "i" controls what has already been sorted.
    int min = intArray[i];
    int minIndex = i;
    // "j = i" prevents the algorithm from sorting what has already been sorted.
    // The "+ 1" is because we don't need to compare the minimum with the minimum again.
    for (int j = i + 1; j < intArray.length; j++) {
        // If the value we get to is less than j, set it as the new minimum.
        if (intArray[j] < min) {
            min = intArray[j];
            minIndex = j;
        }
    }
    // Once we've found the minimum, swap the two values.
    intArray[minIndex] = intArray[i];
    intArray[i] = min;
    // Learning algorithmic strategies from Insertion Sort! Reduce swapping as much as possible!
}

SelectionSort.java - The Sequel

Code:

// I tried getting rid of "min" and replace it with "temp", but...
// Line 36 is slower since I need to find the element of the index again.
for (int i = 0; i < intArray.length; i++) {
    // "i" controls what has already been sorted.
    int minIndex = i;
    // "j = i" prevents the algorithm from sorting what has already been sorted.
    // The "+ 1" is because we don't need to compare the minimum with the minimum again.
    for (int j = i + 1; j < intArray.length; j++) {
        // If the value we get to is less than j, set it as the new minimum.
        if (intArray[j] < intArray[minIndex]) {
            minIndex = j;
        }
    }
    // Once we've found the minimum, swap the two values.
    if (minIndex != i) {
        int temp = intArray[minIndex];
        intArray[minIndex] = intArray[i];
        intArray[i] = temp;
    }
}

Challenge #4: Merge Sort Objective 1

MergeSort.java

Code:

public void sort(int[] intArray) {
    // intArray.length will be called on a lot, so defining it beforehand saves time.
    int intArrayLength = intArray.length;

    // If the length of the array is one... well, start merging. This works because RECURSION.
    if (intArrayLength == 1) {
        return;
    }

    // defining intArrayLength / 2 because that's also used a lot.
    int intArrayMidpoint = intArrayLength / 2;

    // Create the two halves of intArray
    int[] arrayOne = new int[intArrayMidpoint];
    // "intArrayLength -" Deals with odd numbers, since arrayTwo will be larger than arrayOne.
    int[] arrayTwo = new int[intArrayLength - intArrayMidpoint];

    int i = 0, j = 0;
    // For the first half of the array, add to arrayOne.
    while (i < intArrayMidpoint) {
        arrayOne[i] = intArray[i];
        i++;
    }
    // For the second half of the array, add to arrayTwo.
    // Also, reset the pointer for arrayTwo.
    // Keep the pointer for intArray the same.
    while (i < intArrayLength) {
        arrayTwo[j++] = intArray[i++];
    }

    // Start RECURSION
    sort(arrayOne);
    sort(arrayTwo);

    // After RECURSION
    merge(intArray, arrayOne, arrayTwo);
}

private void merge(int[] arrayMerged, int[] arrayOne, int[] arrayTwo) {
    int i = 0, j = 0, k = 0;

    // If both arrays still have elements...
    while (i < arrayOne.length && j < arrayTwo.length) {
        // If arrayOne is less than arrayTwo, add the element of arrayOne.
        if (arrayOne[i] < arrayTwo[j]) {
            arrayMerged[k] = arrayOne[i];
            i++;
        }
        else { // If arrayTwo is less than arrayOne, add the element of arrayTwo.
            arrayMerged[k] = arrayTwo[j];
            j++;
        }
        k++;
    }

    // If arrayOne has run its course...
    if (i == arrayOne.length) {
        // Add the rest of arrayTwo into arrayMerged.
        while (j < arrayTwo.length) {
            arrayMerged[k++] = arrayTwo[j++];
        }
    }
    // If arrayTwo has run its course...
    else {
        // Add the rest of arrayOne into arrayMerged.
        while (i < arrayOne.length) {
            arrayMerged[k++] = arrayOne[i++];
        }
    }
}

Final Judgement: Objective 1

Sorting Algorithm Time (in seconds) Big O Complexity Swaps
Bubble Sort ~0.0460 O(n^2) n^2
Selection Sort ~0.0058 O(n^2) n
Insertion Sort ~0.0042 O(n^2) n
Merge Sort ~0.0010 O(log(n)) 0

Bubble Sort is the slowest, having a O(n^2) complexity AND swapping each element whilst sorting. Selection Sort and Insertion Sort are similar in functionality, just reversed in the direction of sorting. They swap once per nested for loop, making their speed similar. A Merge Sort is the fastest, using recursion to achieve a O(log(n)) complexity and using NO swaps. Compared to the others, it is by far the fastest.

Challenge #0: System works with Queues

SortTester.java

public void queueTester(ITemplateSort genericSort) {
    TestDataGenerator testDataGenerator = new TestDataGenerator(5000);
    int minimum = 0;
    int maximum = 0;
    int totalTime = 0;

    for (int i = 0; i < 12; i++) {
        Queue<Integer> testQueue = testDataGenerator.createQueueTestData();
        System.out.print("Initial Queue ");
        printQueue(testQueue);

        Instant start = Instant.now();  // time capture -- start
        genericSort.sort(testQueue);
        Instant end = Instant.now();    // time capture -- end
        Duration timeElapsed = Duration.between(start, end);

        minimum = Math.min(minimum, timeElapsed.getNano());
        maximum = Math.max(timeElapsed.getNano(), maximum);
        totalTime += timeElapsed.getNano();

        System.out.print("Sorted Queue ");
        printQueue(testQueue);

        System.out.println("Time: " + timeElapsed);
        System.out.println();
    }
    int averageTime = (totalTime - minimum - maximum) / 10;
    double averageTimeInSeconds = averageTime / 1_000_000_000.0;
    System.out.println("Average Time (in seconds): " + averageTimeInSeconds);
}
private void printQueue(Queue<Integer> queue) {
    System.out.print("data: ");
    for (Integer data : queue) {
        System.out.print(data + " ");
    }
    if (queue.getHead() == null) {
        System.out.print("null");
    }
    System.out.println();
}

TestDataGenerator.java

public Queue<Integer> createQueueTestData() {
    Queue<Integer> intQueue = new Queue<>();
    for (int i = 0; i < size; i++) {
        intQueue.add((int)(Math.random() * (size + 1)));
    }
    return intQueue;
}

Challenge #5: Merge Sort Objective 2

MergeSort.java

Code:

@Override
public void sort(Queue<Integer> intQueue) {
    int intQueueLength = intQueue.size;

    if (intQueueLength == 1) {
        return;
    }

    int intQueueMidpoint = intQueueLength / 2;

    Queue<Integer> q1 = new Queue<>();
    Queue<Integer> q2 = new Queue<>();

    int i = 0;
    while (i < intQueueMidpoint) {
        q1.add(intQueue.getHead().getData());
        intQueue.delete();
        i++;
    }
    while (i < intQueueLength) {
        q2.add(intQueue.getHead().getData());
        intQueue.delete();
        i++;
    }

    sort(q1);
    sort(q2);

    mergeQueues(intQueue, q1, q2);
}

private void mergeQueues(Queue<Integer> qMerged, Queue<Integer> q1, Queue<Integer> q2) {
    while (q1.getHead() != null && q2.getHead() != null) {
        // If q1 is less than (or equal to) q2, add the value from q1 into q3.
        // Then delete the head of q1.
        if (q1.getHead().getData() <= q2.getHead().getData()) {
            qMerged.add(q1.getHead().getData());
            q1.delete();
        }
        // Otherwise, add the value from q2 into q3.
        else {
            qMerged.add(q2.getHead().getData());
            q2.delete();
        }
    }

    // If q1 has finished its course, add the remaining values from q2 into q3.
    if (q1.getHead() == null) {
        /*
        while (q2.queue.getHead() != null) {
            q3.queue.add(q2.queue.getHead().getData());
            q2.queue.delete();
        }
        */
        qMerged.getTail().setNextNode(q2.getHead());
    }
    // Else if q2 has finished its course, add the remaining values from q1 into q3.
    else if (q2.getHead() == null) {
        /*
        while (q1.queue.getHead() != null) {
            q3.queue.add(q1.queue.getHead().getData());
            q1.queue.delete();
        }
        */
        qMerged.getTail().setNextNode(q1.getHead());
    }
}

Challenge #6: Bubble Sort Objective 2

BubbleSort.java

Code:

LinkedList<Integer> dummyHead = new LinkedList<>(0, null);
dummyHead.setNextNode(intQueue.head);
LinkedList<Integer> node1, node2;

for (int j = 1; j < intQueue.size; j++) {
    node1 = dummyHead;
    for (int i = 0; i < intQueue.size - j; i++) {
        node1 = node1.getNext();
        node2 = node1.getNext();

        if (node1.getData() > node2.getData()) {
            Integer temp = node1.getData();
            node1.setData(node2.getData());
            node2.setData(temp);
        }
    }
}

Challenge #7: Selection Sort Objective 2

SelectionSort.java

Code:

LinkedList<Integer> dummyHead = new LinkedList<>(0, null);
dummyHead.setNextNode(intQueue.head);
LinkedList<Integer> node1=dummyHead, node2, minTempNode;

for (int i = 0; i < intQueue.size; i++) {
    // "i" controls what has already been sorted.
    node1 = node1.getNext();
    int min = node1.getData();
    int minIndex = i;
    minTempNode = node1;
    // "j = i" prevents the algorithm from sorting what has already been sorted.
    // The "+ 1" is because we don't need to compare the minimum with the minimum again.
    node2 = node1;
    for (int j = i + 1; j < intQueue.size; j++) {
        // If the value we get to is less than j, set it as the new minimum.
        node2 = node2.getNext();
        if (node2.getData() < min) {
            min = node2.getData();
            minTempNode = node2;
        }
    }
    // Once we've found the minimum, swap the two values.
    minTempNode.setData(node1.getData());
    node1.setData(min);
    // Learning algorithmic strategies from Insertion Sort! Reduce swapping as much as possible!
}

Challenge #8: Insertion Sort Objective 2

InsertionSort.java

Code:

LinkedList<Integer> dummyHead = new LinkedList<>(0, null);
dummyHead.setNextNode(intQueue.head);
intQueue.head.setPrevNode(dummyHead);
LinkedList<Integer> node1 = intQueue.head;
LinkedList<Integer> node2;
for (int i = 1; i < intQueue.size; i++) {
    int j = i;
    node1 = node1.getNext();
    // "value" holds the current value, we'll hold this value in memory in case we need to move it back.
    int value = node1.getData();
    node2 = node1.getPrevious();
    while (j > 0 && value < node2.getData()) {
        // Move all values up one until we find the place to insert "value".
        node2.getNext().setData(node2.getData());
        node2 = node2.getPrevious();
        j--;
    }
    node2.getNext().setData(value);
}

Final Judgement: Objective 2

If the Bubble Sort was still O(n^3) with the triple nested for loop, it may have taken ~20-30 minutes to run through 5000 elements!

Sorting Algorithm Queue Time (in seconds) Array Time (in seconds) Big O Complexity Swaps
Bubble Sort ~0.0840 ~0.0460 O(n^2) n^2
Selection Sort ~0.0490 ~0.0058 O(n^2) n
Insertion Sort ~0.0320 ~0.0042 O(n^2) n
Merge Sort ~0.0024 ~0.0010 O(log(n)) 0

Sorting a Queue was slower than sorting the Array, most likely because the Queue is a more complex data structure. The speeds are comparable to the Array, same analysis as Final Judgement: Objective 1.