outline

Searching

• Ever had to search for a word in the dictionary
• Or, search for a file on the computer

Searching types

• Sequential -
     this would be starting at the A's in the phone book and looking through each letter until you came to the last name Watson
• Random -
     this would be opening the phone book to a page, checking to see where it was in the alphabet and moving by groups of pages until you came to the Watson page

Sorting

• Another problem we solve is sorting, we alphabetize a list of names or we file documents based on a order of items
• Sorting compares has two basic operations -
      comparing two items to see which is largest and
      copy an item from one place to another

Sorting types

• Bubble Sort
• Selection Sort
• Insertion Sort - as humans we use this sorting method most in life
• Merge Sort
• Quick Sort

Bubble Sort

• Compares two neighboring items - if in the wrong order - swaps them
• Computer moves through the list comparing and swapping
• At the end of one pass, the largest item will have "bubbled up" to the last position on the list
• This continues until each item is in the correct place

Selection Sort

• Easiest to understand
• The next largest item is found and moved into position at the end of the list
• Still compares two items at a time - finding the largest in the list, comparing, keeping track of the largest, swapping to the next available spot at the end of the list

Insertion Sort

• Take a sorted list and insert a new item into the proper position in the list
• The length of the list grows by one every time a new item is inserted

N² and N^*log(N)

• Some sorting algorithms exhibit what is called running time on the order of N squared or N² algorithms
• N is the number of items being sorted
• An algorithm is of the order of N² means that the running time of the algorithm for an array of N items is given approximately by K^*N² where K is some constant number

Constant Value

• Different algorithms have different values for K
• Even if the same algorithm is run on different computers, each computer will give a different value of K
• K being a "constant" means that for a given algorithm running on a given computer, there is one value of K that will work for any array size N
• Bubble sort is an example of an N² algorithm