Blogs, Mathematical Reasoning, MR Study Help

A Sorting Algorithm

We have seen in Writing and performing algorithms and The Division Algorithm a description of different algorithms and the importance they can play. Here, we will focus on working through a specific example of writing an algorithm. In particular, we will describe how to numerically sort a given set of numbers. Note that we will be using the algorithm notation used in Hammock’s Elements of Discrete Mathematics.

The Goal

Before we start writing an algorithm, we want to determine what the actual goal will be. In this case, we will be assuming that the person performing the algorithm will be given a set of numbers. Then, that person will need to rearrange the set so that the numbers are listed from smallest to largest.

Now, if you ask most people to sort the numbers in order, they would likely be able to do that. As we are writing this algorithm, however, we don’t want to assume that this is possible. Instead, we will work under the assumption that the person doing the algorithm can compare two numbers at a time, but not more than two. However, we will assume that the person does know what each of the given numbers is and the total numbers that are passed to them.

For example, if you were given the set \(\left\{1,3,1,2,8,10,-2,\dfrac{3}{4},25\right\}\), we would assume that you could see that there are 9 numbers being passed to you and that you could compare them pairwise.

Then, we need to make sure that the list you will write is, \(\left\{-2,\frac{3}{4},1,1,2,3,8,10,25\right\}\).

Input

This first thing we need to deal with is how to begin to process the input that is given to us. We will need some way to talk about the input, so we will need have variables used for the input. Here we will assume that the input is given to us in the following way.

Input: \(A=\left\{a_{1},a_{2}, \ldots, a_{n}\right\}\)

The input will give us a set, with an initial ordering. Furthermore, since the elements are labeled \(a_{1}, a_{2}, \ldots, a_{n}\), the number of elements, or the cardinality of the set will be \(n\).

Comparing

