Very frustrated noob: Insertsort on array, doubling array if it gets full

[Larry Marks]

Hello,
I have read through some of the posts on insert sort /arrays and see close but not exactly what I'm looking for. I don't want to use a library to do work for me, I want to do it myself and understand it.
I would like to see if anyone here can spare a few minutes looking and telling me:
1) Where my flaws are in the program.
2) what other flaws they see in my writing.
3) how they attack a problem, do they start with paper/pen ? Do they start with big items and work smaller or just start working it out on the keyboard?

Is there a written guide to a certain way of attacking a problem?


I have been working for hours trying to figure out these last few errors. Perhaps someone on these forums will help a little and not laugh too much. I have been in Java for a few weeks, and this is my first look at arrays.
I may have caused some damage by deleting stuff and starting over 3 or 4 times. ~I've spent maybe 20 hours trying to get this done. I know it is probably all of 30 min work for someone else, if that. Originally I tried writing a moving front end and back end, but that became way to complicated and I took out almost all of that code.

also: Do you normally attach code? or only paste it?
Thank you!
Larry

Note: When pasting in here, I deleted the print lines I used to see what was going on with. The only ones left are what I am trying to work into an error. That isn't important though, I can always delete that.

OrderedArrayList.java

// import static org.junit.Assert.assertEquals;

public class OrderedArrayList<T extends Comparable<T>> {

	// T is a variable that contains a class type, array of T things
	private T[] arrayA; // changed to private per example
	private T[] arrayB;
	int numElements = 0;		// number of elements full (not null), used in multiple methods. numElement -1 = back
	int frontArray = 0;		// Front of the Array, initially at element[0]. It can be expanded to move. -advanced use.
	int j;					// used often
	@SuppressWarnings("unchecked")
	/**
	 * Construct an OrderedArrayList with 10 empty slots. Note the recipe for 
	 * creating an array with the generic type. You'll want to reuse this 
	 * recipe in the insert() method.  You'll also possibly want to tweak this 
	 * constructor a bit if you add other instance variables.
	 */
	public OrderedArrayList() {
		arrayA = (T[]) new Comparable[10];
	}

	@SuppressWarnings("unchecked")
	/**
	 * _Part 1: Implement this method._
	 * 
	 * Inserts a new item in the OrderedArrayList. This method should ensure
	 * that the list can hold the new item, and grow the backing array if
	 * necessary. If the backing array must grow to accommodate the new item, it
	 * should grow by a factor of 2. The new item should be placed in sorted
	 * order using insertion sort. Note that the new item should be placed
	 * *after* any other equivalent items that are already in the list.
	 * 
	 * @return the index at which the item was placed.
	 *  
	 */
	public int insert(T item) {							// implemented

		if (arrayA[arrayA.length-1] != null){			// check if arrayA is full , last element full.
			arrayB = (T[]) new Comparable[(arrayA.length-1)*2];
			for (int k= frontArray; k < numElements-1; k++) {
				arrayB[k] = arrayA[k];
			}//for end
			arrayA = arrayB;
		}//if end arrayB
		if  (numElements<0){ 		// if numElements is 0, array elements are empty.
			if (arrayA[0]==null){
				arrayA[0] = item;
				numElements = 1;
				return 0;
			}
		}// if end, empty arrayA insert
		for (j=numElements-1; j>0 ; j--){ 		// check from the Array-2 (last element must be empty)
			if (item.compareTo(arrayA[j])>=0){		// if item should be added to the end.
				arrayA[j+1] = item;					// Add to last element +1
				numElements ++;
				return j+1;
			}
			arrayA[j+1] = arrayA[j];
			if (j==1){							// when all others have been moved, and item goes to left,
				arrayA[j] = arrayA[0];
				arrayA[0] = item;				//			item is placed in 0.
				numElements++;
				return 0;
			}
		}
		return -1;
	} // insert method end

