Реализация SelectionSort, способная обрабатывать список массивов, связанный список и дважды связанный список в java

ПРЕДПОСЫЛКА: Я хочу реализовать сортировку выбором, способную обрабатывать список массивов, связанный список и двусвязный список. Для каждого типа списка у меня есть класс position{} и list{}. Класс position{} — это то, что содержит список (т. е. класс position{int head; list tail;}). Хотя СПИСОК{} содержит методы next(), previous(), end(), Insert(), first() и использует position{}, он не содержит самого класса списка, самого класса списка, который создает список. называется позицией класса{}.

ВОПРОС: Моя проблема не в том, чтобы сделать сортировку выбором совместимой, я достиг этого, используя только команды, которые являются общими для трех абстрактных типов данных списка. Моя проблема заключается в том, что моя сортировка выбором возвращает тот же список и не выполняет никакой сортировки. Список, напечатанный после сортировки, совпадает со списком, напечатанным до сортировки. Любая помощь приветствуется.

вывод до сортировки выбором 2 879 621 229 702 40 243 312 247 46 711 241 после сортировки выбором 2 879 621 229 702 40 243 312 247 46 711 241

Мой список ADT правильный, проблема заключается в моей плохой сортировке выбора.

public static void SelectionSort(LIST A) { 
        POSITION i, j, maxp, temp;
        for(i = A.Previous(A.End()); !i.isEqual(A.First()); i = A.Previous(i)) {
            maxp = i;
            for(j = A.First(); !j.isEqual(i); j = A.Next(j))  {
                if((Integer)A.Select(j) > (Integer)A.Select(maxp)) {
                    maxp = j;
                }     
            }   
            temp = i;
            A.Insert(i, A.Select(maxp));
            A.Insert(maxp, A.Select(temp));
            A.Delete(maxp);
            A.Delete(i);
        }
    }

java list arraylist doubly-linked-list selection-sort
person Braithe Warnock    schedule 15.04.2014    source источник

Ответы (4)


arrow_upward
1
arrow_downward

Сначала вы вставляете что-то в индекс i, затем вставляете что-то в индекс maxp, затем удаляете что-то в индексе maxp, а затем удаляете что-то в индексе i. Предполагая, что Insert() и Delete() делают то, что подразумевают их имена, эта последовательность операций оставляет ваш список в исходном состоянии после каждой итерации цикла, поскольку удаления отменяют вставки.

В качестве примечания: этот код не соответствует соглашениям об именах Java, что делает его труднее для чтения, чем нужно.

person Michał Kosmulski    schedule 15.04.2014
comment
Я вставляю и удаляю, потому что, вставляя, я заставляю список расти, я не хочу этого, я хочу, чтобы список оставался того же размера. Поэтому я должен прикрепить удаление к каждой вставке. Кстати, использование метода replace() дает тот же результат - person Braithe Warnock; 15.04.2014
comment
@BraithWarnock Но если вы что-то вставите, а затем удалите, вы окажетесь там же, где и начали. Вы должны удалить другой индекс, чем тот, в который вы вставляете, или изменить порядок операций (поскольку вы вставляете в список, один и тот же индекс указывает на разные записи в разное время) - person Michał Kosmulski; 16.04.2014

arrow_upward
0
arrow_downward

Как работают методы Insert, Select и Delete? Возможно ли, что Delete удаляет элемент, который вы только что Inserted?

Вы убедились, что оператор isEqual (и упомянутые выше методы) ведет себя так, как ожидалось?

Из вашего алгоритма я делаю вывод, что происходит следующее:

  • you loop over all the elements, starting at the second last, moving towards the front.
    • Locate the maximal element in the subset from 0 to i
    • Вставить максимальный найденный элемент (по индексу maxp) в массив по индексу i
    • Вставьте элемент, первоначально с индексом i, обратно в массив в позицию, первоначально занятую maxp
    • Удалите i и maxp

Во-первых, зачем вам удалять элементы? Insert дублирует элемент? Если вы вызовете Delete для списка с двумя экземплярами элемента, который вы пытаетесь удалить, какой из них он удалит? Первый? Это то, что вы хотите?

Возможно, вам нужен новый метод Replace, который вместо этого заменяет элемент с заданным индексом. Тогда вам не нужно было бы удалять его после. Еще лучше был бы метод Swap, который меняет местами 2 элемента в списке.

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

person Trenin    schedule 15.04.2014
comment
Вот что я знаю: Insert действительно вставляет НОВЫЙ узел/позицию в список, и это причина моего удаления. Каждый раз, когда я вставляю в список, я увеличиваю количество элементов в списке, поэтому каждая вставка должна сопровождаться соответствующим удалением. Только LIST ADT имеет метод замены, а не список массивов или двойной связи. Что делает алгоритм, так это видит, какая POSITION содержит самый высокий элемент, затем он меняет местами ЭЛЕМЕНТЫ в позиции, поэтому сначала сортировка выбора сравнивает позиции, а затем меняет местами элементы в позиции BTW, я пытался использовать замену, те же результаты - person Braithe Warnock; 15.04.2014

arrow_upward
0
arrow_downward

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

Также будьте осторожны, удаляя правильный элемент. Если вы вставляете перед удалением, то правильный индекс для удаления может быть сдвинут на единицу, если вставка была до этой позиции.

person Jon B    schedule 15.04.2014
comment
Я попробую это, каждый раз, когда я вставляю максимальную позицию, я вставляю 879, что означает, что мой поиск самого высокого значения снова подбирает самые высокие элементы, когда он должен отбрасывать его в конце списка, а затем не искать этот конец списка список для самых высоких - person Braithe Warnock; 15.04.2014

arrow_upward
0
arrow_downward

Это правильный ответ, мне потребовался ясный ум, вероятно, вызванный хорошей чашкой чая, чтобы, наконец, разобраться во всем... Мои методы вставки и удаления были просто неправильными, одно небольшое изменение и валлах. ваше здоровье. Спасибо за все отклики.

public static void SelectionSort(LIST A) { 
    POSITION i, j, maxp, temp;
    for(i = A.Previous(A.End()); !i.isEqual(A.First()); i = A.Previous(i)) { 
        maxp = i;
        for(j = A.First(); !j.isEqual(i); j = A.Next(j))  {                  
            if((Integer)A.Select(j) > (Integer)A.Select(maxp)) {             
                maxp = j;
            }     
        }   
        temp = i;
        A.Insert(A.End(), A.Select(maxp));
        A.Delete(A.Previous(A.End()));
        A.Insert(maxp, A.Select(temp));
        A.Delete(temp);
    }
}
person Braithe Warnock    schedule 16.04.2014