ArrayLinkedList Insertion Sort

Question

I have to do an Array List for an insertion sort and my teacher sent this back to me and gave me an F, but says I can make it up before Friday. I do not understand why this isn't an A.L insertion sort. Can someone help me fix this so it hits his criteria? Thanks.

HE SAID:

After checking your first insertion sort you all did it incorrectly. I specifically said to shift the numbers and move the number into its proper place and NOT SWAP THE NUMBER INTO PLACE. In the assignment in MySA I said if you do this you will get a 0 for the assignment.

 import java.util.ArrayList;

 public class AListINSSORT {

     private static void insertionSort(ArrayList<Integer> arr) {
          insertionSort();
     }

     private static void insertionSort() {
        ArrayList<Integer> swap = new ArrayList<Integer>();
        swap.add(1);
        swap.add(2);
        swap.add(3);
        swap.add(4);
        swap.add(5);

        int prior = 0;
        int latter = 0;

        for (int i = 2; i <= latter; i++)
        {
            for (int k = i; k > prior && (swap.get(k - 1) < swap.get(k - 2)); k--)  
            {
                Integer temp = swap.get(k - 2);
                swap.set(k - 2, swap.get(k - 1));
                swap.set(k - 1, temp);
            }
        }
        System.out.println(swap);
    }
 }

What is the point of the insertionSort(ArrayList<Integer> arr) method that completely ignores its argument? — khelwood
– khelwood, Commented Jan 27, 2016 at 14:11

w3re · Accepted Answer · 2016-01-27 14:18:20Z

2

First of all, it seems your teacher asked you to use a LinkedList instead of an ArrayList. There is quite a difference between them.

Secondly, and maybe more to the point. In your inner loop you are saving a temp variable and swapping the elements at position k - 2 and k - 1 with each other. From the commentary this is not what your teacher intended. Since he wants you to solve the problem with element insertion, I recommend you look at the following method definition of LinkedList.add(int i, E e): https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html#add(int,%20E).

This should point you in the right direction.

answered Jan 27, 2016 at 14:18

w3re

5824 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

JavAlex · Accepted Answer · 2016-01-27 14:18:37Z

1

As far as I see, your code does nothing at all. The condition of the outer for loop

for (int i = 2; i <= latter; i++)

is not fulfilled.

As you start with i = 2 and as latter = 0, it never holds i <= latter. Thus, you never run through the outer for loop and finally just give back the input values.

If you add the input values to swap in a different order (not already ordered), you will see that your code does not re-order them.

answered Jan 27, 2016 at 14:18

JavAlex

6,0442 gold badges15 silver badges14 bronze badges

1 Comment

JavAlex Over a year ago

Regarding "NOT SWAP THE NUMBER INTO PLACE", I think you wanted to do right. Your two for loops look as if you wanted to insert the number and not to swap it. Maybe, your teacher was just confused by the name swap of you list. So, think about just renaming it.

NickJ · Accepted Answer · 2016-01-27 14:38:13Z

There's a lot of stuff wrong here.

Firstly, your method:

private static void insertionSort(ArrayList<Integer> arr) {
   insertionSort();
}

takes an ArrayList and completely ignores it. This should presumably be the List which requires sorting.

Then in insertionSort() you create a new ArrayList, insert some numbers already in order, and then attempt something which looks nothing like insertion sort, but slightly more like bubble sort.

So, when you call insertionSort(List) it won't actually do anything to the list at all, all the work in insertionSort() happens to a completely different List!

Since on SO we don't generally do people's homework for them, I suggest looking at the nice little animated diagram on this page

What you should have then is something like:

public void insertionSort(LinkedList<Integer> numbers) {

   //do stuff with numbers, using get() and add()
}

Collectives™ on Stack Overflow

ArrayLinkedList Insertion Sort

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related