Выбор сортировки. Как сделать выбор сортировки как стабильный алгоритм?
У меня есть эта реализация алгоритма сортировки выбора. Как сделать эту реализацию стабильной? Я думаю, что это невозможно /
int selection_sort1 ( int ai_numbers[], const int ci_count )
{
int counter = 0;
int i, minIndex, j;
for ( i = 0; i < ci_count; i++ )
{
minIndex = i;
for ( j = i + 1; j < ci_count; j++ )
{
if ( ai_numbers[j] < ai_numbers[minIndex] )
{
minIndex = j;
}
}
swap ( &ai_numbers[i], &ai_numbers[minIndex] );
counter++;
}return counter;
}
Решение
Взято прямо из википедии:
Сортировка выбора может быть реализована как стабильная сортировка. Если вместо обмена на шаге 2 минимальное значение вставляется в первую позицию (то есть все промежуточные элементы перемещаются вниз), алгоритм является стабильным. Однако эта модификация либо требует структуры данных, которая поддерживает эффективные вставки или удаления, такие как связанный список, либо приводит к выполнению операций записи n (n2).
Таким образом, в основном у вас есть стабильная сортировка, так как вы всегда меняете значение, которое меньше минимального значения (в отличие от меньше или равно значению).
Другие решения
Ваша реализация не является стабильным. На каждой итерации вы берете элемент в позиции i в массиве и поместите его в произвольную позицию в оставшемся массиве, чтобы вы испортили исходный порядок.
Если вы хотите стабильную сортировку, вы должны:
- Выберите минимальный элемент для оставшегося списка, как вы уже делаете
- Вставить это на месте
iбез обмена. Это означает перемещение оставшихся элементов вправо, чтобы освободить место дляiэлемент, который вы размещаете.
Это обеспечивает размещение элементов с одинаковым значением в тот же порядок в отсортированном массиве и в исходном массиве.
(Спасибо Groo в комментариях за указание на ошибки)