Day 18-19. First A Whisper, then the RUSH

Phew! Another day I've forgotten to put down my progress. Haven't been up to too much, so I don't think much is lost on Day 18, but the combination of the two days has been quite the pickle.

The assignment since yesterday was from the Programming I class, and is thus confidential in terms of information (sorry folks) except for the lightest of info. What I can tell is the sort I managed out, the QuickSort.

QuickSort works with partitioning groups around a pivot. Pick a pivot (I chose the rightmost one) and put all values greater than it past and all values less before it. Afterwards, rinse and repeat on recursively smaller groups. How then, do we do this in 68K? Pointers. By setting a left and right pointer as boundary for the beginning, we can find a value greater on the left and lesser on the right (or same, if there is no larger value) and swap them. At that point we can check if the pointers have crossed, that is right < left. In that case, we can repeat the process below and above the pivot (taking into account its new location), and if left is still lesser than right, we still have a partition we can shrink inwards and still pivot.

Rinse and repeat on smaller portions (make sure to push values on the stack so we can use them later, and use bsr for recursive calls to the same function) and the process is fully sorted. Lo and behold:

THIS IMPORTANT PIECE OF ART is just a display of the solution, starting near the right at 10BC, or where it starts saying "33 45". Sorting per two-byte group (short, or word) starting at 10CC, or "24 44", is the properly sorted version. This keeps the original data intact while perfectly sorting the copy.

This was previously attempted on BubbleSort; however, the amount of time (measured in cycles) required to pull that one off was ten times as much as QuickSort. So far, we have an ideal sort for the upcoming assignment.