diff options
Diffstat (limited to 'notes/algorithms.tex')
| -rw-r--r-- | notes/algorithms.tex | 79 |
1 files changed, 57 insertions, 22 deletions
diff --git a/notes/algorithms.tex b/notes/algorithms.tex index c745b72..4801766 100644 --- a/notes/algorithms.tex +++ b/notes/algorithms.tex @@ -22,15 +22,12 @@ an algorithm is. This might be in how quickly an algorithm can be computationally run, or how much memory is used in running the algorithm. ---best and worst case - \section{Searches} -Let us say that we have a list of numbers $n$ where $n = -\{2,6,4,7,8,3,9,0\}$ Let us now consider algorithms to `search' for a -value in the list $n$. - ---key +Let us say that we have a list of numbers $n$ where \[n = +\{2,6,4,7,8,3,9,0\}\] Let us now consider algorithms to `search' for a +value in the list $n$. We can call this value the `key' in our search +$k$. \subsection{Linear search} @@ -56,35 +53,73 @@ would immediately find it. \subsection{Binary search} Consider searching for an item if the list is already sorted, so $n$ -would become $\{0,2,3,4,6,7,8,9\}$. Now if we wanted to search for an -item we could think of it in a way different from linear search. -Let us say we are looking for the value $6$. One way to do this is to -start in the middle, at the value $4$, and comparing it to $6$. $4 < -6$, so because are list is already sorted, we can discard all the +would become \[\{0,2,3,4,6,7,8,9\}\] We can now search in a different +way. Let us say the value we are looking for ($k$) is $6$. We could +start in the middle, at the value $4$, and comparing it to $6$. \[4 < +6\] so because are list is already sorted, we can discard all the numbers left of and including $4$, knowing that we are not discarding -$6$, so our list becomes $\{6,7,8,9\}$. Let us do the same again, -picking the middle value $7$ and comparing it to $6$. $7 > 6$, so we +$6$, so our list becomes \[\{6,7,8,9\}\] Let us do the same again, +picking the middle value $7$ and comparing it to $6$. \[7 > 6\] so we can discard everything right of and including $7$, knowing that $6$ will not be discarded, as the list is sorted. Thus our list becomes -$\{6\}$. Let us pick the middle value $6$ and compare it to $6$. $6 = -6$, thus we have found the element. If there were no more elements +\[\{6\}\] Let us pick the middle value $6$ and compare it to $6$. \[6 += 6\] thus we have found the element. If there were no more elements left and we had not found our key, then we would know it is not in the -list. - ---unclear +list. This is \textit{binary search}. The major drawback to binary search is that the list must be sorted for the sort to work. However, once the list is sorted, it is -significantly faster (less time complex) then linear search, as each -time the search is performed, half of the list is `discarded', so far -fewer comparisons will be made. +significantly faster (less time complex) then linear search, as for each +comparison, half of the list is `discarded', so far fewer comparisons +will be made. \section{Sorts} +For binary search and for many other reasons we may have a list of +values that we want to sort. Let us once again say that we have a list +of numbers $n$ where \[n = \{2,6,4,7,8,3,9,0\}\] + \subsection{Bubble sort} +Bubble sort involves running through the list and comparing each +element to the element after it. If they are out of order, they are +swapped and we keep going through the list. If we pass through the +entire list without making any swaps, then the list is sorted. For +example, in $n$, we would start with $2$ and compare it to $6$. These +are in order, so we move to $6$ and compare it to $4$. These are out +of order so we would swap them. Here are some but not all steps on the +original list $n$ + +\begin{align*} + &n = \{2,6,4,7,8,3,9,0\} \mbox{ comparing 2 and 6} \\ + &n = \{2,4,6,7,8,3,9,0\} \mbox{ comparing 6 and 4, \textit{swap}} \\ + &n = \{2,4,6,7,8,3,9,0\} \mbox{ comparing 6 and 7} \\ + &n = \{2,4,6,7,8,3,9,0\} \mbox{ comparing 7 and 8} \\ + &n = \{2,4,6,7,3,8,9,0\} \mbox{ comparing 8 and 3, \textit{swap}} \\ + &... +\end{align*} + \subsection{Merge sort} +Merge sort begins by splitting a list into sublists, each containing +only one element. These lists are then merged until they again form +one big list. The merging process begins by running through two lists +at the same time and adding the smaller value to the output. For +example, let us say we want to merge the lists \[\{1,3,5\}\] and +\[\{2,4,6\}\] Then we would start at the beginning of each list and +sequentially add the smaller value between the lists to the output + +\begin{align*} + list\ 1 &&list\ 2 &&output\ list\\ + \{1,3,5\}&&\{2,4,6\}&&\{\} &&\mbox{}\\ + \{3,5\} &&\{2,4,6\}&&\{1\} &&\mbox{Comparing 1 and 2, we start with 1}\\ + \{3,5\} &&\{4,6\} &&\{1,2\} &&\mbox{Comparing 3 and 2, we add 2}\\ + \{5\} &&\{4,6\} &&\{1,2,3\} &&\mbox{Comparing 3 and 4, we add 3}\\ + \{5\} &&\{6\} &&\{1,2,3,4\}&&\mbox{Comparing 5 and 4, we add 4}\\ + \{\} &&\{6\} &&\{1,2,3,4,5\}&&\mbox{Comparing 5 and 6, we add 5}\\ + \{\} &&\{\} &&\{1,2,3,4,5,6\}&&\mbox{Comparing nothing and 6, we add 6}\\ +\end{align*} + \section{Programming languages} Programming languages are useful to humans in writing algorithms for |