Ever needed to write a program to alphabetize a telephone
directory, or to arrange library records by catalogue number ? If so, the
problem of arranging the elements of a list in chronological order has
definitely arouse.
As
you can probably tell by the preamble, the topic of interest concerning us this
week pertains to "Sorting and Efficiency." In solving the
above problem, there are many algorithms that can be used to sort a
list including insertion sort, merge sort, quick sort, and selection sort,
just to name a few. Given that these algorithms vary immensely in
efficiency, it is very important that we choose a good algorithm.
For instance, consider the following list: L = [x for x in
range(5000, 0, -1)].
If we want to sort this list (from smallest to largest), we could try to
use merge sort or insertion sort. Although, its quite obvious in this
case, that merge sort severely outperforms insertion sort. In
general, using big-Oh notation, the efficiency of merge sort in the worst
case is given by
O(
n * log2 n ),whereas insertion sort is given by O(n ** 2). So it shouldn't
be surprising that MERGE sort outperforms INSERTION sort for large lists.
Thats
the simple-essence of what I've learned during these past two weeks on sorting
and efficiency. Although, I personally understand the "practical"
benefit of these tools, I sometimes find determining the efficiency of certain
algorithms to be very difficult. Take merge sort for instance.
Initially, I thought since merge sort divides the
list into half, similar to binary search, its performance would
involve log2 n.
However,
I was missing an n factor, and had no idea
where it came from. It took some time before I realized that the n arises from
the possible splits that are done, and the depth of the recursive calls is given by log2 n.
In
fact, determining efficiency was my biggest hurdle on the second term test.
I'll definitely have to find external resources (more practice
examples) to aid me in preparation of the final exam.
No comments:
Post a Comment