Выбор сортировки. Как сделать сортировку сортировки как стабильный алгоритм?

Question

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

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; 
} 

Answer 1

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

Если вы хотите стабильный сорт, вы должны:

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

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

(Благодаря Groo в комментариях для указания ошибки)

Answer 2

Взятые прямо из википедии:

сортировки Выбор может быть реализован в виде стабильного рода. Если вместо замены на шаге 2 минимальное значение вставляется в первую позицию (то есть все перемещаемые элементы перемещаются вниз), алгоритм является стабильным. Однако для этой модификации требуется структура данных, которая поддерживает эффективные вставки или удаления, такие как связанный список, или приводит к выполнению записи Θ (n2).

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