Home > Back-end >  what is the error in this logic of selection sort
what is the error in this logic of selection sort

Time:07-01

the first for loop will start at the end and swap its value to the max value in the array a[0-->its own index]

int selection_sort(int *a, int size) {
    int i, j, swap;

  
   
    for (i = size - 1; i <= 0; i--) {
        /*this will find the max between o index to i th index*/
        for (j = 0; j <= i; j  ) {
            if (a[i] < a[j]) {
                swap = a[i];
                a[i] = a[j];
                a[j] = a[i];
            }
        }
    }
}

output is the same array with no change in order

CodePudding user response:

For starters the function has the return type int but returns nothing. Also the second parameter should have the unsigned integer type size_t instead of the signed integer type int.

Also you should declare variables in minimum scopes where they are used.

The main problem with your code is that the body of this for loop

for (i = size - 1; i <= 0; i--) {

will never get the control provided that size is not less than 2.

Also there is a typo

a[j] = a[i];

You have to write

a[j] = swap;

Apart from this there are redundant swaps.

The function can look the following way

void selection_sort( int *a, size_t n ) 
{
    for ( size_t i = n; i-- != 0; ) 
    {
        size_t max = i;

        for ( size_t j = 0; j < i; j   ) 
        {
            if ( a[max] < a[j] ) max = j;
        }

        if ( max != i )
        {
            int swap = a[max];
            a[max] = a[i];
            a[i] = swap;
        } 
    }
}

Here is a demonstration program.

#include <stdio.h>

void selection_sort( int *a, size_t n ) 
{
    for ( size_t i = n; i-- != 0; ) 
    {
        size_t max = i;

        for ( size_t j = 0; j < i; j   ) 
        {
            if ( a[max] < a[j] ) max = j;
        }

        if ( max != i )
        {
            int swap = a[max];
            a[max] = a[i];
            a[i] = swap;
        } 
    }
}

int main( void )
{
    int a[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
    const size_t N = sizeof( a ) /sizeof( *a );

    for ( size_t i = 0; i < N; i   )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );

    selection_sort( a, N );

    for ( size_t i = 0; i < N; i   )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );
}

Its output is

9 8 7 6 5 4 3 2 1 0 
0 1 2 3 4 5 6 7 8 9 

CodePudding user response:

Your for loop is wrong for (i = size - 1; i <= 0; i--). The comparison should be >=0.

Also, the value swapping is incorrect

            if (a[i] < a[j]) {
                swap = a[i];
                a[i] = a[j];
                a[j] = a[i];
            }

should be

            if (a[i] < a[j]) {
                swap = a[i];
                a[i] = a[j];
                a[j] = swap;
            }
  • Related