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):