Week #7
Topic: Sorting algorithm complexity, big-Oh
Something
really useful about this week was that we were presented with the different
inferences that we are allowed to use when trying to prove conjectures.
Existential instantiation was one of those inferences that did not make sense
to me, but now I understand that what we are doing is a replacement of
variables. Basically, we do not use the main variable during the process, just
in our conclusion. I thought of this specific inference as not useful, but
rather fancy; however, I realized that it adds a sense of order to our proof.
Speaking of
order, sorting algorithms was another topic that caught my attention this week.
There is a considerable number of algorithms and it seems to me that we should
focus our attention in the most efficient ones. Thus, I surfed the Internet and
found out that Merge sort, Heapsort and Quicksort are considered the most
efficient algorithms.
The
following video gives us a sense of how different, different sorting algorithms
can be. https://www.youtube.com/watch?v=kPRA0W1kECg
And this
video talks about Tim sort, which is the sorting algorithm used in python.
When
looking at these videos it came to my attention the term binary search threes,
and I found a very useful article that includes the history of these threes and
how to make them more efficient. You can find them through the U of T library
website by searching for efficient algorithms. This link gives you direct
access:
http://getit.library.utoronto.ca/index.php/access?http://myaccess.library.utoronto.ca/login?url=http://books.scholarsportal.info/viewdoc.html?id=/ebooks/ebooks0/springer/2010-04-28/1/9783642034565
Videos:
Videos:
Algorithms
Tim Sort
No comments:
Post a Comment