Implementing Sorting Framework for the Backend

[YLu-1258]

On the subject of Sorting

While starting this project, I realized that many of our sorts shared similar methods to one another for generating the actual animations to be played on the frontend. To do this, I created a public abstract class called SortingAnimationGenerator in order to serve as a baseline blueprint for much of our later sorts. The Lombok library was also used to provide for the constructors, setters, and getters. A snippet of the code is provided below:

@NoArgsConstructor
@AllArgsConstructor
@ToString
@Data
public abstract class SortingAnimationGenerator {
    protected ArrayList<Integer> arr;
    protected int swaps;

    public SortingAnimationGenerator(int length) {
        arr = new ArrayList<Integer>();
        System.out.println("I am ran");
        for (int i = 0; i < length; i++) {
            arr.add(i);
        }
        Collections.shuffle(arr);
    }

    public SortingAnimationGenerator(int length, ArrayList<Integer> array) {
        arr = array;
    }

    public void addAnimationEntry(ArrayList<Integer> sortedArr, int start, int end) {
        HashMap<String, ArrayList<Integer>> animationEntry = new HashMap<>();
        ArrayList<Integer> pair = new ArrayList<>();
        animationEntry.put("arr", new ArrayList<>(arr));
        pair.add(start);
        pair.add(end);
        animationEntry.put("pair", pair);
        animations.add(animationEntry);
        this.swaps++;
    }

    public String toStringArr() {
        int n = this.arr.size();
        String array = "";
        for (int i = 0; i < n; i++) {
             array = array + this.arr.get(i) + " ";
        }
        return array;
    }

}

Challenge with MergeSort

The main challenge with the mergeSort algorithm was that the most popular method of implementation used auxiliary space (extra arrays) to denote each split-up subarray. The challenge with this is that it becomes very hard to visualize the individual swaps occurring as they are essentially happening in separate arrays.

To handle this challenge, I opted to develop an in-place sorting version of mergeSort, so that it is much easier to take a snapshot of the whole array, that encapsulates the subarray that is being merged. This was also evident on our animation in the frontend, as one can see the individual subarrays being sorted.

// Standard Merge Sort algo
    public void mergeSortAnimation(int start, int end) {
        if (start < end) {
            int middle = (start + end) / 2;
            mergeSortAnimation(start, middle);
            mergeSortAnimation(middle + 1, end);
            merge(start, middle, end);
        }
    }

    // Have to adopt an in-place sort here because I'm stupid LMAOOOOOOO
    public void merge(int start, int mid, int end) {
        int start2 = mid + 1;

        // Check if merging is necessary
        if (arr.get(mid) <= arr.get(start2)) {
            return;
        } 

        // Merge the two halves
        while (start <= mid && start2 <= end) {
            addAnimationEntry(arr, start, end);

            if (arr.get(start) <= arr.get(start2)) {
                start++;
            } else {
                int valueToInsert = arr.get(start2);
                int indexToInsert = start2;

                // Shift elements to the right to make space for the new element
                while (indexToInsert != start) {
                    arr.set(indexToInsert, arr.get(indexToInsert - 1));
                    indexToInsert--;
                }

                // Insert the element in its correct position
                arr.set(start, valueToInsert);

                // Update indices
                start++;
                mid++;
                start2++;
            }
        }
    }

Creating the Request Objects

One last thing that I did in the initial phases of backend developing was the creation of certain Java objects to model the frontend request. This is one such example:

@NoArgsConstructor
@AllArgsConstructor
@ToString
@Data
public class MergeRequest {
    private int length;
    private ArrayList<Integer> array;
}

And when implemented, it looks like this:

@PostMapping("/merge")
    public ResponseEntity<ArrayList<HashMap<String, ArrayList<Integer>>>> getMergeAnimations(@RequestBody MergeRequest request) {
        int length = request.getLength();
        ArrayList<Integer> array = request.getArray();
        MergeSort mergeSort = new MergeSort(length, array);
        System.out.println(mergeSort.swaps);
        return new ResponseEntity<>(mergeSort.getAnimations(), HttpStatus.OK);
    }

Frontend sorting animation

Something I did for the frontend was create the asynchronous function that grabs the sorted data and plays the animation. This ensures that our animation only plays after we get the animations from the backend (which takes time), and also allows us to specify an animation speed:

async function sort() {
        toggleSortWorking();
        await getAnimations();
        toggleSortStop();
        for (i = 0; i < animations.length-2; i++) {
            console.log(animations[i]);
            let arr = animations[i].arr;
            let pivotPos = animations[i].values[0];
            let current = animations[i].values[1];
            let pivot = animations[i].values[2];
            setTimeout(function() {

                renderFrame(arr, pivotPos, current, pivot);
            }, i*0.01);
        }
        time = document.getElementById("time-display");
        swaps = document.getElementById("swap-display");
        time.innerHTML = "Time: " + animations[animations.length-1].time + " ns"
        swaps.innerHTML = "Swaps: " + animations[animations.length-2].swaps
        console.log(animations[animations.length-1].time);
        console.log(animations[animations.length-2].swaps);
    }