2014-12-03 COMPETITION!

posted Dec 2, 2014, 10:23 PM by Samuel Konstantinovich   [ updated Dec 2, 2014, 10:23 PM ]
Document means you need to write it down in a place I can look at. 
If you don't have EXPLICITLY written explanations, then <insert amusing but serious threat>.

1. Please verify that your insertionSort() DOES in fact work by testing it. Are you sure it worked?  Document how you did this. 
Hint: Arrays.sort() is guaranteed to work. 

2. Please compare the speed of your insertionSort() to this version of insertionSort:
public void badInsertionSort(){
        OrderedSuperArray c = new OrderedSuperArray();
        while( this.size() > 0){ 
            c.add(this.remove(0));
        }
        while(c.size() > 0){
            this.add(c.remove(0));
        }
}

2a. You need to devise a simple, but robust testing methodology, then apply it to the two sorts. Document how you did this. 
2b. If your insertion sort is SLOWER than the badInsertionSort(), then you did something wrong! Go fix it. 

3. In class you can compare with others to see how fast is possible. You cannot compare your insertion sorts against each other on different machines. Instead see how much faster (as a %) your insertion sort is compared to the bad one (on the same size data set, using the same testing methodology).  

3b. Nominate one student to log the times of the top 5 fastest versions, and the name of the students that wrote it. Students should verify the top 5 fastest ones work, because you can sort poorly VERY fast.

Homework:
4. Please compare your OrderedSuperArray to the one at the end of the post. This is to help you understand by reading (hopefully) good code.  



/*++++++++++++++++++++++++++++++++++++++++++++++*/

Solution to OrderedSuperArray:

public class OrderedSuperArray extends SuperArray{

    public void add(String o){
        int index = size();
        while( index >0 && get(index-1).compareTo(o) > 0 ){
            index--;
        }
        super.add(index, o);
    }

    public void add(int index, String o){
        add(o);
    }

    public String set(int index, String o){
        //this is the lazy way, but a good start.
        //This commented out code makes 2 linear passes:
        /*
          String old = remove(index); //remove is linear...
          add(o);//add is linear...
          return old;

        */


        //replacing that code with this code, means you only do 1 linear pass:
        String old = data[index];
        if(size() == 0){ //Included so that you cannot try it on an empty list.
            throw new IndexOutOfBoundsException("" + index);
        }

        //decide if you need to shift left or right, you do EITHER, or none.
        if(o.compareTo(data[index]) > 0){ //move it to the right
            //at least one item left && the next item is smaller
            while(index < size() - 1 && o.compareTo(get(index + 1)) > 0 ){
                //shift the element
                data[index] = data[index+1];
                index++;
            }
        }else if(o.compareTo(data[index]) < 0){//move it to the left
            while(index > 0 && o.compareTo(get(index - 1)) < 0 ){
                data[index] = data[index-1];
                index--;
            }
        }
        data[index] = o;
        return old;
    }
    //Writing the code to save 1 linear pass may not be worth it...
    //in fact in this case it probably isn't! This method is challenging for several reasons.


    //P.S. A bug in my code (I copy pasted a while loop, changed the < to >,
    //but don't change the ++ to --) resulted in 15 minutes of testing.
    //Next time you face a hard problem, realize that NOBODY gets
    //everything right away all the time.
}
Comments