Showing posts with label merge sort. Show all posts
Showing posts with label merge sort. Show all posts

Friday, March 29, 2013

Merge Sort

Merge Sort

Merge Sort

Introduction

Merge sort works based on the fact that it is relatively easy to take 2 sorted lists and merge them into a larger sorted list. Once we have a merge operation the rest of the sorting routine is relatively simple. Merge sort is also a faster sorting algorithm than either selection sort or insertion sort (on moderate sized lists or arrays anyway). It has to do with the divide and conquer structure of the recursive solution. Merge sort's one draw back is that it is memory intensive. At each level of recursion a new list has to be created to hold the merged smaller lists until the program get's back to the top level call where a new list of sorted elements is provided. In the other 2 sorts the sorting is done inline and only a 'tmp' variable is needed to swap the values when necessary. Memory used to be a big thing now adays not so much. Memory for computers is relatively cheap and many gigabytes may be had for a few hundred dollars.

Merge operation

I will develop the merge sort in the same SortLab class as the other sort routines. First step in the merge sort is let's develop the merge operation.

Specifications

  • Take two int[] parameters that are assumed to be sorted
  • return a new int[] whose length is the size of list1.length + list2.length
  • The returned int[] should have its elements sorted in ascending order

Even though the lists are sorted this operation needs to track a few things:

  • One array may run out of elements early at which point just add in the last elements from the other array
  • Even if they alternate they may not alternate evenly so we must track where we are in each contributing array
  • In the first round of testing merge will be a static routine. Once we go to a full merge sort we will instantiate an object as we did for the other routines

merge code

public static int[] merge(int[] a, int[] b)
{
    int[] m = new int[a.length + b.length];
    int i=0;
    int j=0;

    for (int k = 0; k < m.length; k++)
    {
        if (i < a.length && j < b.length) {
        if (a[i]<=b[j]) {
            m[k] = a[i];
            i++;
        }
        else {
            m[k] = b[j];
            j++;
        }
        }
        else if (i < a.length) {  // b exhausted use up a
            m[k] = a[i];
            i++;
        }
        else { // b still has some left use up those
            m[k] = b[j];
            j++;
        }
    }
    return m;
}

public static void main(String[] args) {
    SortLab select = new SortLab();
    SortLab selectA = new SortLab();
    SortLab insert = new SortLab();
    SortLab insertA = new SortLab();

    System.out.println("Selection Sort");
    System.out.print("unsorted: ");
    select.display();
    select.selection();
    System.out.print("sorted:   ");
    select.display();
    System.out.println("SelectionA Sort");
    System.out.print("unsorted: ");
    selectA.display();
    selectA.selectionA();
    System.out.print("sorted:   ");
    selectA.display();
    System.out.println();
    System.out.println();
    System.out.println("Insertion Sort");
    System.out.print("unsorted: ");
    insert.display();
    insert.insertion();
    System.out.print("sorted:   ");
    insert.display();
    System.out.println("Insertion Sort with Explicit Shift");
    System.out.print("unsorted: ");
    insertA.display();
    insertA.insertion();
    System.out.print("sorted:   ");
    insertA.display();

    System.out.println("Merge Testing");
    int[] l1 = {0, 2, 3, 4, 6, 7, 9};
    int[] l2 = {1, 3, 5, 8, 10};
    int[] l3 = merge(l1,l2);
    for (int i : l3)
    {
        System.out.print(i + " ");
    }
    System.out.println();
}    

Output 1

run:
Selection Sort
unsorted: 9  6  2  1  3  7  8  4  0  5  
interim:  0  6  2  1  3  7  8  4  9  5  
interim:  0  1  2  6  3  7  8  4  9  5  
interim:  0  1  2  6  3  7  8  4  9  5  
interim:  0  1  2  3  6  7  8  4  9  5  
interim:  0  1  2  3  4  7  8  6  9  5  
interim:  0  1  2  3  4  5  8  6  9  7  
interim:  0  1  2  3  4  5  6  8  9  7  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
SelectionA Sort
unsorted: 9  0  5  7  2  8  4  3  1  6  
interim:  0  9  5  7  2  8  4  3  1  6  
interim:  0  1  5  7  2  8  4  3  9  6  
interim:  0  1  2  7  5  8  4  3  9  6  
interim:  0  1  2  3  5  8  4  7  9  6  
interim:  0  1  2  3  4  8  5  7  9  6  
interim:  0  1  2  3  4  5  8  7  9  6  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  


