How do I get insertion sort to work with a doubly linked list

Joseph Campbell Published at Dev

Joseph Campbell

I cannot get this method to sort the Doubly Linked List from least to greatest.

My input is : MyLinkedList: 3.0, 4.0, 2.0, 69.0, 76.0, 22.0, 341.0, 15.0

public void insertionSort(Comparator<? super E> compare) {
DLinkedNode<E> tempI = head.next;    
for (int i = 1; i < size  && tempI.next != null; i++) {      
  E temp = tempI.data;
  int j;
  DLinkedNode<E> tempJ = tempI.prev;
  for (j = i-1; j >= 0 && tempJ.prev != null; j--) {        
    if (compare.compare(tempJ.data, temp) <= 0){
      printLinkedList();
      System.out.println("");
      tempJ.next.data = tempJ.data;                  
    }
    tempJ = tempJ.prev;//j--;          
  }//end for
  tempJ.next.data = temp;      
  tempI = tempI.next;//i++;            
}//end for    
}// end insertionSort

The output after each iteration of the inner for loop is:

MyLinkedList: 3.0, 2.0, 2.0, 69.0, 76.0, 22.0, 341.0, 15.0
MyLinkedList: 3.0, 2.0, 2.0, 2.0, 76.0, 22.0, 341.0, 15.0
MyLinkedList: 3.0, 69.0, 2.0, 2.0, 76.0, 22.0, 341.0, 15.0
MyLinkedList: 3.0, 69.0, 2.0, 2.0, 2.0, 22.0, 341.0, 15.0
MyLinkedList: 3.0, 69.0, 2.0, 2.0, 2.0, 22.0, 341.0, 15.0
MyLinkedList: 3.0, 76.0, 69.0, 2.0, 2.0, 22.0, 341.0, 15.0
MyLinkedList: 3.0, 76.0, 69.0, 2.0, 2.0, 2.0, 341.0, 15.0
MyLinkedList: 3.0, 22.0, 69.0, 2.0, 2.0, 2.0, 341.0, 15.0
MyLinkedList: 3.0, 22.0, 69.0, 2.0, 2.0, 2.0, 2.0, 15.0
MyLinkedList: 3.0, 22.0, 69.0, 2.0, 2.0, 2.0, 2.0, 15.0
MyLinkedList: 3.0, 22.0, 69.0, 2.0, 2.0, 2.0, 2.0, 15.0
MyLinkedList: 3.0, 22.0, 69.0, 69.0, 2.0, 2.0, 2.0, 15.0
MyLinkedList: 3.0, 341.0, 22.0, 69.0, 2.0, 2.0, 2.0, 15.0

comparable method is:

public class DoubleComp implements Comparator<Double> {
  public int compare(Double a1, Double a2) {
  double foo = ((double) a1 - (double) a2);
  return (int) foo;
  }
}

Ivan Zaitsau

Use Double.compare(double d1, double d2) to compare doubles if you are using JDK 7 or later.

Sorting looks really messed up. Try using the following approach:

Node root; Comparator comp;
Node current = root;
while (current.next != null) {
    E data = current.data;
    Node i = current;
    while (i.previous != null && comp.compare(data, i.previous.data) < 0) {
        i.data = i.previous.data;
        i = previous;
    }
    i.data = data;
    current = current.next;
}

Collected from the Internet

Please contact [email protected] to delete if infringement.