\title{Exercise Sheet 9}\author{Andrei Pöhlmann\\ \small{1319194}}

\section{Exercise 1 - Bubble Sort} \begin{tasks} \task Starting from the beginning of the list, compare every adjacent pair, swap their position if they are not in the right order (= the latter one is smaller than the former one). After each iteration, one less element (the last one) is needed to be compared until there are no more elements left to be compared. \task \begin{enumerate} \item swap 22 and 15 $\rightarrow$ [15,22,36,20,3,9,29] \item move on and compare next adjacent pair: 22, 36 $\rightarrow$ ok \item move on and compare next adjacent pair: swap 36 and 20 $\rightarrow$ [15,22,20,36,3,9,29] \item move on and compare next adjacent pair: swap 3 and 36 $\rightarrow$ [15,22,20,3,36,9,29] \item move on and compare next adjacent pair: swap 36 and 9 $\rightarrow$ [15,22,20,3,9,36,29] \item move on and compare next adjacent pair: swap 36 and 29 $\rightarrow$ [15,22,20,3,9,29,36] \item start all over again \item {[15,22,20,3,9,29,36] $\rightarrow$ [15,22,3,20,9,29,36]} \item {[15,22,3,20,9,29,36] $\rightarrow$ [15,22,3,9,20,29,36]} \item start all over again \item {[15,22,3,9,20,29,36] $\rightarrow$ [15,3,22,9,20,29,36]} \item {[15,3,9,22,20,29,36] $\rightarrow$ [15,3,9,20,22,29,36]} \item start all over again \item {[15,3,9,22,20,29,36] $\rightarrow$ [3,15,9,20,22,29,36]} \item {[3,15,9,20,22,29,36] $\rightarrow$ [3,9,15,20,22,29,36]} \end{enumerate} \task see pseudo code below \task It's a stable algorithm. Since there is no way that 2 equal adjacent numbers could be swapped, so the order of records with equal keys is preserved. \end{tasks} 
#### Pseudo code
bubblesort <- function(list){
  n = length(list)
  swapped <- TRUE
  while(swapped){
    # In case there was no swap during the for loop
    # it means the list is sorted => end of while-loop.
    # Therefor set swapped to FALSE right at the beginning
    swapped <- FALSE
    # 1st array index in R is 1, not 0 as usual. 
    # Last index = n, not n-1 as usual.
    for(i in 1:n-1){
      if(list[i] > list[i+1]){
        swap(list[i], list[i-1])
        swappped <- TRUE
      } # end if
    } # end for and decrement n 
    n <- n - 1
  } # end while
} # end function
\section{Exercise 2 - Merge Sort}\begin{tasks} \task First divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally all the elements are sorted and merged. \task Sort the array [5, 2, 4, 1, 7, 8, 3, 2] using Merge Sort. \begin{enumerate} \item split into subcomponents \item {[5, 2, 4, 1, 7, 8, 3, 2] $\rightarrow$ [5,2,4,1] and [7,8,3,2]} \item $\rightarrow$ {[5, 2], [4, 1], [7, 8], [3, 2]} \item $\rightarrow$ {5 2 4 1 7 8 3 2} \item sort and merge adjacent elements/lists: \item $\rightarrow$ {[2,5], [1,4], [7,8], [2,3]} \item $\rightarrow$ {[1,2,4,5], [2, 3, 7, 8]} \item $\rightarrow$ {[1,2,2,3,4,5,7,8]} \end{enumerate} \task see below \task see below \task Use Mergesort to sort the k elements $\rightarrow \mathcal{O}(k\cdot log(k))$. Finally find the position where the new sorted array K has to be inserted within the sorted array N $\rightarrow \mathcal{O}(n)$ $\rightarrow$ in total: $\mathcal{O}(k\cdot log(k) + n)$ \end{tasks} 
## c) merge function

merge <- function(a,b){
  # create an empty array of length(a) + length(b)
  c <- rep(NA, length(a)+length(b))
  # start constructing c 
  while(a && b){
      # if a[0] is larger than b[0] append b[0] to c
      # else append a[0]
      # use pop function to shrink the according array
      if(a[0] > b[0]){
        c <- pop(b[0])
      }
      else{
        c <- pop(a[0])
      }
  } # end while loop
  # Now we need to check the cases where either A or B still contain elements. 
  # For example consider two arrays A = [5,6,7] and B = [1,2,999]
  # After the while-loop A,B & C look like: C = [1,2,5,6,7], A = [], B = [999]
  if(b)
    append(c,b) 
  else if(a)
    append(c,a)
  return(c)
} 

## d) merge_sort

merge_sort <- function(x) { 
  if (length(x)<2)
    return(x)
  else{
    mid <- ceiling(length(x)/2)
    # sort the two halves of list x recursively with mergesort and merge them
    merge(merge_sort(x[1:mid]),merge_sort(x[-c(1:mid)]))
  }
}