Searching and sorting algorithms

• What is a linear search?

  A search which checks the first item, then the second and continuing. It will only stop if the item we're looking for is found or if it gets to the end of the data set.
• Advantages of a linear search:

  • Very easy to implement
• Disadvantages of a linear search:

  • Slow on a long list
• What is a binary search?

  • Select middle number (or left/right of middle as even number)
  • Check if selected number matches target number
  • if searched number is larger, discard left half
  • if searched number is smaller, discard right half
  • Repeat until number found or or remaining list is of size 1 / 0- number not found
• Advantages of a binary search:

  • Faster than linear search on a large dataset
• Disadvantages of a binary search:

  • Dataset must be sorted before starting
• Binary search is an example of what type of algorithm?

  Divide and conquer
• Bubble Sort

  1. Looks at the first two items in the list
  2. If they're in the right order, you don't have to do anything. If they're in the wrong order, swap them
  3. Move onto the next pair (2nd and 3rd entries) and repeat step 2
  4. Repeat step 3 until you get the end of the list- this is called one pass
  5. Repeat steps 1-4 until there are no swaps in a pass
• Advantages of a bubble sort:

  • It's a simple algorithm that can be easily implemented on a computer
  • It's an efficient way to check if a list is already in order.
  • Doesn't use very much memory as all the sorting is done using the original list
• Disadvantages of a bubble sort:

  • It's an inefficient way to sort a list
  • Due to being inefficient, the bubble sort algorithm does not cope well with a very large list of items
• Merge Sort

  1. Split the lists into lists of size one.
  2. Merge each pair of sub-lists by comparing the first value of each list and putting the smaller value into the new list first.
  3. Continue merging until there is only one list.
• Advantages of a merge sort:

  • It's generally more efficient and quicker than a bubble sort and insertion sort algorithms for large lists
  • It has a very consistent running time regardless of how ordered the items in the original list are
• Disadvantages of a merge sort:

  • It's slower than other algorithms for small lists
  • Even if the list is already sorted it still goes through the whole splitting and merging process
  • It uses more memory than other sorting algorithms in order to create the separate lists
• 3 types of sorting algorithms:

  1. Bubble sort
  2. Merge sort
  3. Insertion sort
• Which type of sort is this?

  Merge sort

  
• Which type of sort is this?

  Bubble sort

  
• Which type of sort is this?

  Insertion sort

  
• Insertion sort

  1. An insertion sort compares values in turn, starting with the second value in the list. If this value is greater than the value to the left of it, no changes are made.
  2. Otherwise this value is repeatedly moved left until it meets a value that is less than it.
  3. The sort process then starts again with the next value.
  4. This continues until the end of the list is reached.
• Advantages of a insertion sort:

  • Easy to implement
  • Little memory used
• Disadvantages of a insertion sort:

  • Not very efficient (Large data sets are more efficiently handled by merge sorts.)
• What type of sort is this?

  Insertion sort

  
• What type of sort is this?

  Bubble sort

  
• 2 types of search algorithms:

  1. Binary search
  2. Linear search
• What type of search algorithm is this?

  Linear search

  
• What type of search algorithm is this?

  Binary search