Need assistance with an insertionsort program

Question

I've been working on this program for school, and I'd nearly completed it when I saw the instructions had a little bit I hadnt noticed. I'm so POed right now, and I'd love someone to help... Seriously, I'm one step away from trashing this comp. Here's the instructions and examples:

Input the data file and sort them using an “insertionSort” algorithm in a method called “sortNames()”. Then take a group of Strings and organize them alphabetically. As you add new items, maintain the sorted order of the list. New items should always be added in a way that maintains the sorted order of the list.

The data file is this list of names (just stacked like this):

Cole

Emma

Spencer

Matthew

Carter

Robert

Zachary

Connor

Christian

Brixton

Adam Loc

Aidan

Michael

Trenton

Jake

Dallas

Westin

Jonathan

Connor

Priya

Edmund

Zachary

Areli

Connor

Beverly

The part of the instructions I didnt notice was this (it was at the bottom):

You may NOT use Arrays.sort( ) or Collections.sort( ) !

Anyway, here is the skeleton code provided:

import java.util.ArrayList;
import java.util.Collections;
import static java.lang.System.*;

class InsertionSort
{
    private ArrayList<String> list;

    public InsertionSort()
    {
    }

    //modfiers
    public void add( String  word)
    {
        int loc = 0;
    }

    private int findInsertLocation( String word )
    {
      return -1;
    }

    public void remove(String word)
    {
    }

    public String toString()
    {
        return "";
    }
}

If someone can fill out the skeleton code, I can make the runner, so I can actually say I've done some of the work.

I know I sound like a whiny brat "oh it's too hard so I'll be lazy and ask other people to do it" but I'm not. I worked on it for about an hour and a half, and it's just aggravating now. I've just started computer science, this is my first year, but I really am crap at sorts of all kinds. Please help me.

Thanks,

Keelen

EDIT: What I meant was I am putting out what my teacher gave me. Sorry I mislabeled it skeleton code. My problem is inserting the .dat file using an insertion sort. The way it's phrased leads me to believe it wants me to sort it and overwrite the data file. So the code would just work in teh data file, then overwrite it with the sorted version. This is way beyond anything I've done before, my biggest code project before this was making a rock paper scissors game. And no, it did not take me an hour and a half for the blank code, I was saying the way I did it didnt work, so I was giving a blank slate. Sorry.

Answer 1

"but I really am crap at sorts of all kinds"

What you are not doing here is helping yourself. Getting other people to do your work for you is not going to make you any better.

A good place to start learning about insertion sort would be the Wikipedia article. But because you seem like you're in a hurry, I'll summarize here.

Say you start off with this random array:

[ 4, 2, 5, 7, 3 ]

The general idea behind insertion sort is that you want to split your array into two sections -- the sorted section and the unsorted section. Every iteration, you pick the first element in the unsorted portion and then insert it into its proper position in the sorted portion of the array.

So to begin, you have this, where the | represents the split between sorted and unsorted portions, with the sorted portion on the left:

[ | 4, 2, 5, 7, 3]

First you take the first element in the unsorted element in the unsorted array and move it into its proper position in the sorted portion of the array. This is easy, because there is nothing else in the array:

[ 4 | 2, 5, 7, 3 ]

Then you repeat:

[ 2, 4 | 5, 7, 3 ]
[ 2, 4, 5 | 7, 3 ]
[ 2, 4, 5, 7 | 3 ]
[ 2, 3, 4, 5, 7 | ]

And now you're done! Turning this into code shouldn't take anything more than some loops, swaps, and if statements.

This should be enough to get you started. If you try implementing something and there's a specific thing you're stuck on, try posting here again.