Insertion Sort
unsorted: 3  0  5  2  6  4  7  9  1  8  
interim:  0  3  5  2  6  4  7  9  1  8  
interim:  0  3  5  2  6  4  7  9  1  8  
interim:  0  2  3  5  6  4  7  9  1  8  
interim:  0  2  3  5  6  4  7  9  1  8  
interim:  0  2  3  4  5  6  7  9  1  8  
interim:  0  2  3  4  5  6  7  9  1  8  
interim:  0  2  3  4  5  6  7  9  1  8  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
Insertion Sort with Explicit Shift
unsorted: 1  9  3  8  5  7  6  4  0  2  
interim:  1  9  3  8  5  7  6  4  0  2  
interim:  1  3  9  8  5  7  6  4  0  2  
interim:  1  3  8  9  5  7  6  4  0  2  
interim:  1  3  5  8  9  7  6  4  0  2  
interim:  1  3  5  7  8  9  6  4  0  2  
interim:  1  3  5  6  7  8  9  4  0  2  
interim:  1  3  4  5  6  7  8  9  0  2  
interim:  0  1  3  4  5  6  7  8  9  2  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
Merge Testing
0 1 2 3 3 4 5 6 7 8 9 10 

Splitting the list

Splitting is the next thing to tackle, the straight forward way would be to just add the beginning index and the ending index together and divide by 2. This cuts the list in half. If we start with a list with 10 things in it, the starting index = 0 and the ending index = 9. (0+9)/2 = 4 we split the list after four (4). This gives us 2 lists from 0 - 4 and 5 - 9. We then want to split the list again and again until ideally all we are left with is 10 single element list. If you work this out on various size arrays you end up needing to help a little when you get to a pair of indexes. So my implementation will treat single indexes and pair indexes as the test case for recursion.

Given the above for background lets look at some pseudo code. I will assume that the original list is the labArray field and mergesort will track indexes into that array.

public int[] mergesort(int begin, int end)
{
  int[] newArray = null;
  if (begin == end) { 
    // This is the end of the road create a new list of 1 element
    newArray = new int[1];
    newArray[0] = this.labArray[begin];
    return newArray;
  }
  if (1 == end-begin) {
    // down to 2 elements 
    newArray = new int[2];
    if ( this.labArray[begin] < this.labArray[end]) {
      newArray[0] = this.labArray[begin];
      newArray[1] = this.labArray[end];
    } else {
      newArray[0] = this.labArray[end];
      newArray[1] = this.labArray[begin];
    }
    return newArray;
  }
  int split = (begin + end)/2;
  return merge(mergesort(begin, split), mergesort(split+1,end));
}

This works rather nicely. I have made some changes to the actual code over the above pseudo code to display interim results during the merge sort. The full code includes all the sorting routines we have done so far and the work on merge. Finally the code for the mergesort routine itself. It's implemented as a recursive routine as shown in the pseudocode.

The new routines I've added a new display(int[] array) method to display the new arrays that get built during the mergesort. I have also changed all 'for' statements to the for-each version where possible so you can compare it's use to a standard for loop in the previous implementation. I also use the 'display' methods where I can.

Final Code

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package apcompsci;

/**
 *
 * @author Nasty Old Dog
 */
public class SortLab {

    int[] labArray = null;
    int len = 10;

    public SortLab(int n) {
        this.len = n;
        labArray = new int[this.len];
        for (int i = 0; i < this.len; i++) {
            labArray[i] = i;
        }
        this.shuffle();
    }

    public SortLab() {
        this(10);
    }

    // This shuffle routine adapted from the work done previously
    private void shuffle() {
        int rindex;
        int swap;

        for (int i = 0; i < this.len; i++) {
            rindex = (int) ((Math.random() * ((double) (this.len - i))) + i);
            swap = this.labArray[i];
            this.labArray[i] = this.labArray[rindex];
            this.labArray[rindex] = swap;
        }
    }

