2.3 Algorithms

avatar
Created by
Daniel Lievesley

Subdecks (1)

Cards (15)

  • Bubble sort
    Bubble sort makes comparisons and swaps between pairs of elements. The largest element in the unsorted part of the input is said to “bubble” to the top of the data with each iteration of the algorithm.
  • function bubbleSort(){
      let go = true
      while(go){
        go = false
        for (let i=0; i<len; i++){
          moves = 0
          if (array[i] > array[i+1]){
            temp = array[i]
            array[i]=array[i+1]
            array[i+1] = temp
            moves += 1
            go = true
            if (i===len){
              if (moves === 0){
                go = false
              }
            }
          }
        }
        }
      return array
      }
  • Insertion sort
    Insertion sort places elements into a sorted sequence. In the ith iteration of the algorithm the first i elements of the array are sorted. Be careful - although i elements are sorted, they are not the i smallest elements in the input.
    1. Sort starts at the second element in the input and compares it to its left. 
    2. The third element in the input is then selected and inserted into the correct position. If it isn’t it will carry on moving to the left until it is sorted. 
    3. This continues until the last element is inserted into the correct position.
  • Insertion sort:
    for (i=1; i < a.length; i++){
    elem = A[i]
    j=i-1
    while (j > 0 && A[j] > elem){
    A[j+1] = A[j]
    j = j-1
    }
    A[j+1] = elem
    }
  • Linear search
    • Linear search is a method to search for a particular item in a list.
    • Items do not need to be in order.
    • However, it can be highly inefficient as the more terms there are the more comparisons that will need to be made.
    1. The sought for item will be compared to the first term, if it is found the algorithm will return true.
    2. This repeats with every term until the last one, which if it is not found it will return false.
  • Linear:
    function exists(fruit){
    for (i=0; i<list.length-1; i++){
    if (list[i].toLowerCase() === fruit.toLowerCase()){
    return true
    }
    }
    return false
    }
  • Binary search
    The algorithm searches for a specified value by comparing it to a midpoint and repeating the process until the midpoint is the value sought for
  • Binary search
    • It is a highly efficient algorithm as it disregards half of the scale each time that isn't necessary, lowering the range
    • All items need to be in order
  • Binary search
    1. Find the midpoint (ub+lb)/2
    2. Compare the value to the midpoint
    3. If value is greater, move lower bound to midpoint + 1
    4. If value is lower, move upper bound to midpoint-1 and readjust midpoint
    5. Repeat until midpoint is the value sought for, returning true
    6. If value not found and no more values, return false
  • Binary search is a highly efficient algorithm as it disregards half of the scale each time that isn't necessary, lowering the range
  • All items need to be in order for binary search to work
  • Binary search:
    function binarySearch(item){
    let lb = 0
    let ub= fruit.length-1
    while (ub>=lb){
    let mp = Math.floor((ub+lb)/2)
    if (fruit[mp] === item){
    return true
    }
    else if (fruit[mp]>item){
    ub=mp-1
    }
    else if (fruit[mp]<item){
    lb=mp+1
    }
    }
    return false
    }