Youtube Video

Youtube Video: WW3 Presentation - Racketj Drive Link (if youtube is not done): Drive Link

Contributions

Frontend Commits:

Backend Commits:

Key Commits / Additions

Key Commits

Deploy Backend (Rachit): Commit where everything was finally deployed (just changed the name here)
Fibonacci (finished version, both Binet’s Formula and Matrix Exponentiation): Commit
Basic Sorting (All 4 types–merge, insertion, selection, and bubble): Backend Commit
CORS Support serverwide: Commit 1 Commit 2 - more types of requests Commit 3 - Enable Local

Frontend - Got requests to adhere with proper headers and JSON: Commit 1 (build off other commits) - Finish making and organizing sorts

Commit 2 - Batch Analysis

Commit 3 - Fibonacci Frontend Calls w/ Animation

Key additions

Added everything in a more package-based hierarchal structure (FTC!!!!!)

Inheritance!

SortResult.java

package com.nighthawk.spring_portfolio.mvc.sorting;

import java.util.List;

public class SortResult {
    private String sortType; // Add this field
    private List<Integer> sortedList;
    private long timeTakenMs;
    private int iterations;
    private int comparisons;
    private int swaps;

    public SortResult(String sortType, List<Integer> sortedList, long timeTakenMs, int iterations, int comparisons, int swaps) {
        this.sortType = sortType; // Include this in the constructor
        this.sortedList = sortedList;
        this.timeTakenMs = timeTakenMs;
        this.iterations = iterations;
        this.comparisons = comparisons;
        this.swaps = swaps;
    }

    // Getter for sortType
    public String getSortType() {
        return sortType;
    }

    // Existing getters
    public List<Integer> getSortedList() {
        return sortedList;
    }

    public long getTimeTakenMs() {
        return timeTakenMs;
    }

    // New getters
    public int getIterations() {
        return iterations;
    }

    public int getComparisons() {
        return comparisons;
    }

    public int getSwaps() {
        return swaps;
    }
}

SortingServiceInterface.java

package com.nighthawk.spring_portfolio.mvc.sorting;

import java.util.List;

public interface SortingServiceInterface {
    SortResult sort(List<Integer> input);
}

All other sorting classes extend and go through these files:

public class BubbleSortService implements SortingServiceInterface

Endpoints!

SortingController.java

package com.nighthawk.spring_portfolio.mvc.sorting;

import com.nighthawk.spring_portfolio.mvc.sorting.bubble.BubbleSortService;
import com.nighthawk.spring_portfolio.mvc.sorting.insertion.InsertionSortService;
import com.nighthawk.spring_portfolio.mvc.sorting.merge.MergeSortService;
import com.nighthawk.spring_portfolio.mvc.sorting.selection.SelectionSortService;
import com.nighthawk.spring_portfolio.mvc.sorting.SortingAnalysisService;
import com.nighthawk.spring_portfolio.mvc.sorting.SortResult;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.web.bind.annotation.*;

import java.util.List;

@RestController
@RequestMapping("/api/sorting")
public class SortingController {

    @Autowired
    private BubbleSortService bubbleSortService;

    @Autowired
    private InsertionSortService insertionSortService;

    @Autowired
    private MergeSortService mergeSortService;

    @Autowired
    private SelectionSortService selectionSortService;

    @PostMapping("/bubble") // Change the annotation to @PostMapping
    public SortResult bubbleSort(@RequestBody List<Integer> input) { // Use @RequestBody to receive the input data
        return bubbleSortService.sort(input);
    }

    @PostMapping("/insertion") // Change the annotation to @PostMapping
    public SortResult insertionSort(@RequestBody List<Integer> input) { // Use @RequestBody to receive the input data
        return insertionSortService.sort(input);
    }

    @PostMapping("/merge") // Change the annotation to @PostMapping
    public SortResult mergeSort(@RequestBody List<Integer> input) { // Use @RequestBody to receive the input data
        return mergeSortService.sort(input);
    }

