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/
No comments:
Post a Comment