Sorting and Efficiency

    This week we learned about sorting and efficiency. This involves many different solving algorithms as well as something called "the Big O", which I learned is basically a representation of a methods run time. Since no one computer runs at the same speed and thus will have different run times for the same method, it is important to have a different way to represent how long a function will take to compete its job. This is where Big O comes in. It is away of describing run time using functions.

basic functions of Big O:

    c < lg(n) < n < n^2 < n^3 < 2^n < n! < n^n

    (Note: lg(n) refers to log base 2 of n)

The basic idea is that the further left your representation is, the smaller your run time will be. 

Of all of the sort types that Danny showed us this week I only knew a few. From CSC108 I knew Quick sort. Here is a list of the names of the sorting algorithms and a description of the way they operate:

• Quick sort:
• Idea: choose a pivot; decide where the pivot goes with respect to the rest of the list, repeat on the partitions
• Big O: n^2
• Merge sort:
• idea: divide the list in half, (merge) sort the halves, then merge sort the results.
• Big O: lgn
• Count sort:
• Danny wrote this sort, I'm not sure
• Tim sort:
• This is the sorting algorithm used by python, I don't know how this one works either but its fast.

Out of all these sort types Tim sort was the fasted, then count sort, then merge, then quick.

Sorting is quite relevant to the the specialist I am choosing. I am going in to Geophysics, and writing a sorting algorithm to take data I pull out of the ground with my equipment is essential to being able to interpret it.