Now we know that the input is denoted given to us as elements \(a_{i}\) for \(1 \leq i \leq n\), we need to find some way to compare these. Because we will be trying to give the final answer as the elements in ascending order, we will first need to compare two at a time using \(

As we continue to compare, we also want some way to keep track of the results we end up with. The easiest way to do this is to define new variables so that we can input the values that we want to eventually output. We will, therefore, define the set \(B=\left\{b_{1},b_{2}, \ldots b_{n}\right\}\) as the output set.

Smallest Number

Now that we know where we will put our answers, we will begin by finding the smallest number. We had decided above that we can’t just say, “find the smallest number.” Instead we will have to look at these at most two numbers at a time. In so doing, we need somewhere to start, so we will assign the value of \(a_{1}\) to \(b_{1}\) since this is the first number we will run into. Therefore, we set \[b_{1}:=a_{1}.\]

\(a_{1}\) may be the smallest number, but it won’t be the smallest in general, so we will need to continue to compare as we go. In this way, we should check, is \(a_{2} < a_{1}\). If it is, we will say that \(a_{2}\) is the smallest thus far. Otherwise, the smallest so far is still \(a_{1}\). In order to run this in our algorithm, we will check

\begin{align*}
&\textbf{If } (a_{2} < a_{1}) \\
&| &&b_{1}:=a_{2} \\
&\textbf{Else} \\
&| &&b_{1}:=a_{1} \\
&\textbf{End}
\end{align*}

Next Comparison

We note here that the else part is unnecessary, since \(b_{1}\) was already set to \(a_{1}\). Therefore, we may as well leave this part out of our algorithm.

Now that we’ve compared the first two, we will now need to compare the first 3. Since we already know which is the smallest of the first two, we can compare the third to the smallest to determine if it is the new smallest or not. That is, if \(a_{3} < b_{1}\) (the current smallest) then we assign \(b_{1}\) the value of \(a_{3}\) because it will be the smallest of the three. We now perform the operation

\begin{align*}
&\textbf{If } (a_{3} < b_{1}) \\
&|&& b_{1}:=a_{3}\\
& \textbf{End}
\end{align*}

In this case we left the else off since we don’t change anything if the if part is false. We should also note that for the first comparison we compared \(a_{2}\) to \(a_{1}\) and in the second case we compared to \(b_{1}\). However, since \(b_{1}=a_{1}\) in the first case, we may as well have used \(b_{1}\) in the first case.

Finishing the Smallest Value

Looking at the process for \(a_{3}\), we note that we will need to run this comparison again and again for each of the \(a_{i}\). Instead of writing this process out, we instead want to use a loop. Since we start the comparison with \(a_{2}\) and end with \(a_{n}\), we will have

\begin{align*}
&\textbf{For } (i=2 \text{ to } n) \\
&|&&\textbf{If } (a_{i} < b_{1}) \\
&|&&|&& b_{1}=a_{i} \\
&|&& \textbf{End} \\
& \textbf{End}
\end{align*}

Combining this together, we will get

\begin{align*}
& b_{1}:=a_{1} \\
&\textbf{For } (i=2 \text{ to } n) \\
&| && \textbf{If } (a_{i} < b_{1}) \\
&| && | && b_{1}:=a_{i} \\
& | && \textbf{End} \\
& \textbf{end}
\end{align*}

Next Value

Now that we have our smallest value, we need to find the second smallest value. We first note that, we can do a similar process to above, but if we don’t change \(A\), we will just get the same number as before. Therefore, we will like to remove the smallest number from \(A\) before running the process again. We can imagine something like, assign to \(A\) the set \(A\) without the value we assigned as \(b_{1}\), then find the smallest element in this set. This may look like

\begin{align*}
&\textbf{For } (i=1 \text{ to } n) \\
& | && \textbf{If } (a_{i}=b_{1}) \\
& | && | && A:=A-\left\{a_{i}\right\}.\\
& | && \textbf{End} \\
& \textbf{End}
\end{align*}

However, we would note that using this set up, we would run into difficulty when we had multiple of the same values. In our example, we have multiple \(1\)s. Therefore, if this was the smallest value, all of these would be removed by the above process. Therefore, we need some way to ensure we are only removing one of the elements of \(A\).

Removing an Element

There are different ways we might do this. One way is to state that, if we remove an element, then we stop the loop and move on. However, I feel a more intuitive way to explain this is just to say, get rid of the one you used. In order to do this, however, we will need to know which \(a_{i}\) we used. Therefore, we will need to adjust our previous algorithm to do this for us. Here, we will let \(r\) be the index of the used element, and we can write

\begin{align*}
&b_{1}:=a_{1} \\
&r:=1 \\
&\textbf{For } (i=2 \text{ to } n) \\
& | && \textbf{If } (a_{i} < b_{1}) \\
&| && |&& b_{1}:=a_{i} \\
&| && |&& r:=i \\
&| && \textbf{End}\\
&\textbf{End}
\end{align*}

Now, \(r\) will be updated when we use a term, so \(a_{r}\) will be the last term that was assigned to \(b_{1}\). We can then say

\begin{align*}
A:=A- \left\{a_{r}\right\},
\end{align*}

and we will have removed only one element from the set.

Finding Second Smallest

Now, to find the second smallest, since we have already found the smallest and removed it from the set, we need only find the smallest of the new set. That this we will first run the smallest procedure,

\begin{align*}
& b_{1}:=a_{1} \\
& r:=1 \\
& \textbf{For } (i=2 \text{ to } n) \\
& | && \textbf{If } (a_{i} < b_{1}) \\
& | && | && b_{1}:=a_{i} \\
& | && | && r:=i \\
& | && \text{End} \\
& \text{End} \\
& A:=A-\left\{a_{r}\right\}
\end{align*}

We then run the procedure again for the new set \(A\), except we will call this \(b_{2}\) instead of \(b_{1}\). This will look like

\begin{align*}
& b_{2}:=a_{1} \\
& r:=1 \\
& \textbf{For } (i=2 \text{ to } n) \\
& | && \textbf{If } (a_{i} < b_{1}) \\
& | && | && b_{2}:=a_{i} \\
& | && | && r:=i \\
& | && \text{End} \\
& \text{End} \\
& A:=A-\left\{a_{r}\right\}
\end{align*}

Note that in the second run, while we use \(A\) and \(n\), \(A\) will have the previous smallest removed for this iteration and \(n\) would be the original \(n-1\) since \(n\) would be dependent on the size of the input set. Since we will be doing this process repeatedly, it is worth defining this as its own procedure. That is, we will define the procedure to find the smallest and remove it from the set as

\begin{align*}
&\text{smallest}(A) \\
& s:=a_{1} \\
& r:=1 \\
& m:=|A| \\
&\textbf{For } (i=2 \text{ to } m) \\
& | && \textbf{If } (a_{i} < s) \\
& | && | && s:=a_{i} \\
& | && | && r:=i \\
& | && \textbf{End} \\
& \textbf{End} \\
& A:=A-\left\{a_{r}\right\}
\end{align*}

Note that we’ve explicitly defined \(m\) as the cardinality of the set \(A\) which is passed into the procedure. Since the cardinality will change, this will help to let the person running the algorithm that this is occurring so they do not confuse the current cardinality with the cardinality of the original set \(A\).

Sorting All Elements

Now we are set up to finish. Notice that we remove 1 element each time we find the smallest. If we want to find the next smallest element, we just need to run this procedure on the resulting set. We then continue this until we have sorted all elements. What this would look like is

\begin{align*}
&\textbf{For } (i=1 \text{ to } n) \\
& | && b_{i}:=smallest(A) \\
& \textbf{End} \\
& B:=\left\{b_{1},b_{2}, \ldots b_{n}\right\} \\
& \textbf{Output} B
\end{align*}

Entire Algorithm

If we put this together we get the following.

Procedure: smallest(A)
Input: A set \(A=\left\{a_{1}, a_{2}, \ldots a_{m}\right\}\)
Output: The smallest element of \(A\) and the set found by removing the smallest element from \(A\).
\begin{align*}
& \textbf{begin}\\
&| && s:=a_{1} \\
&| && r:=1 \\
&| && m:=|A| \\
&| && \textbf{For } (i=2 \textbf{ to } m) \\
&| && | && \textbf{If } (a_{i} < s) \\
&| && | && | && s:=a_{i} \\
&| && | && | && r:=i \\
&| && | && \textbf{End} \\
&| && \textbf{End} \\
&| && A:=A-\left\{a_{r}\right\} \\
& | && \textbf{Output } s \\
&| && \textbf{Output } A \\
& \textbf{End}
\end{align*}

Algorithm: Sorted List
Input: A list \(A=\left\{a_{1}, a_{2}, \ldots, a_{n}\right\}\)
Output: A list \(B=\left\{b_{1},b_{2}, \ldots, b_{n}\right\}\) which is in ascending numerical order.
\begin{align*}
& \textbf{begin} \\
&| && n:=|A| \\
&| && \textbf{For } (i=1 \text{ to } n)\\
&| && | && b_{i}:=smallest(A) \\
&| && \textbf{End} \\
& | && B:=\left\{b_{1},b_{2}, \ldots, b_{n} \right\} \\
& | && \textbf{Output } B \\
&\textbf{End}
\end{align*}

Conclusion

We note here that this is not the only way to sort a list into ascending order. We even pointed out some options along the way. Furthermore, our algorithm is meant for a person that would understand the notation we are using. If you were, for example, to write this for a computer, you would need to use the appropriate language and notation that the computer would understand. This may even include extra steps such as counting the elements in the set to get the cardinality instead of assuming the person would be able to find this. Hopefully, this illustrates a process which could be used to describe how to sort a list one step at a time.

If you found this helpful, please like the post and share it with others that will find it useful.

We'd love to hear your thoughts!

This site uses Akismet to reduce spam. Learn how your comment data is processed.