    void swap(int k, int l) {
        int tmp;

        tmp = this.labArray[k];
        this.labArray[k] = this.labArray[l];
        this.labArray[l] = tmp;
    }

    public void display() {
        for (int i : this.labArray) {
            System.out.print(i + "  ");
        }
        System.out.println();
    }

    public void display(int[] array) {
        for( int i : array)
        {
            System.out.print(i + "  ");
        }
        System.out.println();
    }

    public void selection() {
        int tmp, tmp_idx;

        for (int i = 0; i < this.len - 1; i++) {
            //select the ith element save value and index
            tmp = this.labArray[i];
            tmp_idx = i;
            // Check if selected is the lowest of the remaining array
            // if not switch them
            for (int j = i + 1; j < this.len; j++) {
                if (this.labArray[j] < tmp) {
                    // found something less save it and it's index
                    tmp = this.labArray[j];
                    tmp_idx = j;
                }
            }
            // if tmp_idx != i then swap the values (move the lowest val in)
            if (tmp_idx != i) {
                this.labArray[tmp_idx] = this.labArray[i];
                this.labArray[i] = tmp;
            }
            System.out.print("interim:  ");
            this.display();
        }
    }

    // Alternate implementation of selection sort using swap function 
    public void selectionA() {
        int tmp, tmp_idx;
        for (int i = 0; i < this.len - 1; i++) {
            tmp = this.labArray[i];
            tmp_idx = i;
            for (int j = i + 1; j < this.len; j++) {
                if (this.labArray[j] < tmp) {
                    tmp = this.labArray[j];
                    tmp_idx = j;
                }
            }
            swap(i, tmp_idx);
            System.out.print("interim:  ");
            this.display();
        }
    }

    public void insertion() {
        int j;

        for (int i = 1; i < this.len; i++) {
            for (j = i; j > 0 && this.labArray[j] < this.labArray[j - 1]; j--) {
                this.swap(j, j - 1);
            }
            System.out.print("interim:  ");
            this.display();
        }
    }

    public void insertionShift()
    {
        int j;
        int tmp;

        for (int i = 1; i < this.len; i++) {
            // take ith element find where it should be inserted
            tmp = this.labArray[i];
            for (j = i; j > 0 && this.labArray[j] < this.labArray[j - 1]; j--) {
                // no need to do anything
                // when the loop ends j will be the insertion position
            }
            // Shift elements from j to i-1 over 1
            for (int k = i - 1; k >= j; k--)
            {
                this.labArray[k + 1] = this.labArray[k];
            }
            this.labArray[j] = tmp;
            System.out.print("interim:  ");
            this.display();
        }
    }

    public int[] merge(int[] a, int[] b)
    {
        int[] m = new int[a.length + b.length];
        int i=0;
        int j=0;

        for (int k = 0; k < m.length; k++)
        {
            if (i < a.length && j < b.length) {
            if (a[i]<=b[j]) {
                m[k] = a[i];
                i++;
            }
            else {
                m[k] = b[j];
                j++;
            }
            }
            else if (i < a.length) {  // b exhausted use up a
                m[k] = a[i];
                i++;
            }
            else { // b still has some left use up those
                m[k] = b[j];
                j++;
            }
        }
        return m;
    }

    public int[] mergesort(int begin, int end)
{
  int[] newArray = null;
  if (begin == end) { 
    // This is the end of the road create a new list of 1 element
    newArray = new int[1];
    newArray[0] = this.labArray[begin];
  System.out.print("interim:  ");
  this.display(newArray);
    return newArray;
  }
  if (1 == end-begin) {
    // down to 2 elements 
    newArray = new int[2];
    if ( this.labArray[begin] < this.labArray[end]) {
      newArray[0] = this.labArray[begin];
      newArray[1] = this.labArray[end];
    } else {
      newArray[0] = this.labArray[end];
      newArray[1] = this.labArray[begin];
    }
  System.out.print("interim:  ");
  this.display(newArray);
    return newArray;
  }
  int split = (begin + end)/2;
  newArray = this.merge(this.mergesort(begin, split), this.mergesort(split+1,end));
  System.out.print("interim:  ");
  this.display(newArray);
  return newArray;
}


