Вариант SelectionSort не работает

Я должен реализовать сортировку выбором в Java в соответствии с этими параметрами:

Реализуйте вариант SelectionSort, который находит как самые маленькие, так и самые большие элементы при просмотре списка и размещает их в начале и конце списка соответственно. На первом проходе сканируются элементы x0,...,xn-1; на втором проходе сканируются элементы x1,...,xn-2; и так далее.

Я передаю методу массив размером 32, и когда я печатаю массив, он не сортируется. Что случилось с моим кодом?

static void selectionSort() {
    scramble();
    int smallIndex = 0;  //index of smallest to test
    int largeIndex = array.length - 1;  //index of largest to test
    int small = 0;  //smallest
    int large;  //largest
    int smallLimit = 0;  //starts from here
    int largeLimit = array.length - 1;  //ends here
    int store;  //temp stored here
    int store2;

    for(int i = 0; i < array.length/2; i++) {  //TODO not working...
        small = array[smallLimit];
        large = array[largeLimit];
        for(int j = smallLimit; j <= largeLimit; j++) {
            if(array[j] < small) {
                smallIndex = j;
                small = array[j];
            }
            else if(array[j] > large) {
                largeIndex = j;
                large = array[j];
            }
        }
        store = array[smallLimit];
        store2 = array[smallIndex];
        array[smallLimit] = store2;
        array[smallIndex] = store;
        store = array[largeLimit];
        array[largeLimit] = array[largeIndex];
        array[largeIndex] = store;
        smallLimit++;
        largeLimit--;
    }
    print();    
}

java arrays sorting selection-sort
person cMarsh    schedule 11.11.2014    source источник
comment
См. J.B. Hayfron-Acquah, Obed Appiah K. Riverson: Improved Selection Sort Algorithm для ссылок (и улучшенную сортировку O(n) пробелом). Дубликат сортировки выбором изменен, более или менее.   -  person greybeard    schedule 23.01.2016

Ответы (2)


arrow_upward
1
arrow_downward

Подумайте о крайних случаях: что происходит, когда самый большой или самый маленький элемент находится в smallLimit или largeLimit. Когда это происходит, у вас есть две проблемы:

  1. largeIndex и smallIndex не установлены. Они сохраняют свои значения из предыдущей итерации.
  2. Замена самого маленького предмета на его правильное место перемещает самый большой предмет. Второй обмен перемещает самый маленький элемент туда, где должен быть самый большой, а самый большой оказывается в случайном месте. Пройдитесь по коду на бумаге или в отладчике, если вам сложно это представить.

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

  • Используйте меньше движущихся частей. Вы всегда можете получить значение small, используя smallIndex, если бы вы просто использовали smallIndex, не было бы опасности того, что разные переменные выпадут из шага.
  • Объявите переменные в минимально возможной области. Если бы smallIndex было объявлено в теле цикла, а не снаружи, компилятор сказал бы вам, что есть вероятность, что оно не было установлено до замены.
  • Деструктивные обновления, такие как первый обмен здесь, всегда могут сделать предыдущий расчет устаревшим. Если вы не можете избежать этого, поищите, как два обновления могут наступить друг другу на пятки.
person Joni    schedule 11.11.2014

arrow_upward
0
arrow_downward

Как и @Joni, ясно указано, что существует большое предостережение при замене двух элементов дважды во время обхода массива. Так как вам нужно реализовать алгоритм сортировки на месте, вам необходимо учитывать позиции элементов, которые нужно поменять местами, когда это происходит последовательно.

Другой предельный случай, который вам нужно увидеть, — это когда осталось всего три элемента, то есть последняя итерация цикла for. Вот как бы я поступил:

    store = array[smallLimit];
    store2 = array[smallIndex];
    array[smallLimit] = small;
    array[smallIndex] = store;
    smallLimit++;
    //No problem with swapping the first two elements
    store = array[largeLimit];

    //However the first swap might cause the other elements to shift
    //So we do this check
    if((array[largeIndex] == large))
     {array[largeLimit] = array[largeIndex];
      array[largeIndex] = store;
      largeLimit--;
     }

    //Just a limiting case, where amongst the last three elements, first swap happens. 
    //The smallest element is in place, just take care of the other two elements.
    if(largeLimit - smallLimit == 1){
        if(array[largeLimit] != large){
            array[smallLimit] = array[largeLimit];
            array[largeLimit] = large;
            largeLimit--;
        }
    }

Работа над DEMO для фрагмента, упомянутого выше, на основе вашего кода. Надеюсь, это поможет вам начать в правильном направлении.

person Vivek Pradhan    schedule 11.11.2014