Вставка Сортировка в случае повторяющихся значений, дважды связанного списка ADT

Question

У меня возникла странная проблема с моей сортировкой вставки в случае повторных значений в хвосте входа. Самый простой случай, с которым у меня возникают проблемы, - это массив {A, A, A}. Поскольку я отслеживаю начальные индексы, я могу сказать, что это неправильно отсортировано так, что хранятся неправильные индексы, так что значения теряются. Вот реализация вставки рода:

List A = new List(); 
    String[] inputArray = {"A","A","A","A"}; 
    String key; 
    int i, j; 
    //begin insertion sort 
    for (j = 1; j < inputArray.length; j++) { 
     i = j - 1; 
     key = inputArray[j]; 
     while (i >= 0) { 
      if (key.compareTo(inputArray[i]) > 0) { 
       break; 
      } 
      inputArray[i+1] = inputArray[i]; 
      A.moveTo(i+1); 
      //make sure we aren't trying to insert before first node 
      if (i > 0) { A.insertBefore(i); } 
      else { A.prepend(i); } 
      //remove node at cursor 
      A.delete(); 
      i--; 
      System.out.println("inner: "+ A); 
     } 
     inputArray[i+1] = key; 
     A.moveTo(i+1); 
     if (i >= 0) { A.insertBefore(j); System.out.println("insert: " + A);} 
     else { A.prepend(j); System.out.println("prepend: " + A);} 
     System.out.println("current cursor:" + A.getIndex()); 
     A.delete(); 
     System.out.println("outer: " + A); 
    } 

С Println, что у меня есть в этом я получаю следующий вывод:

inner: 0 0 2 3 
prepend: 1 0 0 2 3 
current cursor:1 
outer: 1 0 2 3 //works fine the first time 
inner: 1 0 1 3 
inner: 0 1 1 3 
prepend: 2 0 1 1 3 
current cursor:1 
outer: 2 1 1 3 //deletes the wrong value? Why? 
inner: 2 1 1 2 
inner: 2 1 1 2 
inner: 0 2 1 2 
prepend: 3 0 2 1 2 
current cursor:1 
outer: 3 2 1 2 

Вот соответствующие части класса List:

class List { 

private class Node { 
    //Fields 

    int data; 
    Node next, previous; 
    //Constructor 

    Node(int data) { 
     this.data = data; 
     next = null; 
     previous = null; 
    } 

    public String toString() { 
     return String.valueOf(data); 
    } 
} 
//Fields 
private Node frontNode, backNode, cursorNode; 
private int totalSize, cursorPosition; 

//Constructor 
List() { 
    frontNode = backNode = cursorNode = null; 
    totalSize = 0; 
    cursorPosition = -1; 
} 

//length(): Returns number of elements in this list 
int length() { 
    return totalSize; 
} 

//getIndex: Returns the index of the cursor element in this list, or 
//returns -1 if the cursor element is undefined. 
int getIndex() { 
    return cursorPosition; 
} 
//prepend(int data): Inserts new element before front element in this List. 
void prepend(int data) { 
    Node node = new Node(data); 
    if (this.length() == 0) { 
     frontNode = backNode = node; 
    } else { 
     frontNode.previous = node; 
     node.next = frontNode; 
     frontNode = node; 
    } 
    totalSize++; 
    if (cursorPosition != -1) { 
     cursorPosition++; 
    } 
} 

//insertBefore(int data): Inserts new element before cursor element in this 
// List. Pre: length()>0, getIndex()>=0 
void insertBefore(int data) { 
    Node node = new Node(data); 
    if (this.length() > 0 && this.getIndex() >= 0) { 
     node.previous = cursorNode.previous; 
     node.next = cursorNode; 
     cursorNode.previous.next = node; 
     cursorNode.previous = node; 
     totalSize++; 
     cursorPosition++; 
    } else if (this.length() <= 0) { 
     throw new RuntimeException("Error: insertBefore called on empty list"); 
    } else { 
     throw new RuntimeException("Error: insertBefore called without cursor set"); 
    } 
} 

Answer 1

Нет необходимости изменять список внутри цикла while.

for (j = 1; j < inputArray.length; j++) { 
    i = j - 1; 
    key = inputArray[j]; 
    while (i >= 0) { 
     if (key.compareTo(inputArray[i]) >= 0) { 
      break; 
     } 
     inputArray[i+1] = inputArray[i]; 
     i--; 
    } 
    inputArray[i+1] = key; 
    A.moveTo(i+1); 
    A.insertBefore(j); // insert 'key' in right place 
    A.moveTo(j+1); 
    A.delete(); // remove old occurrence of 'key' 
} 

я заменил > с >=, чтобы сделать цикл прекращается, как только ключ больше, чем или равна текущего элемента. Таким образом, ключ будет вставлен после равных значений, а не раньше.

Предлагаю вам продлить insertBefore, чтобы вставить в начале, когда cursorPosition == 0. Это логическое расширение, которое устраняет особые случаи в алгоритме сортировки вставки.