Lecture Preview: Sorting

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

Today we will 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, 2018. 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.