• 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?
  

• 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 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:

• We could sort the elements in this array A by increasing order of value:

• Or, we could sort by decreasing order of value:

• Or we could sort first by primes and then by composite numbers:

• 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:

• Bubble sort
• Insertion sort
• Selection sort
  

• 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
• Bogosort and other joke algorithms
  

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.
  

• 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.
  

• 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.

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.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