Search code examples
cloopssortingfor-loopselection-sort

Why does my selection sort fail when I hardcode a non-zero minimum value?


My code isn't performing a selection sort successfully when I specify min = arr[0] before entering the loop to process the array, it fails.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int arr[11] = {7, 12, 4, 28, 3, 15, 7, 3, 89, 1, 12};
    int x, i, next_index;

    /* Select first element (i = 0) first for loop and compare it with all  
       elements of array till the end of array second for loop (so next   
       iteration, when i = 1 the first element will be the smallest one */

    for (i = 0; i <= 10; i++)
    {   
        // min = arr[0]; /* <-- WHEN I UNCOMMENT THIS THE CODE FAILS. WHY? */

        /* Select min element */
        for (next_index = i + 1; next_index <= 10; next_index++)
        {     
            if (arr[next_index] < arr[i])
            {   
                 /* Swap arr[i] with min value */
                 x = arr[i];
                 arr[i] = arr[next_index];
                 arr[next_index] = x;
            }
        }
     }
     printf("Sorted array: \n");

     for (i = 0; i <= 10; i++)
        printf(" %d \n", arr[i]); 

     return 0;
}

Solution

  • For starters the both approaches are inefficient because there are redundant swaps of elements of the array.

    In the second program instead of using in the body of the outer loop the statement

    min=arr[i];
    

    you are using

    min=arr[0];
    

    In this loop

    printf("sorting array is : \n");
           for(i=0;i<=10;i++)
               {
        printf(" %d \n",min); // as i put value of min in i
               } 
    

    you are always outputting the last value of the variable min outside the loops that sort the array. . Also it is a bad idea to use magic numbers like 10.

    And you should declare variables in the smallest scope where they are used.

    The program can look the following way

    #include <stdio.h>
    
    int main( void )
    {
        int arr[] = { 7, 12, 4, 28, 3, 15, 7, 3, 89, 1, 12 };
        const size_t N = sizeof( arr ) / sizeof( *arr );    
    
        printf( "Unsorted array: " );
        for ( size_t  i = 0; i < N; i++ )
        {
            printf(" %2d ", arr[i] );
        }
        putchar( '\n' );
    
    
        for ( size_t i = 0; i < N; i++ )
        {   
            size_t min_i = i; 
    
            for ( size_t j = i + 1; j < N; j++ )
            {     
                if ( arr[j] < arr[min_i] ) min_i = j;
            }
    
            if ( min_i != i )
            {
                int tmp = arr[i];
                arr[i] = arr[min_i];
                arr[min_i] = tmp;
            }
        }
    
        printf( "sorted array:   " );
        for ( size_t  i = 0; i < N; i++ )
        {
            printf(" %2d ", arr[i] );
        }
        putchar( '\n' );
    
        return 0;
    } 
    

    Its output is

    Unsorted array:   7  12   4  28   3  15   7   3  89   1  12 
    sorted array:     1   3   3   4   7   7  12  12  15  28  89