Searching and Sorting

Chapter 18: Searching and Sorting

Chapter Scope

• Linear search and binary search algorithms

• Sorting algorithms:

  • Selection sort

  • Insertion sort

  • Merge sort

• Complexity of search and sort algorithms.

• Comparators

Searching

• Searching: process of finding a target element within a group of items (search pool) or determining it's absence.

• Requires repetitively comparing the target to candidates in the search pool.

• Efficient search: performs no more comparisons than necessary.

Linear Search

• Examines each item in the search pool, one at a time, until the target is found or the pool is exhausted.

• Does not assume items in the search pool are in any particular order.

Binary Search

• Requires the search pool to be sorted to be more efficient than a linear search.

• Eliminates large parts of the search pool with each comparison

• Begins in the middle of the pool.

• If the target isn't found, it can be determined if it's in the upper or lower half of the pool.

• Then, the search jumps to the middle of that half, and continues similarly.

• Each comparison eliminates half of the viable candidates.

• Example: Finding the number 29 in the sorted list: 8 15 22 29 36 54 55 61 70 73 88.

  • First, compare the target to the middle value 54.

  • Since 29 is less than 54, it must be in the front half of the list.

  • With one comparison, half the data is eliminated.

  • Then compare to 22, eliminating another quarter of the data, etc.

• Binary search algorithm is often implemented recursively.

• Each recursive call searches a smaller portion of the search pool.

• The base case is when there are no more viable candidates.

• At any point, there may be two “middle” values, in which case the first is used

Comparing Search Algorithms

• The expected case for finding an element with a linear search is n/2, which is O(n).

• Worst case is also O(n).

• The worst case for binary search is (log_2 n)/2 comparisons, which makes binary search O(log n).

• Binary search requires the elements to be already sorted.

Sorting

• Sorting: Arranging a group of items into a defined order based on particular criteria.

• Sequential sorts require approximately n^2 comparisons to sort n elements.

• Logarithmic sorts typically require n log_2 n comparisons to sort n elements.

Selection Sort

• Orders a list of values by repetitively putting a particular value into its final position.

  • Find the smallest value in the list.

  • Switch it with the value in the first position.

  • Find the next smallest value in the list.

  • Switch it with the value in the second position.

  • Repeat until all values are in their proper places.

Insertion Sort

• Orders values by repetitively inserting a particular value into a sorted subset of the list.

  • Consider the first item to be a sorted sublist of length 1.

  • Insert the second item into the sorted sublist, shifting the first item if needed.

  • Insert the third item into the sorted sublist, shifting the other items as needed.

  • Repeat until all values have been inserted into their proper positions.

Merge Sort

• Orders values by recursively dividing the list in half until each sub-list has one element, then recombining.

  • Divide the list into two roughly equal parts.

  • Recursively divide each part in half, continuing until a part contains only one element.

  • Merge the two parts into one sorted list.

  • Continue to merge parts as the recursion unfolds.

Comparing Sorts

• Selection sort and insertion sort use different techniques but are both O(n^2).

• They are all based in a nested loop approach.

• Merge sort divides the list repeatedly in half, which results in the O(log n) portion.

• The act of merging is O(n).

• So the efficiency of merge sort is O(n log n).

• Selection and insertion are called quadratic sorts, while merge sort is called a logarithmic sort.