# Class 45: Introduction to Sorting

Back to Searching, continued. On to Merge Sort.

Held Friday, November 17, 2000

Summary

Today we move on to algorithm design for a very common problem, that of sorting. When you sort an array or vector, you put the elements in order (e.g., alphabetical, numerical, ...).

Notes

• I've decided not to add any more homework stress to your lives. Hence, any remaining homeworks will be based on labs.
• The searching lab is due next Wednesday.
• Since I didn't end up giving separate lab writeups as assignments, I've updated the grading scale. Homework is still worth 30%, and includes the lab writeups. Class participation is still worth 10%. I'll probably give you a chance to grade each other on class participation :-)
• I'll be gone on Monday. Mr. Walker will run a lab on sorting. I'll email you about the readings for Monday and Tuesday. I'd appreciate it if you do each reading on time.
• Have a great weekend!

Overview

• The problem
• Examples using various objects
• Describing the problem
• Famous solutions

## The Problem of Sorting

• Typically, computer scientists look at collections of problems and attempt to find appropriate generalizations of these problems (or their subproblems).
• By solving the generalized problem, you solve a number of related problems.
• One problem that seems to crop up a lot is that of sorting. Given a list, array, vector, sequence, or file of comparable elements, put the elements in order.
• in order typically means that each element is no bigger than the next element. (You can also sort in decreasing order, in which case each element is no smaller than the next element.)
• you also need to ensure that all elements in the original list are in the sorted list.
• you also need to ensure that no other elements are in the list.
• We'll look at techniques for sorting vectors and lists.

## Sorting Examples

• In my experience, most of us know some sorting algorithms, but have difficulty generalizing them.
• I'll bring in some things to sort (most frequently, a stack of CDs) and we'll look at different ways to sort them.

## Formal Description

• Before moving on to algorithms for solving the sorting problem, let's take a look at the way wemight document one (or all) of the procedures
• Purpose?
• Parameters?
• Produces?
• Preconditions?
• Postconditions?

## Insertion Sort

• One simple sorting technique is insertion sort.
• Insertion sort operates by segmenting the list into unsorted and sorted portions, and repeatedly removing the first element from the unsorted portion and inserting it into the correct place in the sorted portion.
• This may be likened to the way typical card players sort their hands.
• What's the extra storage? It should be constant.
• How might we code this recursively?

## Bubble Sort

• Selection sort is among the simpler and more natural methods for sorting.
• In this sorting algorithm, you segment the array into two subparts, a sorted part and an unsorted part. You repeatedly find the largest of the unsorted elements, and swap it into the beginning of the sorted part. This continues until there are no unsorted elements.
```+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|
Unsorted           Sorted
```
• Note that we can also write selection sort iteratively.

## Bubble Sort

• Bubble sort is a lot like both insertion sort and selection sort
• In bubble sort, you step all the way through the array, swapping adjacent elements if they're out of order.
• This ``bubbles'' the largest value to the end.
• Like selection sort, it puts the largest value at the end. It just uses a different technique.
• Like insertion sort, it repeatedly swaps neighboring elements when they're out of order. Unlike insertion sort, it goes all the way through the array.
• There's an interesting variant of bubble sort that requires multiple simultaneous swaps. We'll simulate it in class if there's enough time.

## History

Thursday, 24 August 2000

• Created as a blank outline.

Back to Searching, continued. On to Merge Sort.

Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.