Writing Insertion Sort with ListIterator

Question

I am trying to write an insertion sort method that takes in a list of Integers and sorts it in increasing order by using ListIterator. I tried running the method on my main method to see if it has worked but, I end up with a bunch of errors. I would like to know what mistakes I have made and how you would write the code. Here is the method:

public static void insertionsort(LinkedList<Integer> arr){
ListIterator<Integer> it = arr.listIterator();
while(it.hasNext()){
  while(it.hasPrevious()){
    Integer curr = it.next();
    it.previous();
    Integer prev = it.previous();
    if(curr<prev){
      it.set(curr);
      it.next();
      it.next();
      it.set(prev);
    }
  }
  it.next();
}

}

Here is the main method:

public static void main(String[] args){
LinkedList<Integer> a = new LinkedList<Integer>();
a.add(40);
a.add(30);
a.add(20);
a.add(10);
a.add(5);
insertionsort(a);
ListIterator<Integer> i = a.listIterator();
while(i.hasNext()){
  System.out.println(i.next());
}

}

you should read this https://stackoverflow.com/a/2599114/9050514 — deadshot, May 23 '20 at 03:49

ccamcmxc · Accepted Answer · 2020-05-23T05:48:50.403

When this condition

curr<prev

is not met you go into an infinite loop because you are leaving the cursor at the same place.

You could do something like this although not very efficient (but still insertion sort), but very easy to understand:

    ListIterator<Integer> iter = arr.listIterator();
    Integer current = iter.next();
    Integer next = null;
    while (iter.hasNext()) {
        if (!iter.hasPrevious() && next != null) {
            //insertion into sorted sublist
            while (iter.hasNext() && iter.next() < next) ;
            iter.previous();
            iter.add(next);
        }
        next = iter.next();
        //nothing to do, keep going
        if (next >= current) {
            current = next;
        } else {
            //remove misplaced element, and check where to put it
            iter.remove();
            //we can go backwards and check or move to the beginning and keep checking
            iter = arr.listIterator();
            current = next;
        }
    }

Writing Insertion Sort with ListIterator

1 Answers1