Week 11: Sorting and Efficiency

Sorting a list or array of items is a common problem in the world of computer science and can be solved in various different ways. Each method of sorting a list has its advantages and disadvantages, as well as efficiency. Quick and merge sort were two algorithms we looked at last week (see my last post for more detail), both of which used recursion and both which had a worst-case runtime of O(n log n) (given that quicksort is modified, otherwise the worst-case runtime is O(n^2)). Merge sort recursively splits the list into sublists and then merges them to produce a final sorted list. Quicksort chooses a pivot (any item in the list, it could be random) and moves the items to the left (items less than the pivot) and right (items greater than the pivot) sublists and then recursively repeats the process. The reason why recursion has been stressed so frequently in this course is becoming more clear; recursive sorts and searches have a better runtime than other sorts. Bubble (compares each item to the next), insertion (inserts items into a sorted sublist) and selection (selects the largest element and moves it to the end) sorts all have runtimes of O(n^2) because of the repeated passes on the list, and hence, are not as efficient. Sorting is an important and common issue in computer science, so making these algorithms

run as fast as possible is important.

Timsort is the sorting algorithm built into Python. It is meant to perform quickly and with various sizes of data. This sort has elements of both merge and insertion sorts. The worst-case runtime is O(n). The implementation is fairly advanced; it uses insertion sort on (relatively) small sublists, which are already ordered, and merges the rest of the data. The procedure is adaptive and depends on the size of the list, so the way this sort orders data varies for different lists.

Parenthetically, the term test this week was much more difficult than the first. I've also noticed that the labs gave gotten more intense over the last few weeks.

xkcd's explanation of terrible sorts. Panicsort resembles my style of coding.

https://xkcd.com/1185/

Week 10: More Sorting and Runtime

This week we looked at more efficient sorting algorithms. As I suspected, faster sorting methods do make use of recursion. The two algorithms that we examined were quicksort and merge sort. Quicksort lives up to its name; it is very fast and takes roughly O(n log n) times on average, much better than O(n²) (for selection sort). The worst case is O(n²), but this case is rare. The algorithm works by first choosing a pivot (it's easiest to choose the first item in the list, but to avoid the worst case runtime as much as possible, we modified it to take a random number in the list). The list is then rearranged so that the elements are either greater than or less than/equal than the pivot element. The two sublists are then recursively sorted in the same manner.

Merge sort is another sorting method which I have seen before, but not using recursion. It also has a runtime of O(n log n). It works by splitting the list into two parts (more or less of equal size, depending on if the number of elements is odd or even), and recursively sort each of these sublists, and merge the two results.

This week we also talked about ways to approach the second assignment. I think I've more or less have my code working. I didn't fully agree with the class design that was given to us, I feel that the way I did it was simpler (if I did it right). But I digress.

Explanation of quicksort. 
http://www.nczonline.net/blog/wp-content/uploads/2012/11/quicksort_21.png

Week 9: Runtime Analysis

This week we mainly focused on algorithm runtime analysis, which is an estimated amount of “steps” (lines of code) which an algorithm takes to complete a task. This analysis is not specific to any programming language, and an algorithm can be mathematically proven to be O(x) (where O means big O and x is some function or a constant). This provides an upper-bound (ie. worst-case runtime) on an algorithm or function. For example, the binary search tree example we went over in class had an approximate runtime of O(log n) (instead of n, so it was faster). The reason that we have been focusing on linked and recursive structures (such as binary search trees) is that they often can reduce runtime and are more efficient.

We also went over the selection and insertion sorts and analyzed their upper-bounds. These sorts are not very efficient, and I have a feeling that recursion will be a key element in other, more efficient sorting algorithms. I already took CSC165 as well as CSC108, so most of what we did in class this week was review for me. I started the second part of the second assignment, as well as finished the third exercise this week. 

 

Some sort of runtime analysis for a merge sort algorithm. 

(http://i.stack.imgur.com/j1mZV.png)

Week 8: More Linked Structures

This week we went over more linked structures (and hence, more opportunities to use recursion), specifically linked lists and binary trees. These ADTs made sense to me, and were somewhat similar to regular trees. The idea of wrapper classes and the difference between __str__ and __repr__ methods was also discussed. A linked list has a node (with a value) which points to another object (another linked list, until the end, where the value is None), and we made a wrapper class to keep track of the size and the front of the list. As seen in last weeks lab, adopting these ADTs and wrapper classes can be used to cut down on runtime and make programs more organized.

A binary tree (and the binary search tree wrapper class) is a tree with only two children, so the children are represented as left and right. In this instance, a __str__ method that is different from __repr__ is useful for the programmer to visualize the structure. I think I'll do a similar thing for the second part of the second assignment. A traversal was used for the _str method, and recursion for the _insert method. Binary trees are another way which runtime can be reduced.

I was pleased with my result on the term test, and I finished and understand the first part of the assignment. I've already done some code for the next part.

A graphic of a linked list

http://www.cs.usfca.edu/~srollins/courses/cs112-f07/web/notes/linkedlists/ll2.gif