CSC 2110 Lecture Notes - Lecture 18: Bubble Sort, Insertion Sort, Search Algorithm
Document Summary
A collection of values of the same type. Array is a convenient place to store a list. Search the list for a given item. The sorting problem is to rearrange the items of a given list in a nondecreasing order. Many sorting algorithms are available in literature. Smaller elements move toward the top (beginning of the list) Larger elements move toward the bottom (end of list) During the sorting phase, the array is divided into two subunits. Elements in the unsorted sublist are to be moved in to the proper places in the sorted sublist, one at a time. The key comparisons is equal to half of the size of the list. Does not assume that the list is sorted. If list is sorted, then the search algorithm can be improved. In order to apply binary search, the list must be sorted. Every iteration of the while loop cuts the size of the search by half.