Algorithm descriptions

LinearSearch(v,l) searches the items in list l for the value v. It returns the position of the value or n if the is not in the list, where n is the length of l. The value is compared to every element in the list, denoted by l(i).

  1. (Initialize counter i.) Set i <- 0.
  2. (loop trough every item in l.)
    1. if l(i) = v return i.
    2. i <- i+1.
  3. return n.

InsertionSort(l) sorts the list l and returns it. It loops through each element of the list, finds its location in the sorted list, and inserts it there. The sorted list consists of every visited item.

  1. (Initialize counter i.) Set i <- 1.
  2. (Sort the list.) Loop trough every item in l.
    1. (Initialize counter j.)j is used to search for the correct position to insert l(i). Set j <- i.
    2.  While j is still a valid index ( j > 0 ) and the predecessor of l(j) is greater than l(j) ( l(j-1) > l(j) ).
      1. Swap l(j) and l(j-1).
      2. j <- j-1.
  3. return l.

MergeSort(l) sorts the list l with a divide-and-conquer approach. That means the data is broken down into parts which are processed individually. After that, the preprocessed parts are merged back together again. Overall, the algorithm has a complexity of O(n log n).

Input: unsorted list l.

Output: sorted list l.

 

The major steps of the algorithm are as follows:

  1. Recursive subdivision of the list until each contains 1 item.
  2. Merge sublists until only one is remaining. This is the sorted list.

We now examine these steps in detail.

  1. (Subdivision.)
    1. If a list is empty or has only one element is sorted by definition. In this case, return l.
    2. left, right <- split(l).
      1. This evenly divides all items of l into left and right. This has a constant complexity, since only the midpoint of l needs to be computed.
    3. left <- MergeSort(left)
    4. right <- MergeSort(right)
      1. Recursive calls are used to further subdivide the sublists. This is done until there is until the whole list is divided into sublists of length one. These sublists are then sorted in the Merge function. This has a complexity of  logarithmic since the inputs for the recursive calls are halved at each recursion step.
    5. return Merge(left,right)

function Merge(left, right)

This help function called by the MergeSort function actually does the sorting. The merge has a linear complexity, because each element of the input lists is merged into the result list exactly once.

  1. result <- empty_list.
  2. If none of both lists is empty merge both lists using a zip lock principle. Both left and right are sorted meaning the first element of both is the smallest item in each list. To merge the sublists, the first elements of both sublists are compared and the smaller one is appended to result.
    1. if head(left) <= head(right) then
      1. result <- result + head(left)
      2. left <- tail(left)
    2. else
      1. result <- result + head(right)
      2. right <- tail(right)
    3. head(list) return the first element of list and tail(list) returns every element of list except the first one.
    4. If one of the sublists has any elements has any elements left simply append these elements to result.
    5. return result. This is a sorted list.

Leave a Reply

Your email address will not be published. Required fields are marked *