Welcome to Lesson 4!
Learning Objectives for Today's LessonBy 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
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
Advantage:  Easy to write and remember
Disadvantage: 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.
 Hint: Use copy and paste to your
advantage.
 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.
 When finished, upload your Sort.java file to Canvas.
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 unalphabetized exams at the back of the pile.
 Onebyone, you insert an exam from the unalphabetized 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 unalphabetized 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.
 Onebyone, 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[j1] > temp
A[j] = A[j1]
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).
 Hint: Use copy and paste to your
advantage.
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! ~
