cs chapter 3

Ascending

Arranging items from smallest to largest

Descending

Arranging items from largest to smallest

Traversal

travel across or through something (in bubble sort is making a pass across the entire given list)

Bubble sort

Occurs to sort into either ascending or descending order

Starts at one end of the list, and gradually moves down the list comparing pairs of data items and swapping if they are in the wrong order. The comparisons continue until the end of the list is reached. Each complete traversal is called a pass. This process repeats until there are no swaps made during a pass, indicating that it is sorted in the right order. A computer will take one extra pass because of this.

Why will a computer take one extra pass than a human when doing bubble sort?

A computer would have to do one extra pass to ensure no remaining swaps need to be made and check if the list is in the right order. A human would be able to recognize without an extra pass if the list is sorted in the correct order.

Recursion

A process that is repeated on the results of a previous application of the method

Merge Sort

Is a sorting algorithm that divides a list into two smaller lists and divides these in two until the size of each list is one item. It applies recursion

Brute force

An algorithm design that does not include any techniques to improve performance, but instead relies on computing power to try all possibilities until the solution to a problem is found.

Why is bubble sort said to be using brute force?

Bubble sort is said to be using brute force because it stars at the beginning and completes the same task over and over again until it has found a solution

Divide and Conquer

An algorithm design that works by dividing a problem into smaller and smaller sub-problems until they are easy to solve. Solutions to these sub-problems are then combined to give a solution to the complete problem.

Why is merge sort said to be using divide and conquer

It is said to be using divide and conquer method because it repeatedly breaks down the problem into smaller sub-problems, solves those and then combines the solutions to reach a solution to the original more complex problem

Linear Search

Simple, sequential algorithm that goes through the list from the beginning item by item until it finds the search item or reaches the end of the list without finding it

Start at first item in list

Compare item with search item

If same, then stop search

If not same, move on to next item of list

Repeat 2-4 until end of list is reached

Median

The middle number when the numbers are put in ascending order ( If two numbers are in the middle, the higher of the two will be chosen)

Binary Search

Median item is list is repeatedly selected and compared with search item

Based on its comparison, list to be searched is reduced (if selected item is too high, lower items are searched, if selected item is too low, higher items are searched)

CANNOT WORK ON UNSORTED LIST so it NEEDS to be sorted beforehand

Compare and contrast efficiency of the searching algorithms

Linear search is most efficient if the search item is the first item, least efficient if search item is the last item

Binary search is most efficient if the search item is median, least efficient if search item is first or last item

List must have to be sorted for binary search to occur so a sorting algorithm has to be applied before the searching algorithm

Linear search works on both sorted and unsorted lists

If list only has to be searched once, linear is better

If list has to be searched many times, binary search is better