    public static void main(String[] args) {
        SortLab select = new SortLab();
        SortLab selectA = new SortLab();
        SortLab insert = new SortLab();
        SortLab insertA = new SortLab();
        SortLab msort = new SortLab();

        System.out.println("Selection Sort");
        System.out.print("unsorted: ");
        select.display();
        select.selection();
        System.out.print("sorted:   ");
        select.display();
        System.out.println("SelectionA Sort");
        System.out.print("unsorted: ");
        selectA.display();
        selectA.selectionA();
        System.out.print("sorted:   ");
        selectA.display();
        System.out.println();
        System.out.println();
        System.out.println("Insertion Sort");
        System.out.print("unsorted: ");
        insert.display();
        insert.insertion();
        System.out.print("sorted:   ");
        insert.display();
        System.out.println("Insertion Sort with Explicit Shift");
        System.out.print("unsorted: ");
        insertA.display();
        insertA.insertion();
        System.out.print("sorted:   ");
        insertA.display();
        System.out.println("\n");
        System.out.println("Merge Testing");
        int[] l1 = {0, 2, 3, 4, 6, 7, 9};
        int[] l2 = {1, 3, 5, 8, 10};
        int[] l3 = msort.merge(l1,l2);
        System.out.print("l1 = ");
        msort.display(l1);
        System.out.print("l2 = ");
        msort.display(l2);
        System.out.print("l3 = merge(l1,l2) = ");
        msort.display(l3);
        System.out.println("\n");

        System.out.println("merge sort");
        System.out.print("unsorted: ");
        msort.display();
        int[] sorted  = msort.mergesort(0,msort.len-1);
        System.out.print("sorted:   ");
        msort.display(sorted);
    }
}

Output 2

run:
Selection Sort
unsorted: 6  2  5  0  3  8  7  1  4  9  
interim:  0  2  5  6  3  8  7  1  4  9  
interim:  0  1  5  6  3  8  7  2  4  9  
interim:  0  1  2  6  3  8  7  5  4  9  
interim:  0  1  2  3  6  8  7  5  4  9  
interim:  0  1  2  3  4  8  7  5  6  9  
interim:  0  1  2  3  4  5  7  8  6  9  
interim:  0  1  2  3  4  5  6  8  7  9  
interim:  0  1  2  3  4  5  6  7  8  9  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
SelectionA Sort
unsorted: 0  3  1  6  9  5  8  4  2  7  
interim:  0  3  1  6  9  5  8  4  2  7  
interim:  0  1  3  6  9  5  8  4  2  7  
interim:  0  1  2  6  9  5  8  4  3  7  
interim:  0  1  2  3  9  5  8  4  6  7  
interim:  0  1  2  3  4  5  8  9  6  7  
interim:  0  1  2  3  4  5  8  9  6  7  
interim:  0  1  2  3  4  5  6  9  8  7  
interim:  0  1  2  3  4  5  6  7  8  9  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  


Insertion Sort
unsorted: 1  3  2  7  6  0  9  8  5  4  
interim:  1  3  2  7  6  0  9  8  5  4  
interim:  1  2  3  7  6  0  9  8  5  4  
interim:  1  2  3  7  6  0  9  8  5  4  
interim:  1  2  3  6  7  0  9  8  5  4  
interim:  0  1  2  3  6  7  9  8  5  4  
interim:  0  1  2  3  6  7  9  8  5  4  
interim:  0  1  2  3  6  7  8  9  5  4  
interim:  0  1  2  3  5  6  7  8  9  4  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
Insertion Sort with Explicit Shift
unsorted: 7  1  2  5  4  3  6  9  8  0  
interim:  1  7  2  5  4  3  6  9  8  0  
interim:  1  2  7  5  4  3  6  9  8  0  
interim:  1  2  5  7  4  3  6  9  8  0  
interim:  1  2  4  5  7  3  6  9  8  0  
interim:  1  2  3  4  5  7  6  9  8  0  
interim:  1  2  3  4  5  6  7  9  8  0  
interim:  1  2  3  4  5  6  7  9  8  0  
interim:  1  2  3  4  5  6  7  8  9  0  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  


