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

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 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.
Image result for exam papers

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.
Insertion sort divides an array into a sorted and unsorted section
  • 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.
One-by-one it takes elements and places them in the sorted part of the array

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

  • 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).
  • 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! ~