Selection sort. How to do selection sort as stable algorithm?

Question

I have this impementation of Selection sort algorithm. How to do this implementation as stable? I think its not possible/

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

Your implementation is not stable. At each iteration, you take the element at position i in the array and put it at an arbitrary position in the remaining array, so you mess up the original order.

If you want a stable sort you have to:

• Choose the minimum element fro the remaining list as you already do
• Insert it at place i without swapping. This means moving the remaining elements to the right to make space for the ith element you are placing.

This ensures elements with the same value are placed in the same order in the sorted array and in the original array.

(Thanks to Groo in comments for pointing out mistakes)

Answer 2

Taken straight from wikipedia:

Selection sort can be implemented as a stable sort. If, rather than swapping in step 2, the minimum value is inserted into the first position (that is, all intervening items moved down), the algorithm is stable. However, this modification either requires a data structure that supports efficient insertions or deletions, such as a linked list, or it leads to performing Θ(n2) writes.

So basically you do have a stable sort, since you are always swapping a value that is less then the minimum value (as opposed to less then or EQUAL to the value).