	/**
	 * _Part 2: Implement this method._
	 * 
	 * @return the number of items in the list.
	 */
	public int size(){ 					// done returns number of full elements
		return numElements ;				// each insert will index numElements, remove will decrement numElements.
	}
	/**
	 * _Part 3: Implement this method._
	 * 
	 * Gets an item from the ordered array list. You can assume that this method
	 * will only be called with valid values of index. Specifically, values that
	 * are in the range 0 - (size-1). To impress your friends and build your
	 * street cred, consider adding checks that the index supplied is in fact in
	 * bounds. If it is not, you can raise an IndexOutOfBoundsException.
	 * 
	 * @param index
	 *            the index to get an item from
	 * @return 
	 * @return an item at the specified index
	 */
	public void indexOutOfBoundsException(){
		System.out.println("index() is incorrect. Index is between "+frontArray+" and "+numElements+".");
	}
	public T get(int index) {					// returns arrayA[index]
		if ((index >= numElements || index <frontArray) && index != 0){
			indexOutOfBoundsException();
		}
		// T getElement = arrayA[index];
		return arrayA[index];
	}
	/**
	 * _Part 3: Implement this method._
	 * 
	 * Counts the items in the ordered array list that are equal to the item at
	 * the specified index. Be sure to take advantage of the fact that the list
	 * is sorted here. You should not have to run through the entire list to
	 * make this count.
	 * 
	 * @param index
	 *            an index in the range 0..(size-1)
	 * @return the number of items in the list equal to the item returned by
	 *         get(index)
	 */
	public int countEquivalent(int index) {		// implemented
		int equivElements =1;
		for (int j=index; j>=1; j--){
			if (arrayA[j].compareTo(arrayA[j-1])==0){	// check below
				equivElements ++;						// add 1 to count
			}
		}
		for (int j=index; j<arrayA.length-2; j++){
			if (arrayA[j].compareTo(arrayA[j+1])==0){	// check below
				equivElements ++;						// add 1 to count
			}
		}
		return equivElements;				// return answer
	}

	/**
	 * _Part 4: Implement this method._
	 * 
	 * Finds the location of the first object that is equal to the specified
	 * object. Linear search is sufficient here, but feel free to leverage your
	 * binary search code too.
	 * 
	 * @param obj
	 *            an object to search for in the list
	 * @return the first index of an object equal to the one specified, or -1 if
	 *         no such object is found.
	 */
	public int find(T obj) {
		for (int j=frontArray;(j<=numElements);j++ ){
			if (obj.compareTo(arrayA[j])==0){
				return j;
			}
		}
		return -1;			// Can not use ("Did not find " +obj "."); return must be int only.
	}
	/**
	 * _Part 5: Implement this method._
	 * 
	 * Removes all the objects equal to the specified object.
	 * 
	 * @param obj
	 *            an object equal to the one(s) you'd like to remove
	 * @return the number of objects removed
	 */
	public int remove(T obj) {
		int removedArray =0;
		for (int j=frontArray;j<=numElements-1;j++ ){
			if (obj.compareTo(arrayA[j])==0){
				for (;j<=numElements-1;j++ ){
					arrayA[j] =arrayA[j+1];
				}
				arrayA[arrayA.length-1] = null;
				removedArray ++;
				numElements --;
			}
		}
		return removedArray;
	}
	/*public void testPrint(T item, int numElements,int j){
		System.out.println(arrayA[0] +" "+ arrayA[1]+" "+arrayA[2] +" "+arrayA[3] 
				+" "+arrayA[4]+" "+arrayA[5]+" 6: "+arrayA[6] +" "+arrayA[7]+" "+arrayA[8]+" "+arrayA[9]);
		System.out.println("test print. J= "+j+" "+"item = "+item);
		System.out.println(" ");
	}
	*/
	/**
	 * This method is included for testing purposes.
	 * Typically, you would not want to expose a private instance variable
	 * as we are doing here. However, it does have value when the code is 
	 * going through a testing phase. Do not modify or remove this method.
	 * Some WebCAT tests may rely upon it.
	 */
	public Comparable<T>[] dbg_getBackingStore() { return arrayA; } // had to rename array to arrayA else error
}

Second File for testing.


OrderedArrayListTests.java