    @PostMapping("/selection") // Change the annotation to @PostMapping
    public SortResult selectionSort(@RequestBody List<Integer> input) { // Use @RequestBody to receive the input data
        return selectionSortService.sort(input);
    }

    @Autowired
    private SortingAnalysisService sortingAnalysisService;

    @PostMapping("/analyze") // Change the annotation to @PostMapping
    public List<SortResult> analyzeSorts(@RequestBody List<Integer> input) { // Use @RequestBody to receive the input data
        return sortingAnalysisService.analyzeSorts(input);
    }
}

FibonacciController.java

package com.nighthawk.spring_portfolio.mvc.fibonacci;

import com.nighthawk.spring_portfolio.mvc.fibonacci.binets.BinetService;
import com.nighthawk.spring_portfolio.mvc.fibonacci.matrix.MatrixFibonacciService;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.web.bind.annotation.*;

@RestController
@RequestMapping("/api/fibonacci")
public class FibonacciController {

    @Autowired
    private BinetService binetService; // Can go until 92 (java)

    @Autowired
    private MatrixFibonacciService matrixFibonacciService; // Cannot go above 46 (some matrix thing)

    // Autowire other services

    @GetMapping("/{method}/{n}")
    public Object calculateFibonacci(@PathVariable String method, @PathVariable int n) {
        switch (method.toLowerCase()) {
            case "binet":
                return binetService.calculate(n);
            case "matrix":
                return matrixFibonacciService.calculate(n);
            // Add more cases for other methods here
            default:
                throw new IllegalArgumentException("Invalid Fibonacci calculation method: " + method);
        }
    }
}

Logic

Sorting: Bubble

package com.nighthawk.spring_portfolio.mvc.sorting.bubble;

import org.springframework.stereotype.Service;
import com.nighthawk.spring_portfolio.mvc.sorting.SortResult;
import com.nighthawk.spring_portfolio.mvc.sorting.SortingServiceInterface;


import java.util.ArrayList;
import java.util.List;

@Service
public class BubbleSortService implements SortingServiceInterface {

    public SortResult sort(List<Integer> input) {
        long startTime = System.nanoTime(); // Start timing

        List<Integer> arr = new ArrayList<>(input);
        int n = arr.size();
        int iterations = 0;
        int comparisons = 0;
        int swaps = 0;

        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-i-1; j++) {
                comparisons++; // Increment comparison count
                if (arr.get(j) > arr.get(j+1)) {
                    // swap arr[j+1] and arr[j]
                    int temp = arr.get(j);
                    arr.set(j, arr.get(j+1));
                    arr.set(j+1, temp);
                    swaps++; // Increment swap count
                }
            }
            iterations++; // Increment iteration count
        }

        long endTime = System.nanoTime(); // End timing
        long duration = (endTime - startTime) / 1000000; // Convert nanoseconds to milliseconds

        return new SortResult("Bubble", arr, duration, iterations, comparisons, swaps);
    }
}

Sorting: Insertion

package com.nighthawk.spring_portfolio.mvc.sorting.insertion;

import org.springframework.stereotype.Service;
import com.nighthawk.spring_portfolio.mvc.sorting.SortResult;
import com.nighthawk.spring_portfolio.mvc.sorting.SortingServiceInterface;


import java.util.ArrayList;
import java.util.List;

@Service
public class InsertionSortService implements SortingServiceInterface {

    public SortResult sort(List<Integer> input) {
        long startTime = System.nanoTime();

        List<Integer> arr = new ArrayList<>(input);
        int n = arr.size();
        int iterations = 0;
        int comparisons = 0;
        int swaps = 0;

        for (int i = 1; i < n; ++i) {
            int key = arr.get(i);
            int j = i - 1;

            while (j >= 0 && arr.get(j) > key) {
                comparisons++; // Increment comparison count
                arr.set(j + 1, arr.get(j));
                j = j - 1;
                swaps++; // Increment swap count
            }
            arr.set(j + 1, key);
            iterations++; // Increment iteration count
        }

        long endTime = System.nanoTime();
        long duration = (endTime - startTime) / 1000000;

        return new SortResult("Insertion", arr, duration, iterations, comparisons, swaps);
    }
}

