CSCI 2 Chapter 18 Searching and Sorting

Selection and insertion, are called…

Quadratic sorts

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

Phase one of merge sort

a) Divide the unsorted list into sub-arrays of two smaller halves.

b) Then, the smaller lists are broken down further until they can no longer be divided, leaving one element item in each halved list

Merge sort phase two

Sort and merge two of the sub-arrays until you have sorted and merged all the sub-arrays that were created in phase one.

Note: always start the sorting and merge in the reverse order of phase one

Merge sort is also called

logarithimic sorts

Searching

the process of finding a target element among a group of items (the search pool) or determining that it isn't there

requires repetitively comparing the target to candidates in the search pool

An efficient search…

performs no more comparisons than it has to.

Linear search

examines each item in the search pool, one at a time, until either the target is found or until the pool is exhausted

does not assume the items in the search pool are in any particular order

binary search

eliminates large parts of the search pool with each comparison

Begins in the middle, rather than at one end

If the target isn't found, we know that if it is in the pool at all, it is in one half or the other

We can then jump to the middle of that half, and continue similarly

Each comparison in a binary search eliminates half of the viable candidates that remain in the search pool

A 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.

Binary search steps

1) Add the smallest index to the largest index then divide it by 2. Note: you are doing integer division.

2) Then compare the target with the middle value found at the index in part 1 above.

a) If the target value and the middle value are equal, then return the index of the middle value.

b) If the target value is greater than the middle value, then the target must be in the 2nd half of the subarray.

c) If the target is less than the middle value, then the target must be in the 1st half of the subarray.

3) Repeat the steps above starting a step #1 on the new subarray until the target is found or the list is exhausted (that is, the target is not found in the list).

Sorting

The process of arranging a group of items into a defined order based on particular criteria

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 a values by repetitively inserting a particular value into a sorted subset of the list

Insertion sort steps

1) If it is the first element, it is already sorted.

2) Pick the next element and compare it with all the elements in the sorted sub-list.

3) Shift if necessary to the right all the elements in the sorted sub- list to that is greater than the value to be sorted.

4) Repeat the steps starting at step#2 until the list is sorted.