import static org.junit.Assert.*;
import org.junit.Test;

public class OrderedArrayListTests {

	@Test
	public void construct() {
		OrderedArrayList<String> a = new OrderedArrayList<String>();
		assertEquals("Size should be 0 after construction!", 0, a.size());
	}
	@Test
	public void insertOneItem() {
		OrderedArrayList<String> a = new OrderedArrayList<String>();
		assertEquals("Size should be 0 after construction!", 0, a.size());
		a.insert("Hello!");
		assertEquals("Size should be 1 after one insert!", 1, a.size());
	}
	@Test
	public void findWithJustOneItem() {
		int i;
		OrderedArrayList<String> a = new OrderedArrayList<String>();
		a.insert("Hello!");
		i = a.find("Hello!");
		assertEquals("Can't properly find the only string that should be in the list!", 0, i );
		i = a.find("Hellooooooooo!");
		assertEquals("find() expecting -1, but got something else", -1, i );
	}
	@Test
	public void removeWithJustOneItem() {
		int i;
		OrderedArrayList<String> a = new OrderedArrayList<String>();
		a.insert("Hello!");
		i = a.find("Hello!");
		assertEquals("Can't properly find the only string that should be in the list!", 0, i );
		i = a.remove("Hel"+"lo!");
		assertEquals("remove() expecting 1, but got something else", 1, i );
	}
	@Test
	public void removeWithTwoDifferentItems() {
		int i;
		OrderedArrayList<String> a = new OrderedArrayList<String>();
		a.insert("Hello!");
		a.insert("Zeno.");
		i = a.find("Hello!");
		assertEquals("Can't properly find the only string that should be in the list!", 0, i );
		i = a.remove("Hel"+"lo!");
		assertEquals("remove() expecting 1, but got something else", 1, i );
	}
	@Test
	public void removeWhenThereAreDuplicates() {
		int i;
		OrderedArrayList<String> a = new OrderedArrayList<String>();
		a.insert("Hello!1");
		a.insert("Hello!2");
		a.insert("Hello!3");
		a.insert("Zeno.");
		a.insert("Abacus");
		i = a.find("Hello!");
		assertEquals("find() :: doesn't find the first occurance!", 1, i );
		i = a.remove("Hel"+"lo!");
		assertEquals("remove() expecting 3, but got something else", 3, i );
	}
	@Test
	public void testCounting() {
		int i;
		
		OrderedArrayList<String> a = new OrderedArrayList<String>();
		a.insert("Hello!");
		a.insert("H"+"ello!");
		a.insert("Hell"+"o!");
		a.insert("Zeno.");
		a.insert("Abacus");
		assertEquals("size() is incorrect.", 5, a.size());
		assertEquals("insert() placed an item incorrectly or get() is broken", "Abacus", a.get(0));
		assertEquals("insert() placed an item incorrectly or get() is broken", "Hello!", a.get(1));
		assertEquals("insert() placed an item incorrectly or get() is broken", "Hello!", a.get(2));
		assertEquals("insert() placed an item incorrectly or get() is broken", "Hello!", a.get(3));
		assertEquals("insert() placed an item incorrectly or get() is broken", "Zeno.", a.get(4));
		assertEquals("countEquivalent() is broken or insert isn't working correctly.", 1, a.countEquivalent(0));
		assertEquals("countEquivalent() is broken.", 3, a.countEquivalent(1));
		assertEquals("countEquivalent() is broken.", 1, a.countEquivalent(4));
		
		i = a.find("Hello!");
		assertEquals("find() :: doesn't find the first occurance!", 1, i );
		i = a.remove("Hel"+"lo!");
		assertEquals("remove() expecting 3, but got something else", 3, i );
	}

}

[Junilu Lacar]

One of the best ways to improve a program is to refactor complicated logic into Composed Methods. This example does some of what you want to do. Notice how clean and understandable the refactored version of the code is.

[Junilu Lacar]

Your insertion sort code seems way more complicated than it needs to be. You can find pseudocode of the algorithm on the Internet and it's much shorter than what you've come up with.

[Larry Marks]

