NOTE: This web site is out of date. This is the course web site from a past quarter, Winter 2018. If you are a current student taking the course, this is not your class web site, and you should visit the current class web site instead at http://cs106b.stanford.edu/. If you are already at http://cs106b.stanford.edu/, the web page may not be updated yet for the new quarter. Please be advised that courses change with each new quarter and instructor. Any information on this out-of-date page may not apply to you this quarter.

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.