Выбор сортировки - индекс мин / макс

Question

Я просматривал алгоритм сортировки выбора на cprogramming.com и я думаю, что нашел ошибку в реализации.

Если вы работаете с алгоритмом, есть переменная index_of_min, которая, как я считаю, должна быть index_of_max (поскольку, когда я ее тестировал, сортировка выполнялась по величине и наименьшему).

Думая, что это опечатка или небольшая ошибка, я проверил некоторые другие сайты, такие как wikipedia и некоторые менее известные сайты, такие как geekpedia . Кажется, они называют это индексом мин.

Когда я запустил его через отладчик, мне действительно показалось, что это индекс максимального значения. Я где-то ошибаюсь?

Редактировать: Как указал Сванте, только внедрение cprogramming неверно. Википедия и Geekpidia в порядке.

Answer 1

Сайты википедии и geekpedia кажутся правильными, в реализации cprogramming.com действительно есть ошибка; это:

if (array[index_of_min] < array[y])
  { index_of_min = y; }

имеет обратный порядок, он должен быть:

if (array[y] < array[index_of_min])
  { index_of_min = y; }

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

Answer 2

С Cprogramming.com «Он работает, выбирая наименьший (или самый большой, если вы хотите отсортировать от большого к маленькому) элемент массива и помещая его в начало массива», поэтому они сортируют его от большого к маленький, код неверен, и переменная naming не имеет значения, index_of_min отслеживает начальную точку в массиве (0) и затем перемещается вперед в этом массиве. то есть index_of_min хранит наименьшее значение индекса. Не путайте его с каким-либо значением этого индекса.

Answer 3

Я только что прочитал код, но похоже, что вы правы: либо index_of_min названо неправильно, либо сравнение обратное.

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

Answer 4

Вы правы. Код с этого сайта (показанный ниже) неверен.

for(int x = 0; x < n; x++)
    {
        int index_of_min = x;
        for(int y = x; y < n; y++)
        {
            if(array[index_of_min] < array[y])    /* Here's the problem */
            {
                index_of_min = y;
            }
        }
        int temp = array[x];
        array[x] = array[index_of_min];
        array[index_of_min] = temp;
    }

В конце внутреннего цикла, for(int y=x; y<n; y++), переменная index_of_min содержит индекс максимального значения . Предполагая, что предназначен для сортировки массива из от наибольшего к наименьшему , это переменная с плохим именем .

Если вы хотите, чтобы массив сортировался от наименьшего к наибольшему (как и следовало ожидать), вам нужно обратить оператор if :

if (array[y] < array[index_of_min])
{
    index_of_min = y;
}