Sorting: Merge

package com.nighthawk.spring_portfolio.mvc.sorting.merge;

import org.springframework.stereotype.Service;
import com.nighthawk.spring_portfolio.mvc.sorting.SortResult;
import com.nighthawk.spring_portfolio.mvc.sorting.SortingServiceInterface;


import java.util.ArrayList;
import java.util.List;

@Service
public class MergeSortService implements SortingServiceInterface {

    private int comparisons = 0;
    private int merges = 0;

    public SortResult sort(List<Integer> input) {
        long startTime = System.nanoTime();

        List<Integer> arr = new ArrayList<>(input);
        mergeSort(arr, 0, arr.size() - 1);

        long endTime = System.nanoTime();
        long duration = (endTime - startTime) / 1000000;

        return new SortResult("Merge", arr, duration, 0, comparisons, merges);
    }

    private void merge(List<Integer> 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 */
        List<Integer> L = new ArrayList<>(n1);
        List<Integer> R = new ArrayList<>(n2);

        /* Copy data to temp arrays */
        for (int i = 0; i < n1; ++i)
            L.add(i, arr.get(l + i));
        for (int j = 0; j < n2; ++j)
            R.add(j, arr.get(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) {
            comparisons++;  // Increment comparison count
            if (L.get(i) <= R.get(j)) {
                arr.set(k, L.get(i));
                i++;
            } else {
                arr.set(k, R.get(j));
                j++;
            }
            merges++;  // Increment merge count
            k++;
        }

        /* Copy remaining elements of L[] if any */
        while (i < n1) {
            arr.set(k, L.get(i));
            i++;
            k++;
            merges++;  // Increment merge count for remaining elements of L[]
        }

        /* Copy remaining elements of R[] if any */
        while (j < n2) {
            arr.set(k, R.get(j));
            j++;
            k++;
            merges++;  // Increment merge count for remaining elements of R[]
        }
    }


    // Main function that sorts arr[l..r] using merge()
    private void mergeSort(List<Integer> arr, int l, int r) {
        if (l < r) {
            // Find the middle point
            int m = (l + r) / 2;

            // Sort first and second halves
            mergeSort(arr, l, m);
            mergeSort(arr, m + 1, r);

            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }
}

Sorting: Selection

package com.nighthawk.spring_portfolio.mvc.sorting.selection;

import org.springframework.stereotype.Service;
import com.nighthawk.spring_portfolio.mvc.sorting.SortResult;
import com.nighthawk.spring_portfolio.mvc.sorting.SortingServiceInterface;

import java.util.ArrayList;
import java.util.List;

@Service
public class SelectionSortService implements SortingServiceInterface {

    public SortResult sort(List<Integer> input) {
        long startTime = System.nanoTime();

        List<Integer> arr = new ArrayList<>(input);
        int n = arr.size();
        int iterations = 0;
        int comparisons = 0;
        int swaps = 0;

        for (int i = 0; i < n-1; i++) {
            int min_idx = i;
            for (int j = i+1; j < n; j++) {
                comparisons++; // Increment comparison count
                if (arr.get(j) < arr.get(min_idx)) {
                    min_idx = j;
                }
            }

            // Swap
            int temp = arr.get(min_idx);
            arr.set(min_idx, arr.get(i));
            arr.set(i, temp);
            swaps++; // Increment swap count

            iterations++; // Increment iteration count
        }

        long endTime = System.nanoTime();
        long duration = (endTime - startTime) / 1000000;

        return new SortResult("Selection", arr, duration, iterations, comparisons, swaps);
    }
}

Sorting: Batch Analysis

package com.nighthawk.spring_portfolio.mvc.sorting;

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Service;

import com.nighthawk.spring_portfolio.mvc.sorting.bubble.BubbleSortService;
import com.nighthawk.spring_portfolio.mvc.sorting.insertion.InsertionSortService;
import com.nighthawk.spring_portfolio.mvc.sorting.merge.MergeSortService;
import com.nighthawk.spring_portfolio.mvc.sorting.selection.SelectionSortService;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

@Service
public class SortingAnalysisService {

    @Autowired
    private BubbleSortService bubbleSortService;

    @Autowired
    private InsertionSortService insertionSortService;

    @Autowired
    private MergeSortService mergeSortService;

    @Autowired
    private SelectionSortService selectionSortService;

    private static final int NUM_TESTS = 12;

    public List<SortResult> analyzeSorts(List<Integer> inputList) {
        List<SortResult> results = new ArrayList<>();

        results.add(analyzeSort("Bubble", bubbleSortService, inputList));
        results.add(analyzeSort("Insertion", insertionSortService, inputList));
        results.add(analyzeSort("Merge", mergeSortService, inputList));
        results.add(analyzeSort("Selection", selectionSortService, inputList));

        return results;
    }

    private SortResult analyzeSort(String sortType, SortingServiceInterface sortService, List<Integer> inputList) {
        List<Long> times = new ArrayList<>();
        List<Integer> comparisons = new ArrayList<>();
        List<Integer> swaps = new ArrayList<>();
        List<Integer> representativeSortedList = null;

        for (int i = 0; i < NUM_TESTS; i++) {
            // Clone the input list to avoid modifying the original list
            List<Integer> testData = new ArrayList<>(inputList);
            SortResult result = sortService.sort(testData);

            times.add(result.getTimeTakenMs());
            comparisons.add(result.getComparisons());
            swaps.add(result.getSwaps());

            if (i == 0) {
                representativeSortedList = result.getSortedList();
            }
        }

        Collections.sort(times);
        Collections.sort(comparisons);
        Collections.sort(swaps);

        // Remove the highest and lowest values
        times.remove(0);
        times.remove(times.size() - 1);
        comparisons.remove(0);
        comparisons.remove(comparisons.size() - 1);
        swaps.remove(0);
        swaps.remove(swaps.size() - 1);

        // Calculate averages
        long avgTime = times.stream().mapToLong(Long::longValue).sum() / times.size();
        int avgComparisons = comparisons.stream().mapToInt(Integer::intValue).sum() / comparisons.size();
        int avgSwaps = swaps.stream().mapToInt(Integer::intValue).sum() / swaps.size();

        // Return a new SortResult with averages and the sort type
        return new SortResult(sortType, representativeSortedList, avgTime, 0, avgComparisons, avgSwaps);
    }
}

Fibonacci: Binet’s Formula

package com.nighthawk.spring_portfolio.mvc.fibonacci.binets;

import org.springframework.stereotype.Service;

@Service
public class BinetService {

    public FibonacciResult calculate(int n) {
        long startTime = System.nanoTime();

        double phi = (1 + Math.sqrt(5)) / 2;
        int fibonacci = (int) Math.round(Math.pow(phi, n) / Math.sqrt(5));

        long endTime = System.nanoTime();
        long duration = (endTime - startTime) / 1000000; // Convert to milliseconds

        return new FibonacciResult(fibonacci, duration);
    }

    public static class FibonacciResult {
        private final int fibonacciNumber;
        private final long timeTakenMs;

        public FibonacciResult(int fibonacciNumber, long timeTakenMs) {
            this.fibonacciNumber = fibonacciNumber;
            this.timeTakenMs = timeTakenMs;
        }

        public int getFibonacciNumber() {
            return fibonacciNumber;
        }

        public long getTimeTakenMs() {
            return timeTakenMs;
        }
    }
}

Fibonacci: Matrix Exponentiation

This service is breaking jekyll right now. This will be fixed soon!

Outputs:

Fibonacci goes directly to animation… thats why it is not on the frontend and instead on postman.

Sorting *Times get bigger for bigger lists (1k):

WW3 Individual Review • 27 min read

Description