Merge Testing
l1 = 0  2  3  4  6  7  9  
l2 = 1  3  5  8  10  
l3 = merge(l1,l2) = 0  1  2  3  3  4  5  6  7  8  9  10  


merge sort
unsorted: 6  9  0  8  7  2  3  1  4  5  
interim:  6  9  
interim:  0  
interim:  0  6  9  
interim:  7  8  
interim:  0  6  7  8  9  
interim:  2  3  
interim:  1  
interim:  1  2  3  
interim:  4  5  
interim:  1  2  3  4  5  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
BUILD SUCCESSFUL (total time: 2 seconds)

Conclusion

If you haven't done so already you should at the very least download the AP Computer Science A Course Description. It's a PDF file and basically goes over everything you should have been taught in AP Computer Science (See References). My read of the latest 2010 document indicates that you only need to know about the 3 sorts I have covered. However in years past looking at the teaching site Bubble sort and Quick sort have been taught in the past. If you have time go over those your teacher's may have introduced them to you. If not then take the College Board at their word and make sure you know the 3 I have presented. For Future knowledge Donald Knuth in his Art of Computer Programming series goes over the following sorts (based on a quick scan of the text I may have missed one or two):

  • Insertion sort
  • Shell Sort
  • Exchange Sort
  • Bubble Sort
  • Baucher Sort
  • Quick Sort
  • Heap Sort
  • Merge Sort

If you go online to Google Scholar you will find many more. Sorting is certainly a basic problem for any Computer Scientist. They all have their drawbacks and the best one changes from time to time as people discover scenarios where the algorithms don't work well. In my day of learning this material I was told that Quicksort was best in actual practice even though theoretically Heap sort should have the better outcome. I don't have a reference for you but if you continue your pursuit of computers you will probably come across Journal articles that will espouse one algorithm over another.

References

  1. Knuth, Donald Ervin. The Art of Computer Programming Sorting and Searching. 2nd ed. Vol. 3. Reading, Mass. Addison-Wesley, 1998.
  2. https://apstudent.collegeboard.org/apcourse/ap-computer-science-a/course-details "Course Details." AP Computer Science A. N.p., n.d. Web. 29 Mar. 2013.

Author: Nasty Old Dog

Tuesday, March 26, 2013

AP Comp Sci Sorting Algorithms

Sorting

Sorting

Introduction

The AP Computer Science test expects you to know 3 sorting methods.

  • Selection sort
  • Insertion sort
  • Merge sort

The blackjack program I have put together needs sorting too. When a hand is scored in Blackjack Aces can be either 1 or 11 in favor of the highest hand you can make without going over 21. By sorting the hands with Aces last the hand can be scored quite easily. So this seemed to be good time to go over sorting.

The Selection sort and Insertion sort are quite easy to implement. Why not start with the easiest part first? To keep it simpler still only int arrays will be used for sorting.

Selection Sort

In selection sort you visit each element of the array up to the second to last element. At each step you look through the array from i to the end, find the smallest value and swap it for the ith element. The pseudo-code should clarify:

int sortArray[] = {4,5,9,6,1,0,3,8,7,2};
int tmp, tmp_idx;

for (int i=0; i < sortArray.length - 1; i++)
{
  tmp = sortArray[i];
  tmp_idx = i;
  for (int j = i + 1; j < sortArray.length; j++) 
  {
    if (sortArray[j] < tmp) {
      tmp = sortArray[j];
      tmp_idx = j;
    }
  }
  // swap the values if the i-th was the smallest this swap doesn't do anything
  // you could test for that if you wanted (which is the way it's done in 
  // the final code)
  sortArray[tmp_idx] = sortArray[i];
  sortArray[i] = tmp;
}

Insertion Sort

Start at the second element and visit the rest of the list. Check the elements before the ith position and see if it is less than any previous elements. If not it stays where it is and move on. This has the appearance of removing the number shifting the elements before it to create a space and placing the number where it belongs.