Thank you for the answer. I'll take a look at that web page some more. I've only looked a little at it and I don't understand it yet. I don't know much of the vocabulary yet.
One part of the program I have trouble with is compareTo.
I need to compare what I am inserting to each of the values down the line, but if any are null it messes things up. I assume compareTo cannot compare something to null, correct? So I keep adding if statements to only look at non-null elements. is there a better way to do this? (While still being simple). I wish i knew how to debug in eclipse but my instructor says that isn't part of the course. I'm trying to learn from youtube, ill spend a few more hours on it tomorrow but I can't neglect other work.

Thanks for your help.

[Campbell Ritchie]

… and welcome to the Ranch

[Andrew Kenyon]

Larry Marks wrote:

3) how they attack a problem, do they start with paper/pen ? Do they start with big items and work smaller or just start working it out on the keyboard?

Personally, I make sure I understand the problem as best as I can before trying to implement a solution. In this case, that may mean sitting down with
a pen and paper, writing a "random" sequence of 5 - 10 integers, and then stepping through the pseudo-code of the insertion sort algo. At each iteration
you'll mark exactly where the loop pointers are pointing, note when you've found the correct insert location for the integer (and how you knew that), then
manually shift however many integers are required to their new location, etc...

Then, I would implement the algorithm in the absolute simplest code possible (i.e. forget about generics, implementing Comparable, writing test code
before you even understand how the code is supposed to execute properly, dynamically resizing arrays, input validation, etc...). If the bare bones
implementation works as you expected it to (based on your whiteboard/notebook practice stepping through the algo), THEN comment it very well so
that Future Larry will still love you (Present Larry) when he has to read it again at some point.

Now, if you need to implement additional bells and whistles then introduce them one at a time, making sure you completely understand (and test) them
as you go along. That way if it doesn't work, you know exactly which changes are causing the issue. Trying to implement two (or more) features into your code
before you understand what you are doing is just asking for frustration. Tomorrow-morning-Larry (the one who got some sleep tonight because he sensibly implemented
one new feature at a time) will be very appreciative of you for sticking to this process.

And, now I've got about 15 minutes to get to class, so I'll sign off here.

Good luck!

[Stefan Evans]

Here is a test to help you fix your bug:

    @Test
    public void testInsertingIntoAnEmptyListInsertsTheELementAtPosition0(){
      OrderedArrayList<String> a = new OrderedArrayList<String>();
      assertEquals("Element should be inserted at index 0", 0, a.insert("Hello!"));
    }

[Stefan Evans]

Ok, some initial comments from reviewing your code:
Here are some things I think you can improve on

#1: Scope of variables
You have a bunch of effectively "global" variables at the top of your class. Variables should be declared to the minimum scope possible. The main one I have an issue with is the array counter "j". Best practice with arrays is to declare the array counter as part of the loop:
i.e. for (int j=0; j<array.length; j++)
Why do you have two arrays declared here? The only place I can see arrayB used is when you are copying values from one array to another after 'growing'.

#2: Write a toString method so you can easily examine the contents of your array for debugging (Ok, I see something similar there commented out)

#3: Some of your tests are testing multiple things. Best practice is to have each unit test test one process/thing. Tests that tests too much are hard to debug. For instance your testCounting method is also testing removing from the list.

Oh, and here are a couple more tests for ya.

    @Test
    public void testSizeDoublesWhenFull(){
      OrderedArrayList<String> a = new OrderedArrayList<String>();
      a.insert("1");
      a.insert("3");
      a.insert("5");
      a.insert("7");
      a.insert("9");
      a.insert("2");
      a.insert("4");
      a.insert("6");
      a.insert("8");
      a.insert("0");
      assertEquals(10, a.getCapacity());  // a.getCapacity returns how many items CAN be in this list. 
      a.insert("11");
      assertEquals(20, a.getCapacity());
    }

    @Test
    public void testInsertingAtStartOfList(){
      OrderedArrayList<String> a = new OrderedArrayList<String>();
      a.insert("5");
      a.insert("3");
      assertEquals("3", a.get(0));
    }