The concept of
putting things in an order has been established within our minds since we were
very young. Maybe we'd arrange our toys according to which one is our
favourite, putting them at the top of our toy box. We learned that sorting and
ordering things simply made our lives easier, like having easier access to our
favourite toys, since they were at the top of our toy box, and we would not
have to dig around for them.
Bubble sort,
Insertion sort, and Selection sort were introduced to us in CSC108, and it was
interesting to see how they worked in terms of sorting lists, and making our
lives much easier. I don't suppose we spoke much of the rate at which they were
better than each other, but we just accepted the fact that a certain option was
better than another in certain instances, and that Bubble sort was never really
a good option.
In CSC148, we were
introduced to more sorting methods, namely Merge sort, Quick sort, and Tim sort
(a hybrid sort, created in 2002, and now used as Python's built-in sorting
method). Merge sort and Quick sort are pretty similar to each other, and Tim
sort is a mix of both Merge sort and Insertion sort. Not only did we learn
about how they worked, but we also learned about their efficiency.
When we talk of Big
O, we refer to the run time of the worst case of a function, or in other words,
its efficiency. When determining the worst case, there are various factors
involved, such as the length of the list, or how sorted it is. Knowing of these
factors helps us in figuring out the worst case of a function.
Since I'm not
currently enrolled in CSC165, I had to teach myself about the concept of Big O,
(for the most part). It took me a while to understand at first, but after a
thinking of the efficiency of a few functions, the reasoning clicked and made
it much easier and faster to figure out the answer.
For Term Test #2, I
looked back on the Sample Test for Term Test #1, since it had a question on Big
O. It was in chart form, and those were questions I was completely comfortable
with. I had sheer confidence in my skills of determining efficiency. However,
when it came to writing Term Test #2, I was not prepared in the slightest for
the Big O question. It was a very worrying experience, because it took a while
to go through the functions and then explain the reasoning without sounding
like I was making it up.
I'm still trying to
get better at learning about Big O, and this week's SLOG helped me out a bit,
in terms of making me research different sorting methods, and figuring out
which ones are better than others in specific cases. I especially liked the
interactive displays of some sorting methods, because you could step through
the process, and you could see the sorting methods working under different
conditions.
Specifically, this
is the link I liked the most:
No comments:
Post a Comment