Jump to content
Mapa

Contemporary Education in Action

Recommended Posts

Back in August, I needed an extra class to complete my schedule. I figured, then, since I like programming and am already pretty familiar with Java, that I should take AP Computer Science online! I get to have a bit of fun writing some programs on the side and get grades for them! 

Sounds fun, right?

Not even close.

For a recent assignment, I had to use merge sort to sort a list of movies by title, year, and studio, in both ascending and descending order. Looking at this, then, I decided that it would benefit me to rub a couple brain cells together and write one method to handle all of the cases, rather than writing the same god damn thing six different times to achieve essentially the same result. Of course, the actual implementation of the sorting algorithm would be basically the same, so my teacher shouldn't have any issue assessing my understanding of how the sorting algorithm works. Here is the result:

    /**
     * Sorts a list using merge sort with a comparator based on a key extraction function
     * @param ts List to sort
     * @param key Key extraction function
     * @param descending Whether or not to sort in descending order
     * @param <T> Type of list to sort
     * @param <U> Type of the key to be extracted -- must be Comparable
     * @return The sorted list
     */
    public static <T, U extends Comparable<? super U>>
    T[] mergeSort(T[] ts, Function<? super T, ? extends U> key, boolean descending) {
        Comparator<T> comp = Comparator.comparing(key);
        return mergeSort(ts,
                descending ? comp.reversed()
                           : comp
                );
    }

    /**
     * Merge sort with custom comparator
     * @param ts The list to sort
     * @param comp Comparator to sort with
     * @param <T> Type of the list to be sorted
     * @return The sorted (modified) list
     */
    public static <T> T[] mergeSort(T[] ts, Comparator<? super T> comp) {
        return mergeSort(ts, comp, 0, ts.length - 1);
    }

    /**
     * Merge sort with custom comparator (recursive call)
     * @param ts List to sort
     * @param comp Comparator to sort with
     * @param low The low index of the section of the list to merge sort
     * @param <T> Type of list that is sorted
     * @return A new (i.e. separate reference) sorted list
     */
    public static <T> T[] mergeSort(T[] ts, Comparator<? super T> comp, int low, int high) {
        if(low == high) return ts;
        int mid = (high + low) / 2;

        mergeSort(ts, comp, low, mid);
        mergeSort(ts, comp, mid+1, high);
        merge(ts, comp, low, mid, high);

        return ts;
    }

    /**
     * Merges two sections of a list together in order base on a comparator
     * @param ts The list to merge
     * @param comp The comparator to use while merging
     * @param low The lower bound of the section to merge
     * @param mid The end of the lower section -- used to divide the list into two sections to merge
     * @param high The high end of the higher section
     * @param <T> Type of the list to merge
     */
    public static <T> void merge(T[] ts, Comparator<? super T> comp, int low, int mid, int high) {
        T[] temp = Arrays.copyOf(ts, high - low + 1);

        int l = low;
        int r = mid+1;
        int n = 0;

        while(l <= mid || r <= high) {
            if(l > mid) {
                temp[n] = ts[r];
                r++;
            } else if(r > high) {
                temp[n] = ts[l];
                l++;
            } else if(comp.compare(ts[l], ts[r]) > 0) {
                temp[n] = ts[r];
                r++;
            } else {
                temp[n] = ts[l];
                l++;
            }
            n++;
        }

        System.arraycopy(temp, 0, ts, low, high-low+1);
    }

Seems like a bit much for a relatively simple task, but here's the code that demonstrates the algorithm:

        System.out.println("Unsorted");
        printMovies(movies);

        System.out.println("Title, Ascending");
        printMovies(mergeSort(movies, Movie::getTitle, false));
        System.out.println("Title, Descending");
        printMovies(mergeSort(movies, Movie::getTitle, true));

        System.out.println("Year, Ascending");
        printMovies(mergeSort(movies, Movie::getYear, false));
        System.out.println("Year, Descending");
        printMovies(mergeSort(movies, Movie::getYear, true));

        System.out.println("Studio, Ascending");
        printMovies(mergeSort(movies, Movie::getStudio, false));
        System.out.println("Studio, Descending");
        printMovies(mergeSort(movies, Movie::getStudio, true));

The very essence of Don't Repeat Yourself philosophy. Hell, you can practically read it like it's English! Dr K's going to be thrilled to mark such beautiful code!

The verdict?

Quote

 

20% F
Nice algorithm. However, you need to use the standard algorithms. 

 

I don't really have to explain much for you to understand why that's completely ridiculous. The algorithm is actually nearly identical to the one taught in the lessons, except that the comparisons of elements use a generic comparator rather than using their specific comparators explicitly, so there's no doubt I've, in essence, successfully implemented merge sort as he wanted it. Now I have to go back and murder my program so I can move on in the course, because of course he's going to hold the exam passwords hostage until I "fix" my program, even though my grade is still an A by a pretty decent margin.

Oh yeah, and he told me the same thing for two other assignments I completed implementing search algorithms.

Contemporary education in action, folks. Being punished for being creative going above and beyond. What a waste of time.

  • Like 2

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...