Selection sort algorithm
To execute selection sort, we firstly need
to look for smallest item in the list and switch with the current index that we
stand on. We read over the index from 0 to length of list – 1. We call the
initial state of list is unsorted list that contains no sorted part. While
processing the sort, the list becomes sorted from the first to the end. Here,
the sorted part is at the index less than the current index, and the unsorted
part is at the index greater or equal to the current index. Whenever we find
the smallest value from the unsorted part, we switch that smallest value with
the current value.
Quick sort algorithm
Firstly, we let item at index 0 in a given
list be pivot, and look for items less than pivot and put them before the
pivot, and also look for items greater or equal to pivot and put them after the
pivot. Once we do this step, list is slightly sorted but not perfectly, so we
separate it into two parts (one is left side of pivot and the other is right
side). Then, we use recursion to repeat these steps for left and right. After
finishing all recursion, the list must be sorted.
Merge sort algorithm
We continuously split the given list into
left and right where one refers to first half of list and the other has last
half until the list becomes length of one. Of course, these repeating steps should
be done by recursion. Then when left and right reach the length of one, we
start to compare these two to sort. For comparison, starting from index 0 of
left and also index 0 of right, we append one of left item and right item to
the new list, and when once we append the item, we need to increase the value
of index of left or right that currently we read over. For example, if we
append the item at index 0 from left to the new list, we increase the index of
left by 1, but index of right must stay at index 0 since item at index 0 has
not been appended yet. Then, when one of index of left and right becomes length
of the corresponding list, we stop comparing and then append all item that is
left over in left and right. These steps are all done by recursion, and after
it totally ends, list is finally sorted.
Efficiency
In python, one of possible cases to code in
efficient way is memoization. In the lecture, it is introduced by Fibonacci
number. There is a nested function which has the outer function and the inner
function, and the inner function is used in the outer function. When we execute
the recursion in the inner function and also record the data of value came from
any calculations done during recursion running, we no more need to repeat the
calculations that we have done before since we already recorded that
calculation in the dictionary. It means that we can simply recall the result of
calculation from dictionary by giving the keys. This kind of work decreases
running time since there is no repetition anymore.
No comments:
Post a Comment