Lecture Preview: Searching and Sorting

(Suggested book reading: Programming Abstractions in C++, section 7.5, 10.1)

Today we will discuss various algorithms for searching for a value in a vector of data. The most straightforward algorithm is to start at the beginning of the vector and loop across it, which is called a sequential search. If the data in the vector is sorted, a more efficient algorithm is to repeatedly look at the middle element and eliminate half of the data until the target is found. This is called a binary search.

figure

We will also discuss a few algorithms for sorting the data in a vector. One algorithm is selection sort, which repeatedly finds the smallest remaining element and swaps it to the front:

figure

Another algorithm is merge sort, which involves splitting the data in half, sorting the halves, and then merging the sorted halves into a sorted whole:

figure

There are a huge number of sorting algorithms, each with its own pros and cons. This makes sorting an interesting problem to study in terms of the tradeoffs and algorithm analysis.

This document and its content are copyright © Marty Stepp, 2015. All rights reserved. Any redistribution, reproduction, transmission, or storage of part or all of the contents in any form is prohibited without the authors' expressed written permission.