Sorting and Practicality

Sorting, and the practicality of such algorithms is a significant area of study in computer science. How do we sort large amounts of data in a reasonable amount of time? Attempts to answer this question have resulted in numerous algorithms being created, and perhaps the most popular 3 that are taught in lower level courses are Selection Sort, Quicksort and Merge Sort

Selection sort is the simplest of the trio. It is an in-place sort and takes the minimum element of the unsorted list, and adds it in place in the sorted list. It is simple, yet slow for larger lists, having O(n²) time complexity. This may not seem slow, however when working with thousands of items this can take minutes to sort the list, as compared to seconds with quicksort or even merge sort. I personally havent found much use for this particular algorithm as it still performs worse than insertion sort when used on its optimal input (smaller lists).



Quicksort is the next simplest. It works recursively, taking whats known as a pivot element, and sorting items to the left and right of it depending on if they are less than or greater than the pivot. Its' average case complexity is O(nlogn) however there are cases where it can perform as O(n²). Overall I find quicksort to be the simplest, and the most useful of the sorting algorithms taught, however it too is outperformed by other algorithms.



Merge Sort is the final one we were fully taught. Like Quicksort, it is recursive and is a divide and conquer algorithm. It works by dividing the list continually into halves until the list is one element long, at which point it is sorted by default and is then merged together with the other halves. Like Quicksort, mergesort is also O(nlogn).



I feel it is worth noting that there is no single best sorting algorithm. All sorts are data dependent and context dependent. For small enough lists, selection and insertion sort can outperform the recursive algorithms like quicksort and mergesort. Also worth noting, time efficiency does not mean space efficiency. In situations where memory space is limited, some algorithms which may be faster in an academic environment lose their usefulness.

O, Omega, and Theta

Ever had that one program that takes absolutely forever to execute? Ever wondered if you can safely get a cup of coffee while you wait for it to finish, or if you can go sleep for a few hours and come back?

We finally have an answer to these pressing questions. I introduce to you, Big O, Big Θ and Big Ω. These three notations provide us with a good estimate of how slow (or fast!) our programs will run given a large enough input in the worst case.

Big O is used to describe an upper bound on the runtime. This can be extremely useful depending on how fast your runtime grows with the input. If you have a program that runs in O(n!) time for example, you're going to want to leave your program running overnight, possibly for days.

When I ran bogosort during Lab 8 it took 35 minutes to sort a 10 item list. Big O can help prevent that awkward situation where you want to leave it running, but you also want to be there to see it finish and you're not sure how long it will take.



Visually, and mathematically Big-O provides us with an upper bound by giving us a function, that when multiplied by a constant will bound the runtime from above, or inuitively, our runtime will grow no faster than g(n).

The other two boundaries can be even more useful than Big-O. Big Ω provides us with a lower bound on runtime. Rather than giving us a general idea on the maximum amount of time it will take, Big-Ω instead tells us a lower bound. Given an input of size n, some constant times g(n) will make it grow no faster than our runtime.


Finally, Big Θ provides us with perhaps the most useful boundary on the runtime. This tells us that the runtime of our algorithm grows in the same way as some function g(n), essentially bounding it from above and below.



These three notations are an incredibly useful tool under the right circumstances and are no doubt something every programmer should learn at some point. No matter how slow or fast your program is, its still nice to know whether it will finish in the blink of an eye, or whether it will finish long after the heat death of the universe.

A2 and the wider world (Part II)

The other connection between A2 and the larger concepts of computer science is found in a different, and perhaps better way of handling the matching of regexes.

If you've looked far enough ahead into computer science you will undoubtedly uncover a field known as automata theory. I won't go into too much detail on this, however we do cover it in later year courses. Essentially it is the study of what are called automata, or abstract machines. Having an understanding of automata and how they work provides a very nice solution to A2.

Regexes themselves are what are known as finite state machines. As they read in the input values, they will take on a certain state, and depending on what the input was and what the transition behaviour of the machine is, it will then proceed to another state.

Within the scope of A2 heres how it works:



We begin in our initial state, and look to the first edge for the initial character.

If that character is an a, we can move on to our accepting state then check the rest. if the next character is a b, we move into an intermediate state, then back to the accepting state if the following character is a c.

If any of these conditions fail we move into the rejecting state, and for our purposes return False.

In pseudocode:

state = initial
if state == initial:
    if s[0] != 'a':
        return false # rejecting state
    elif s[0] == 'a':
        state = final
if state == final:
    if s[i] == 'b':
        state = inter
    if i == len(s) -1:
         return True
if state == inter:
    if s[i] == 'c':
         state = final
    else:
         return False

As I said before, everything eventually ties together. A2 more so than most.