Welcome to Lesson 4!

## Learning Objectives for Today's Lesson

By the end of today's lesson, you should know...
• What is a sorting algorithm?
• What is the bubble sort algorithm and how does it sort an array?
• What is the insertion sort algorithm and how does it sort an array?

1. Sorting Algorithms
Introduction to Sorting
• When we sort a collection of data, we arrange it in increasing or decreasing order based on some particular property of the data
• Sorting is a task that we perform often in our daily lives.
• Sorting improves our ability to read or understand data
• Sorting data makes it easier to search or extract a particular element.
• Let's look at some examples:
• When booking a vacation using a site such as hotels.com, we have the option to sort the list of hotels by price, by star rating or by some other property:

• When looking up words in a dictionary, the words must be sorted into alphabetical order or it will be impossible to find the one we are looking for:

• When we go shopping at a department store, the clothes are sorted first by category (mens vs womens vs childrens, etc) and then by size in order to make it easier to find a garment to purchase:

• Can you think of any other sorted data that you interact with on a daily basis?
Sorting Algorithms in Computer Science

• Sorting data is a very common task in computer science.
• Typically, sorting is performed on an array
• Sorting an array will involve rearranging the array into a sorted order.
• This order could be alphabetical or numerical or based on some other property of the data (such as add date in the case of a class roster of names).
• Let's take the below array as an example:

A = [3, 5, 2, 1, 9, 7, 6]
• We could sort the elements in this array A by increasing order of value:
A = [1, 2, 3, 5, 6, 7, 9]
• Or, we could sort by decreasing order of value:
A = [9, 7, 6, 5, 3, 2, 1]
• Or we could sort first by primes and then by composite numbers:
A = [1, 2, 3, 5, 7, 6, 9]
• However, traditionally in computer science, arrays are sorted into increasing numerical or lexicographical (alphabetical) order by applying what is known as a sorting algorithm.
• A sorting algorithm is simply a series of steps to follow to sort a list of data by some property.
• Some common sorting algorithms include:
Less efficient (slower):
• Bubble sort
• Insertion sort
• Selection sort
- - - - - - - - -- - - - - - - -
More efficient (quicker)
• Heap Sort
• Merge sort
• Quick sort
• These algorithms all use a different series of steps to sort a list of data.
• The first 3 algorithms are consider "slow" algorithms. It takes more steps to sort the data using these algorithms and they will typically finish the task more slowly.
• However, the advantage of the first three algorithms is that they are easy to understand and implement.
• The last three algorithms are "faster" algorithms but more conceptually difficult.
• We will implement bubble sort and insertion sort today in class.
• When you take 22C, you will implement the last three algorithms
• To help you visualize the difference between the faster and slower algorithms: Sorting algorithm "race"
• There are many more sorting algorithms than the above 6. Some are even joke sorting algorithms

2. Bubble Sort
• Compare all pairs of values
• Swap any pair where the first value is larger than the second value
• Repeat from beginning until array is sorted
• Note: As algorithm progresses, sorted part of array built up from end.
• Largest value will repeatedly swap until it reaches the end of the array on the first pass and then stays there.
• In other words, largest element will "bubble up" to its correct location in the sorted array.
• In the second pass of algorithm, second largest element will be swapped to end of array, where it will stay, etc.
• Thus, the algorithm makes one fewer comparison for each pass (does not compare value(s) at end of the array that are known to be in sorted order)

Bubble Sort Animation

• For example:

First Pass:

[ 5 3 8 2 4 ] –> [ 3 5 4 2 8 ] // Here, algorithm compares the first two elements, and swaps since 5 > 3.
[ 3 5 8 2 4 ] –>  [ 3 5 8 2 4 ] // No Swap since 5 < 8
[ 3 5 8 2 4 ] –>  [ 3 5 2 8 4 ] // Swap since 8 > 2
[ 3 5 2 8 4 ] –> [ 3 5 2 4 8 ] //
Swap since 8 > 4. 8 arrives at end of array, where it will stay

