UTK Notes

Home / CS102 / Lectures / Sorting and Searching Algorithms

Sorting and Searching Algorithms

Oftentimes, you will come across a list of numerical data than you need to order from least to greatest (or greatest to least)
In other words, you need to *sort- them in numerical order
Oftentimes the data will be stored in an array or vector, and sorting algorithms allow us to move the data around in the same vector
There are many algorithms to sort a list of numbers, and some are more efficient than others
We will learn a set of less efficient sorting algorithms in this class, and in 202/302 you will learn more efficient ones
Questions about sorting (both efficient and non-efficient algorithms) are popular interview topic questions
Fair warning: it is MUCH easier to look at a picture or watch a video to understand the steps in the algorithm for selection and insertion sort

Pass (as in, first pass, second pass)
- We have a “pass” through a vector if every element is looked at, and we are going back to the beginning index to repeat steps in the algorithm (this happens in Bubble Sort)
Ascending Order
- Ordering from least to greatest, the most common order to sort values
Descending Order
- Ordering from greatest to least

Bubble sort works by repeatedly swapping adjacent elements if they are in wrong order.
- The algorithm will take the first pair in the list (index 0 and 1), see if they are in the correct order, and if not, swap.
- Then the algorithm will take the next pair (potentially new index 1, index 2), and repeat.
The algorithm is named Bubble Sort because the elements with greater value than their surrounding elements “bubble” towards the end of the list.

Selection sort works by stepping through each index of the vector (think of this index as the “selected” index) and placing the correct value in that index. It will not move again.
- We start at index 0 as the selected index. We look at every value to the right of the selected index and find the smallest value. We swap the value at the selected index (0) with the smallest value found.
- Next, we move the selected index to index 1. We repeat (look at every value to right of the selected index) to find the smallest value, and swap.
- If there are no values to the right of the selected index that are smaller, no swap will occur.
Unlike Bubble Sort, Selection Sort does not go back to previous indexes at any point
Selection sort is the only algorithm where we decide the *final* resting spot of a value.
If we are running the algorithm and the selected index is 5 currently, then we know indexes 0-4 are sorted and their values will not change.

Insertion sort works by splitting the vector into two parts, the sorted portion, and the unsorted portion.
Selection sort also has a sorted portion, and but insertion sort’s sorted portion is only RELATIVE to the other items in the sorted portion. Their final resting index is not determined and may change as other values are moved into the sorted portion.
Begin with index 0 as the “sorted” portion (a sorted portion consisting of one item).
- Take the first index to the right of the sorted portion (i.e. the first element in the unsorted portion), and look backwards through the unsorted portion and “insert” the value where it belongs.
- This is the most common way people sort playing cards in their hand.

Linear Search is a very simple algorithm, essentially a for loop.
A sequential search is made over items one by one. Each item is checked and if a match is found, then that item is returned, otherwise the search continues till the end of the list.

Binary Search is a much more efficient searching algorithm (i.e. will find matches faster, on average).
Algorithm:
- Make sure the list is sorted before starting the algorithm.
- Designate a beginning, midpoint, and end for the list.
- See if the value you are searching for is greater than, less than, or equal to the midpoint.
- If it’s greater than the midpoint, remove the bottom half from the searching area and repeat. If it’s less than the midpoint, remove the top half from the searching area and repeat.
- If it’s equal to the midpoint, then you have a match! If you have reached a searching area of size 1, and still haven’t found a match, then the value is not in the list. This is implemented by checking if the “end” (or “high”) is less than the “begin” (or “low”)
Use the following formula to find the midpoint:
- mid = low + (high - low) / 2
- Note – this uses integer division
Blue squares are the searchable portion