Выбор сортировки на C. Почему?

Question

Это простой код на C (выбор сортировки):

#include <stdio.h>
#include <stdlib.h>
#define ItemCount 10

int numbers[ItemCount] = {4,9,3,7,2,5,10,2,12,6};    

int MinNumberIndex(int start) {
    int i;
    int minindex = start;

    for (i = start + 1; i < ItemCount; i++)
        if (numbers[minindex] > numbers[i])
            minindex = i;

    return minindex;    
}


void SelectionSort() {
    int i,temp,minindex;

    for (i = 0; i < 10; i++) {
        minindex = MinNumberIndex(i);

        temp = numbers[i];
        numbers[i] = numbers[minindex ];
        numbers[minindex ] = temp;                                                                          
    }
}

int main() {
    int i;

    SelectionSort();
    for (i = 0; i < 10; i++)
        printf("%d\t",  numbers[i]);

    system("pause");    
}

И все работает нормально ... но если я немного изменюсь так (в функции selectionSort):

for (i = 0; i < 10; i++) {
    temp = numbers[i];
    numbers[i] = numbers[MinNumberIndex(i)];
    numbers[MinNumberIndex(i)] = temp;                                                                          
}

это не работает ... Почему? Вроде бы тоже самое.

Answer 1

Значение, возвращаемое MinNumberIndex, зависит от содержимого массива. Вы меняете контент, когда делаете:

numbers[i] = numbers[MinNumberIndex(i)];

поэтому следующий звонок:

numbers[MinNumberIndex(i)] = temp;

будет / может быть сохранено в неправильной ячейке, поскольку MinNumberIndex (i) может измениться. Это нарушает алгоритм, потому что вы не делаете правильный обмен.

Answer 2

Поскольку MinNumberIndex(i) возвращает индекс наименьшего элемента в диапазоне [i,ItemCount-1], а ваша альтернативная версия кода изменяет этот диапазон в массиве между двумя вызовами на MinNumberIndex(), вы не меняете местами элементы.

Ваш альтернативный цикл эквивалентен:

for (i=0;i<10;i++)
        {

            temp = numbers[i];
            numbers[i] = numbers[MinNumberIndex(i)];
            numbers[i] = temp;                                                                          
        }

Немного подробнее, когда эта строка кода выполняется в цикле for:

numbers[i] = numbers[MinNumberIndex(i)];

Это делает numbers[i] минимумом в диапазоне массива, с которым вы имеете дело в данный момент, поэтому при следующем вызове MinNumberIndex(i) будет возвращено i.И

numbers[i] = temp;

просто восстановит массив в то же состояние, в котором он находился в верхней части цикла.

Answer 3

Поскольку MinNumberIndex(i) возвращает разные значения каждый раз, когда вы вызываете его, вторая версия действительно не является перестановкой значений.