Algorithm homework

I finally had the time to finish this homework as well.

 

Linear search

LinearSearch(x,items) searches the items for the given item . The algorithm starts at the first position in items and iterates over each item while comparing with x. If the one item equals the item x, the algorithm the position of this item, otherwise -1.

  1. Init index variable to zero(0)
  2. Iterate over items and compare the i-th element of items with x
  3. increase the index variable by one and start over with 2
  4. if the i-th item and x are equal return the i otherwise -1

Heapsort

Heapsort(items) is a function to sort a collection of items by using a tree datastructure. The passed items are transformed in a tree-based datastructure with a defined order. Each tree-node is either smaller or equal to his parent node. Next we create a sorted region by removing the largest element in the tree(the root) and inserting this into a array. By repeating this step the sorted array is created and henceforth the tree is shrinked.

  1. create a binary tree from the given array
  2. iterate over the tree and move the root of the tree to a array, the sorted array
  3. update the remaining tree to create a new tree with the root as the largest element
  4. by repeating step you create a sorted array
  5. as soon as the heap is empty we are finished

SelectionSort

SelectionSort(items) is a in-place sort algorithm, which means the items are not moved to different arrays or other structures. It finds the smallest element in the items collection and swaps it with a specified different element.

  1. finding the smallest element in the array
    1. find minimum from start to end
  2. swap the found element with the first element
  3. find the next smallest element in the array
    1. not all elements has to be concerned because the smallest element is on position 0 already so we can start from 1
  4. swap the second smallest element with the second element
  5. repeat step 3 and 4 until we are at the end of the list

In terms of costs this algorithm has a runtime of O(n*n) which makes it inefficient for large lists.