n301/cs21complexity n301.tplt 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