Две версии сортировки выбором

Недавно я изучал алгоритмы сортировки, и, как и многие вводные книги по алгоритмам, та, которую я начал читать, начинается с реализации сортировки выбором. код выглядел следующим образом...

Реализация А

//a is an array of ints.
int n = a.length;
    for(int i = 0; i < n; i ++){
        int min =0;
        for( int x = i+1; x <n;x++){
            if(a[x].compareTo(a[i])<0){
                Comparable tmp = a[i];
                a[i] = a[x];
                a[x] = tmp;                 
            }
        }
    }

После анализа блока кода я изменил алгоритм на следующий.

Реализация Б

//a is an array of ints
int n = a.length;
    for(int i = 0; i < n; i ++){
        int min =i;
        for( int x = i+1; x <n;x++){
            if(a[x].compareTo(a[min])<0){
                        min=x;      
            }
        }

        if(min>i){
            Comparable tmp = a[i];
            a[i] = a[min];
            a[min] = tmp;
        }

    }

Я также нашел аналогичные реализации в Интернете, используя минимальное значение для поиска наименьшего значения в массиве, а затем заменяя его элементом в позиции i массива. Мой вопрос: что-то не так со второй реализацией? это не правильная сортировка выбора, потому что она не заменяет каждый найденный элемент, который меньше, чем элемент в позиции i, а вместо этого ждет, пока он не найдет наименьший элемент в массиве перед заменой?

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


sorting algorithm selection-sort
person czgaljic    schedule 22.07.2014    source источник
comment
Я считаю вашу реализацию B правильной сортировкой выбором, она даже выглядит как пример реализации из Википедии . Он делает меньше свопов, чем реализация A, и в целом должен быть быстрее.   -  person Blastfurnace    schedule 22.07.2014
comment
В моей книге о структуре данных Java используется ваша реализация «B». Во всяком случае, для меня «А» выглядит как слабая попытка улучшить сортировку пузырьком.   -  person ChiefTwoPencils    schedule 22.07.2014

Ответы (1)


arrow_upward
0
arrow_downward

Реализация B — это правильная сортировка выбором. Реализация A не такова, потому что она всегда заменяет меньшее значение на переднее, что иногда не является наименьшим значением.

Согласно википедии http://en.wikipedia.org/wiki/Selection_sort

Далее алгоритм находит наименьший (или наибольший, в зависимости от порядка сортировки) элемент в несортированном подсписке, заменяет его крайним левым несортированным элементом (помещает его в отсортированном порядке) и перемещает границы подсписка на один элемент вправо.

person nuttt    schedule 22.07.2014