Second Pass:

[ 3 5 2 4 8 ] –> [ 3 5 2 4 8 ] //Start again at the beginning. No swap since 3 < 5
[ 3 5 2 4 8 ] –> [ 3 2 5 4 8 ] //Swap since 5 > 2
[ 3 2 5 4 8 ] –> [ 3 2 4 5 8 ] //Swap since 5 > 4. Now 5 in correct location, where it will stay

Third Pass:

[ 3 2 4 5 8 ] –> [ 2 3 4 5 8 ] //Swap since 3 > 2
[ 2 3 4 5 8 ] –> [ 2 3 4 5 8 ] //No swap since 3 < 4. Now 4 in correct location, where it will stay

Fourth Pass:

[ 2 3 4 5 8 ] –> [ 2 3 4 5 8 ] //No swap, since 2 < 3. Now 3 in correct location, where it will stay

Bubble Sort Pseudocode - assuming that you compare each pair and ignore the fact that part of the array is already sorted after each pass:

BubbleSort(A[])
for i = 0 up to and including length - 2
for j = 0 up to and including length - 2
if A[j] > A[j+1]
A[j] <---> A[j+1] //swap

More efficient Bubble Sort (doesn't compare elements that are already sorted at the end of the array)

BubbleSort(A[])
for i = 0 up to and including length - 2
for j = 0 up to and including length - i - 2 //each pass make fewer comparisons
if A[j] > A[j+1]
A[j] <---> A[j+1] //swap

• Easy to write and remember
• Very sloooowww
• Never used in real life applications - unless using a very small array

Activity 4.1: Tracing Bubble Sort (10 pts)
• Open up MS Word or another text editor, create a new text document named trace, with a doc, docx, odt, or txt extension
• Then trace bubble sort on the following array.
• You must show intermediate steps, labeled below as "Comparisons"
• - i.e. show what happens when two elements are compared to each other - show them as swapped or not swapped.
• To save yourself unnecessary work, use the more efficient version of bubble sort.
• Please highlight the two elements being compared in some way (underline, bold, or italicize them, or place brackets around them)
• Trace bubble sort on the following array of data. int A[] = { 12, 3, 19, 14, 2};
Comparison 1: 3 12 19 14 2
Comparison 2:
Comparison 3: 3 12 14 19 2
Comparison 4:
Comparison 5:
Comparison 6: 3 12 14 2 19
Comparison 7:
Comparison 8:
Comparison 9:
Comparison 10: 2 3 12 14 19
• When you are finished, upload trace.doc/.text/.odt/.docx to Canvas, then move onto the next activity.

The Swap Algorithm :
• Many sorting algorithms use swapping as a mechanic
• It is important to know how to write code to do a simple swap

`Activity 4.2: Implementing Bubble Sort (10 pts)`
• Open up Eclipse and create a new Java project called Sort with a class named Sort.java.
• Copy and paste the starter code below into the file and add your name in the comment at the top.
`/** * Sort.java * A program to sort a list of numbers * @author  */public class Sort {	    public static void main(String[] args) {              int top10Scores[] = {95, 92, 88, 99, 93, 89, 94, 97, 100, 91};        System.out.println("Top 10 Exam Scores, Unsorted:");        printArray(top10Scores);               //call bubbleSort here!              System.out.println("\nAfter Sorting:");        printArray(top10Scores);            }//end of main        /**     * Sorts an array of integers from smallest to largest     * using the bubble sort algorithm     * @param array the list of integer values     */    public static void bubbleSort(int array[]) {       return;    }    /**     * Print an array of integers to the console     * @param array the list of integer values     */    public static void printArray(int[] array) {    	for (int i = 0; i < array.length; i++) {    		System.out.println((i + 1) + ". " + array[i]);    	}    } //end of method printArray}//end of class`
• Write the bubbleSort method using the more efficient version of bubble sort's pseudocode provided above.
• Make sure your bubbleSort method correctly sorts the given array.
• If you get stuck, post a question on Piazza.

3. Insertion Sort

Insertion Sort Overview
• Consider: How do you alphabetize a set of student exam papers?
• You keep the exams that have already been alphabetized at the front of the pile.
• You keep the un-alphabetized exams at the back of the pile.
• One-by-one, you insert an exam from the un-alphabetized pile into the correct place in the alphabetized pile.
• The alphabetized part of the pile grows larger and larger until it contains all the exams.
• The un-alphabetized part of the pile grows smaller and smaller until it contains no exams.
• Insertion sort works in the same way.

Insertion Sort
• An algorithm for sorting the items in an array.
• You keep the sorted set of items at the front of the array.
• You keep the unsorted set of items at the back of the array.
• One-by-one, you insert an item from the unsorted part of the array into the correct place in the sorted part of the array.

• The sorted part of the array grows larger and larger until it contains all items.

• The unsorted part of the array grows smaller and smaller until it contains no items.

Insertion Sort in Action:

Insertion Sort Video: Romanian Folk Dancers
• Video: Romanian Folk Dancers

Insertion Sort Pseudocode

```for i = 1 up to and including length(A) - 1
temp = A[i] //next value to place in sorted order
j = i //its location    //loop to shift up elements and create a hole       while j > 0 and A[j-1] > temp
A[j] = A[j-1]
j = j - 1    end while         A[j] = temp //copy into new position
end for```
`Let's try it with an example!: A = {5, 8, 3, 2, 9};`
`Pass 1: {5, 8 | 3, 2, 9}Pass 2: {3, 5, 8 | 2, 9}Pass 3: {2, 3, 5, 8 | 9}Pass 4: {2, 3, 5, 8, 9}`
Activity 4.3: Tracing Insertion Sort (10 pts)
• Open up the same document in which you traced Bubble Sort in Activity 4.1 and trace insertion sort on the first array.
• Optionally, you can also trace insertion sort on the second array
• You must show each intermediate step, labeled as Passes (see above for an example).

1. Trace insertion sort on the following array of data. int A[] = { 19, 3, 78, 79, 15, 45, 1};

Pass 1: 3, 19, 78, 79, 15, 45, 1
Pass 2:
Pass 3:
Pass 4:
Pass 5:
Pass 6:

2. Trace insertion sort on the following array of data. String A[] = { "bird", "bicycle", "ants", "cat", "array", "film", "brim", "elephant"};

Pass 1: "bicycle", "bird", "ants", "cat", "array", "film", "brim", "elephant"
Pass 2:
Pass 3:
Pass 4:
Pass 5:
Pass 6:
Pass 7:

When you are finished, upload trace.doc/.docx/.odt/.txt to Canvas

`Activity 4.4: Implementing Insertion Sort (10 pts)`
• Open up your Sort.java file from the prior activity.
• Copy and paste the below method into your file right below bubbleSort.

`    /**     * Sorts an array of integers from smallest to largest     * using the insertion sort algorithm     * @param array the list of integer values     */        public static void insertionSort(int array[]) {        return;    }`
• Write the insertionSort method by using the pseudocode for insertion sort provided above.
• Now, remove the method call to bubbleSort in main and replace it with a call to insertionSort.
• Note that you can leave the bubbleSort method inside of your program, you just won't be calling it.
• You should get the same sorted output as when you called bubbleSort.
• If you get stuck, post a question on Piazza.
• When finished, upload Sort.java to Canvas.

## Wrap Up

• Answer the Lesson 4 Practice Exam Questions on Canvas

## Upcoming Assignments

• Lesson 4 Practice Exam Questions due Thursday at 11:59pm on Canvas
• Peer Reviews due Saturday at 11:59pm on Canvas
• Quiz 2 due Friday at 11:59pm on Canvas
• Lab 2 due Monday at 11:59pm on Canvas

~ Have a Great Weekend! ~