In the actual implementation you visit each previous element starting at the element immediately to the left and do compare-swaps until one of 2 conditions apply either the number is now at the begining of the list or the element to the immediate left is less. This method accomplishes the shifting of the elements and the comparisons in a way more neatly suited for looping. Again, pseudo-code should help your understanding.

int sortArray[] = {4,5,9,6,1,0,3,8,7,2};
int tmp, tmp_idx;
int j;

for (int i = 1; i < sortArray.length; i++)
{
  for (j = i; j > 0 && sortArray[j] < sortArray[j - 1]; j--)
  {
     // swap
     tmp = sortArray[j];
     sortArray[j] = sortArray[j - 1];
     sortArray[j - 1] = tmp;
  }
}

Create a Sort Lab

To experiment with these I have created a SortLab class. I have borrowed the shuffle method (from the blackjack program) and reworked it for use in the SortLab class. I did this the old fashioned way by cutting and pasting and then changing the names to fit the names of the SortLab fields. The constructors allow you to default to an int array of size 10 or to experiment with other sizes. The arrays are intialized with positive whole numbers. Then they are shuffled to use for sorting. A display method is implemented to print out the values in the array. There is also a swap method to switch values. The selection sort is implemented in 2 different ways. One with an inline swap and a check if a swap is necessary (the first element could have been the lowest of all remaining elements). The other using the swap method with no check.

public class SortLab {

    int[] labArray = null;
    int len = 10;

    public SortLab(int n) {
        this.len = n;
        labArray = new int[this.len];
        for (int i = 0; i < this.len; i++) {
            labArray[i] = i;
        }
        this.shuffle();
    }

    public SortLab() {
        this(10);
    }

    // This shuffle routine adapted from the work done previously
    private void shuffle() {
        int rindex;
        int swap;

        for (int i = 0; i < this.len; i++) {
            rindex = (int) ((Math.random() * ((double) (this.len - i))) + i);
            swap = this.labArray[i];
            this.labArray[i] = this.labArray[rindex];
            this.labArray[rindex] = swap;
        }
    }

    void swap(int k, int l) {
        int tmp;

        tmp = this.labArray[k];
        this.labArray[k] = this.labArray[l];
        this.labArray[l] = tmp;
    }

    public void display() {
        for (int i = 0; i < this.len; i++) {
            System.out.print(this.labArray[i] + "  ");
        }
        System.out.println();
    }

    public void selection() {
        int tmp, tmp_idx;

        for (int i = 0; i < this.len - 1; i++) {
            //select the ith element save value and index
            tmp = this.labArray[i];
            tmp_idx = i;
            // Check if selected is the lowest of the remaining array
            // if not switch them
            for (int j = i + 1; j < this.len; j++) {
                if (this.labArray[j] < tmp) {
                    // found something less save it and it's index
                    tmp = this.labArray[j];
                    tmp_idx = j;
                }
            }
            // if tmp_idx != i then swap the values (move the lowest val in)
            if (tmp_idx != i) {
                this.labArray[tmp_idx] = this.labArray[i];
                this.labArray[i] = tmp;
            }
        }
    }

    // Alternate implementation of selection sort using swap function 
    public void selectionA() {
        int tmp, tmp_idx;
        for (int i = 0; i < this.len - 1; i++) {
            tmp = this.labArray[i];
            tmp_idx = i;
            for (int j = i + 1; j < this.len; j++) {
                if (this.labArray[j] < tmp) {
                    tmp = this.labArray[j];
                    tmp_idx = j;
                }
            }
            swap(i, tmp_idx);
        }
    }

    public void insertion() {
        int j;

        for (int i = 1; i < this.len; i++) {
            for (j = i; j > 0 && this.labArray[j] < this.labArray[j - 1]; j--) {
                this.swap(j, j - 1);
            }
        }
    }

    public static void main(String[] args) {
        SortLab select = new SortLab();
        SortLab selectA = new SortLab();
        SortLab insert = new SortLab();

        System.out.println("Selection Sort");
        System.out.print("unsorted: ");
        select.display();
        select.selection();
        System.out.print("sorted:   ");
        select.display();
        System.out.println("SelectionA Sort");
        System.out.print("unsorted: ");
        selectA.display();
        selectA.selectionA();
        System.out.print("sorted:   ");
        selectA.display();
        System.out.println();
        System.out.println();
        System.out.println("Insertion Sort");
        System.out.print("unsorted: ");
        insert.display();
        insert.insertion();
        System.out.print("sorted:   ");
        insert.display();
    }
}

