ex-bubblesort.tex

\begin{Exercise}[title={Bubble sort},difficulty=1]
\label{ex:bubble}
\Question\label{ex:bubble q1} Write a function that performs 
a bubble sort on a slice of ints. From \cite{bubblesort}:
\begin{quote}
It works by repeatedly stepping through the list to be sorted, comparing each
pair of adjacent items and swapping them if they are in the wrong order. The
pass through the list is repeated until no swaps are needed, which indicates
that the list is sorted. The algorithm gets its name from the way smaller
elements ``bubble'' to the top of the list. 
\end{quote}

\cite{bubblesort} also gives an example in pseudo code:
\begin{lstlisting}[language=pascal]
procedure bubbleSort( A : list of sortable items )
  do
    swapped = false
    for each i in 1 to length(A) - 1 inclusive do:
      if A[i-1] > A[i] then
        swap( A[i-1], A[i] )
        swapped = true
      end if
    end for
  while swapped
end procedure
\end{lstlisting}
\end{Exercise}

\begin{Answer}
\Question 
Bubble sort isn't terribly efficient, for $n$ elements it scales
$O(n^2)$. See QuickSort \cite{quicksort} for a better sorting algorithm.

But bubble sort is easy to implement:
\lstinputlisting[caption=Bubble sort,linerange=4-19]{ex-functions/src/bubblesort.go}

Because a slice is a reference type the \func{bubblesort} function works and
does not need to return a sorted slice.
\end{Answer}