Мой метод SelectionSort не работает.Зачем? - PullRequest
Новая
       12

Мой метод SelectionSort не работает.Зачем?

1 голос
/ 29 апреля 2011

Я пытаюсь использовать алгоритм сортировки выбора в версии двусвязного списка, который я написал сам. По этому вопросу мы можем предположить, что в другом месте, кроме кода, который я публикую, нет ошибок (по крайней мере, нет ни одного, имеющего отношение к вопросу). Я сделал много испытаний.

вот мой метод: 

public void selectionSort(){

    ListItem front = head;
    ListItem current;
    T currentLowest;
    T potentialLowest;
    int lowestIndex = 0;
    for (int a = 0; a<count-1; a++){
        System.out.println("a: "+a);
        currentLowest = (T) front.content;
        front = front.next;
        current = front.next;
    for(int i = a+1; i<count; i++){
        System.out.println("i: "+i);
**(29)**    potentialLowest = (T) current.content;
        if (potentialLowest.compareTo(currentLowest)==-1)
        {
            currentLowest = (T) current.content;
            lowestIndex = i;
        }
        if(current.next == null)break;

        current = current.next;
    }
    System.out.println("swapped"+a+","+lowestIndex);
    swap(a, lowestIndex);
}

}

Это сортировка списка из 100 целых чисел. Вот последний бит вывода, прежде чем я получу нулевой указатель в строке 29 (помечено).

swapped95,97

а: 96 я: 97 я: 98

swapped96,97

а: 97 я: 98

swapped97,97

а: 98 я: 99 (нулевой указатель)

У меня раньше это работало, но оно было ужасно оптимизировано. После внесения некоторых изменений я застрял с этим. Есть идеи?

Спасибо за ваше время.

Ответы [ 2 ]

1 голос
/ 29 апреля 2011

Ну, вы пытаетесь получить доступ к содержимому нулевого элемента.Когда вы переходите к последнему элементу, ваш «текущий» будет нулевым, когда вы установите его на следующий.сравните ваш старый (рабочий) код с ним и найдите исправление.

0 голосов
/ 29 апреля 2011

Я думаю, что проблема может возникнуть в первой итерации цикла сортировки.Учитывая, что первая строка в этой функции (ListItem front = head) указывает front на первый элемент списка, кажется, что, вызывая: front = front.next; current = front.next; , вы фактически «пропускаете» элемент с индексом 1 в списке и начинаетецикл сравнения элемента с индексом 2.

Например, если ваш (несортированный) список выглядит так:

[54, 11, 25, 34]

Он будет выглядеть как

[25, 11, 54, 34]

после первой итерации вашего алгоритма сортировки.Поскольку следующая итерация начнется с индекса 1, элемент 11 никогда не будет помещен в индекс 0, даже если он является самым низким элементом в списке.

Возможно, именно эта неточность вызывает проблему нулевого указателя вконец списка.Я бы посоветовал поместить оператор front = front.next; после во внутренний цикл for и перед оператором swap(a, lowestIndex);.Это предотвратит возможную ошибку в первой итерации и может решить вашу проблему.

...