Output 1

run:
Selection Sort
unsorted: 4  7  2  6  1  5  3  9  8  0  
sorted:   0  1  2  3  4  5  6  7  8  9  
SelectionA Sort
unsorted: 1  3  9  6  8  7  5  4  2  0  
sorted:   0  1  2  3  4  5  6  7  8  9  


Insertion Sort
unsorted: 4  5  9  6  1  0  3  8  7  2  
sorted:   0  1  2  3  4  5  6  7  8  9  
BUILD SUCCESSFUL (total time: 0 seconds)

AP Exam

One way they may ask you about these sorts is to show you interim passes on the list and ask you what type of sort is being done. With a few simple additions our SortLab class can print out interim results to show you how this would look. By placing print statement at the end of the outer loop you can get a print out that shows you the developing sorted lists.

Look at the bottom of the outer loop in each of the 3 sort implementations. I have also added a fourth routine that implements insertion sort with an explicit shift of elements. Some practice exams implement insertion sort in this fashion. Take a look at the output trail it's operation is no different than the first insertion sort. But it uses an extra inner loop.

 public void selection() {
     int tmp, tmp_idx;

     for (int i = 0; i < this.len - 1; i++) {
         //select the ith element save value and index
         tmp = this.labArray[i];
         tmp_idx = i;
         // Check if selected is the lowest of the remaining array
         // if not switch them
         for (int j = i + 1; j < this.len; j++) {
             if (this.labArray[j] < tmp) {
                 // found something less save it and it's index
                 tmp = this.labArray[j];
                 tmp_idx = j;
             }
         }
         // if tmp_idx != i then swap the values (move the lowest val in)
         if (tmp_idx != i) {
             this.labArray[tmp_idx] = this.labArray[i];
             this.labArray[i] = tmp;
         }
         System.out.print("interim:  ");
         this.display();
     }
 }

 // Alternate implementation of selection sort using swap function 
 public void selectionA() {
     int tmp, tmp_idx;
     for (int i = 0; i < this.len - 1; i++) {
         tmp = this.labArray[i];
         tmp_idx = i;
         for (int j = i + 1; j < this.len; j++) {
             if (this.labArray[j] < tmp) {
                 tmp = this.labArray[j];
                 tmp_idx = j;
             }
         }
         swap(i, tmp_idx);
         System.out.print("interim:  ");
         this.display();
     }
 }

 public void insertion() {
     int j;

     for (int i = 1; i < this.len; i++) {
         for (j = i; j > 0 && this.labArray[j] < this.labArray[j - 1]; j--) {
             this.swap(j, j - 1);
         }
         System.out.print("interim:  ");
         this.display();
     }
 }

 public void insertionShift()
 {
     int j;
     int tmp;

     for (int i = 1; i < this.len; i++) {
         // take ith element find where it should be inserted
         tmp = this.labArray[i];
         for (j = i; j > 0 && this.labArray[j] < this.labArray[j - 1]; j--) {
             // no need to do anything
             // when the loop ends j will be the insertion position
         }
         // Shift elements from j to i-1 over 1
         for (int k = i - 1; k >= j; k--)
         {
             this.labArray[k + 1] = this.labArray[k];
         }
         this.labArray[j] = tmp;
         System.out.print("interim:  ");
         this.display();
     }
 }

 public static void main(String[] args) {
     SortLab select = new SortLab();
     SortLab selectA = new SortLab();
     SortLab insert = new SortLab();
     SortLab insertA = new SortLab();

     System.out.println("Selection Sort");
     System.out.print("unsorted: ");
     select.display();
     select.selection();
     System.out.print("sorted:   ");
     select.display();
     System.out.println("SelectionA Sort");
     System.out.print("unsorted: ");
     selectA.display();
     selectA.selectionA();
     System.out.print("sorted:   ");
     selectA.display();
     System.out.println();
     System.out.println();
     System.out.println("Insertion Sort");
     System.out.print("unsorted: ");
     insert.display();
     insert.insertion();
     System.out.print("sorted:   ");
     insert.display();
     System.out.println("Insertion Sort with Explicit Shift");
     System.out.print("unsorted: ");
     insertA.display();
     insertA.insertion();
     System.out.print("sorted:   ");
     insertA.display();
}

