Can I improve the running time of this selection sort algorithm?

Question

I have been trying to write my own selection sort algorithm, and have been testing it on randomly generated arrays of size 10000, 50000 and 100000. My algorithm works correctly but I am trying to get it to work as quickly as possible. On my machine the tests take approximately 0.45s, 1.88s and 11.77s respectively. Is there any way to improve my algorithm so I can get it to run faster?

void SelectionSort(int array[], int len){

  int temp,i,j,min,minpos;


    for(j=0;j<len;j++){
         minpos=j;

       for(i=j+1;i<len;i++){

           if(array[minpos]>array[i]){
               minpos=i;
            }
         }

      temp=array[j];
      array[j]=array[minpos];
      array[minpos]=temp;

     }

}

Answer 1

There are a couple of improvements that could be made to your code. Every number will be swapping with itself in a sorted array instead of being ignored.

For example: If you were given an array [4, 5, 20, 30, 40]

In your given code:

void SelectionSort(int array[], int len){

    int temp,i,j,min,minpos;


    for(j=0;j<len;j++){
        minpos=j;
        for(i=j+1;i<len;i++){

            if(array[minpos]>array[i]){
                minpos=i;
            }
        }

    temp=array[j];
    array[j]=array[minpos];
    array[minpos]=temp;

}

minpos will never change and so it will swap with itself. Instead of doing that, you can put the swap in a if condition and create another variable called swapped that will act like a switch when a swap occurs.

Thus:

void SelectionSort(int array[], int len)
{

    int temp, i, j, minpos, swapped;

    swapped = 0;
    for(j=0; j<len; j++)
    {
        minpos=j;
        for(i=j+1; i<len; i++)
        {

            if(array[minpos] > array[i]){
                minpos=i;
                swapped=1;
            }
        }
        if (swapped == 1)
        {
            temp=array[j];
            array[j]=array[minpos];
            array[minpos]=temp;
            swapped = 0;
        }
    }
}

Also, if you do j < len - 1 in your first for loop, that will save you from comparing the last number with itself in the end.

I want to also point out that you have a variable named min that you declare but don't use.

With huge data sets like arrays of size 20000, 40000, and 100000 I personally wouldn't use selection sort since average and worse case scenarios are quadratic O(n^2) time which is slow compared to something like heap or merge sort.

Sorry the highlighted portion of the code looks a little wonky.

Answer 2

There is nothing that can be done "algorithm wise" to improve the running time of your sorting code. The selection sort is as simple as it gets.

Although you can optimize the code a little bit. One simple change I can think of is -

Instead of doing -

if(array[minpos]>array[i]){
    minpos=i;
}

do

int val = array[i];
if(minval>val){
    minpos=i;
    minval=val;
}

For the swapping

array[minpos] = array[j];
array[j] = minval;

What I have tried to do is to minimize the number of memory accesses. You have repeated accesses of array[minpos], (which can lead to cache misses). Copying it into a separate variable, allows it to be promoted to a register which saves the dereferences.

Lastly you can let the compiler to optimize as much as it can.

Try passing -O3 flag on gcc/clang and /O2 on Microsoft C compiler.

I have a feeling that clang with -O3 should give you the fastest possible execution times.

Answer 3

If an array contains only two elements then it will not be sorted due to this condition of the external loop

for(j=0;j<len-2;j++){
        ^^^^^^^

I think you can make it more efficient if before making swapping of elements of the array you will check whether the current element and the smallest element are the same.

So I would like to suggest the following implementation

void SelectionSort( int a[], size_t n )
{
    for ( size_t i = 0; i < n; i++ )
    {
        size_t min = i;;

        for ( size_t j = i + 1; j < n; j++ )
        {
            if ( a[j] < a[min] ) min = j;
        }

        if ( i != min )
        {
            int tmp = a[i];
            a[i] = a[min];
            a[min] = tmp;
        }
    }
}