How Do I Implement an Insertion Sort Method for A Generic ArrayList?

by

I am meant to create a simple insertion sort method which sorts a series of generic names into alphabetical order. This should be simple, and I have already reviewed many other examples of insertion sort online, including on this site, yet I still cannot seem to obtain the correct output despite comparing my code, line-by-line, with other versions and being unable to identify what I have done different than some supposedly successful insertion sort methods.

The following code is the main class which I am not meant to alter:

  public static void main(String[] args) {
    GenericTools t = new ToolBox();
    ArrayList<String> data = new ArrayList<>();
    data.add("Carlos");
    data.add("Alice");
    data.add("Bob");
    data.add("Zebra");
    data.add("Fred");

    t.insertionSort(data);
    data.forEach(x -> System.out.println(x));
}

And, this is the GenericTools interface referenced above, for the record:

public <T> void swap(ArrayList<T> data, int p1, int p2);

Finally, this is my code which should be correctly sorting this list:

@Override
    public <T extends Comparable<T>> void insertionSort(ArrayList<T> data) {
        int i, x =0;
        T key;
        for (i=1;i<data.size();i++){
            key= data.get(i);
            while (x>=0 && data.get(x).compareTo(key) > 0){
                data.set(x+1,data.get(i));
                x--;
            }
            data.set(x+1,key);
        }
      }

However, instead produces the following output:

Fred
Alice
Bob
Zebra
Fred

As opposed to correct output of:

Alice
Bob
Carlos
Fred
Zebra

Leave a Comment