Output 2

run:
Selection Sort
unsorted: 9  6  2  1  3  7  8  4  0  5  
interim:  0  6  2  1  3  7  8  4  9  5  
interim:  0  1  2  6  3  7  8  4  9  5  
interim:  0  1  2  6  3  7  8  4  9  5  
interim:  0  1  2  3  6  7  8  4  9  5  
interim:  0  1  2  3  4  7  8  6  9  5  
interim:  0  1  2  3  4  5  8  6  9  7  
interim:  0  1  2  3  4  5  6  8  9  7  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
SelectionA Sort
unsorted: 9  0  5  7  2  8  4  3  1  6  
interim:  0  9  5  7  2  8  4  3  1  6  
interim:  0  1  5  7  2  8  4  3  9  6  
interim:  0  1  2  7  5  8  4  3  9  6  
interim:  0  1  2  3  5  8  4  7  9  6  
interim:  0  1  2  3  4  8  5  7  9  6  
interim:  0  1  2  3  4  5  8  7  9  6  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  


Insertion Sort
unsorted: 3  0  5  2  6  4  7  9  1  8  
interim:  0  3  5  2  6  4  7  9  1  8  
interim:  0  3  5  2  6  4  7  9  1  8  
interim:  0  2  3  5  6  4  7  9  1  8  
interim:  0  2  3  5  6  4  7  9  1  8  
interim:  0  2  3  4  5  6  7  9  1  8  
interim:  0  2  3  4  5  6  7  9  1  8  
interim:  0  2  3  4  5  6  7  9  1  8  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
Insertion Sort with Explicit Shift
unsorted: 1  9  3  8  5  7  6  4  0  2  
interim:  1  9  3  8  5  7  6  4  0  2  
interim:  1  3  9  8  5  7  6  4  0  2  
interim:  1  3  8  9  5  7  6  4  0  2  
interim:  1  3  5  8  9  7  6  4  0  2  
interim:  1  3  5  7  8  9  6  4  0  2  
interim:  1  3  5  6  7  8  9  4  0  2  
interim:  1  3  4  5  6  7  8  9  0  2  
interim:  0  1  3  4  5  6  7  8  9  2  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9    
BUILD SUCCESSFUL (total time: 1 second)

Conclusion

That's 2 of the 3 sorts you need to know about. Questions on the AP may show code and of course try to hide what is really going on. If there is an inner loop shifting multiple elements then placing the value in after the shift think insertion sort. The insertion sort above combines the compare and the shift together but the effect is the same. Selection sorts you should see a single swap of 2 values then back out to the main loop. I like to think of it as "select the lowest value and swap it to the current front of the line".

Merge Sort should be next but its implementation is simplified by recursion. So before we go into Merge Sort I want to revisit recursion in my next blog post. Then tackle merge sort. Then I will get back to finishing up blackjack.

You should also visit wikipedia they have some nice animations of how these sorts work.

References

  1. Aho, Alfred V., John E. Hopcroft, and Jeffrey D. Ullman. Data Structures and Algorithms. Reading, MA: Addison-Wesley, 1983.
  2. "Selection Sort." Wikipedia. Wikimedia Foundation, 25 Mar. 2013. Web. 26 Mar. 2013. http://en.wikipedia.org/wiki/Selectionsort
  3. "Insertion Sort." Wikipedia. Wikimedia Foundation, 22 Mar. 2013. Web. 26 Mar. 2013. http://en.wikipedia.org/wiki/Insertionsort
  4. Litvin, Maria, and Gary Litvin. Be Prepared for the AP Computer Science Exam in Java. Andover: Skylight, 2009.

Date: 2013-03-28T17:58-0400

Author: Nasty Old Dog