Реализация алгоритма сортировки Шелла в связанном списке ⇐ JAVA

[Anonymous]

Я работаю над проектом для своего класса структур данных, в котором мне нужно реализовать алгоритм сортировки Shell в связанном списке. Ранее мы делали это, используя список массивов, и когда были введены 10 000 случайных целых чисел, моей программе потребовалось в среднем 0,012 секунды, чтобы отсортировать список. Теперь, когда я реализовал тот же алгоритм, используя DS со связанным списком, я сделал его в среднем около 20,1 секунды (угу). Мне интересно, это нормально или это как-то связано с самой реализацией? Вот основная часть алгоритма, в которой в качестве значений пробела используется последовательность Кнута:

Код: Выделить всё

while(k >= 1) {
for (int i = k; i < theList.size(); i++) {
int j = i;
while (j >= k && theList.get(j - k).compareTo(theList.get(j)) > 0) {
T smaller = theList.delete(j);
theList.add(j - k, smaller);

T larger = theList.delete(j - k + 1);
theList.add(j, larger);

j -= k;
}
}

Я попробовал использовать метод подкачки, чтобы поменять местами два сравниваемых значения, но это, похоже, не помогло. Я также попробовал провести рефакторинг методов get(), add() и delete() для LinkedList, но это тоже ничего не дало.

Подробнее здесь: https://stackoverflow.com/questions/778 ... inked-list