Why this selection sort algorithm not work?

Question

I have tried selection sorting algorithm using single for loop.

but the output is not as expeted.

is there any mistake in this code. pleases help.

#include <stdio.h>
int main() {
   int arr[10]={6,12,0,18,11,99,55,45,34,2};
   int n=10;
   int i=0, j,swap;
 
      for (j =1; j <n; j++) {
          if(j==(n-1)){
              i++;
              j=i+1;
          }
          
         if (arr[i] > arr[j]){
           swap = arr[j];
           arr[j] = arr[i];
           arr[i] = swap;}
     
     
      }
    for (int jj = 0; jj < n; jj++)
      printf("%d\t", arr[jj]);

   return 0;
}


output:  0       6       11      12      18      34      45      55      0       99

Hint: traditionally, selection sort uses 2 loops.....en.wikipedia.org/wiki/Selection_sort' — Mitch Wheat
– Mitch Wheat, Commented Apr 11, 2021 at 10:55
“using single for loop” — that’s why it doesn’t work. — Konrad Rudolph
– Konrad Rudolph, Commented Apr 11, 2021 at 11:02
@MitchWheat but the logic behind the single and double for loop same right?? — Wounder
– Wounder, Commented Apr 11, 2021 at 11:10

Răzvan Rujoiu · Accepted Answer · 2021-04-11 11:00:17Z

1

Selection sort uses two for nested loops. Try this code:

    int arr[10]={6,12,0,18,11,99,55,45,34,2};
    int n = 10;
    for (int i = 0; i < n - 1; i++) {
      for (int j = i + 1; j < n; j++) {
        if (arr[i] > arr[j]) {
            int swap = arr[i];
            arr[i] = arr[j];
            arr[j] = aux;
        }
      }
    }

answered Apr 11, 2021 at 11:00

Răzvan Rujoiu

1,49518 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Vlad from Moscow · Accepted Answer · 2021-04-11 12:11:20Z

For starters in this if statement

     if (arr[i] > arr[j]){
       swap = arr[j];
       arr[j] = arr[i];
       arr[i] = swap;}

there is used undeclared variable swap. You have to write

     if (arr[i] > arr[j]){
       int swap = arr[j];
       arr[j] = arr[i];
       arr[i] = swap;}

Secondly I have been unable to get the output you showed. If to write your updated program as shown above then its output is

0   6   11  12  18  34  45  55  2   99

The problem of your for loop is that the last element of the array takes part in the algorithm only when i is equal to n-2 due to this if statement

      if(j==(n-1)){
          i++;
          j=i+1;
      }

in this case j will be equal to n-1 before this if statement

     if (arr[i] > arr[j]){
       int swap = arr[j];
       arr[j] = arr[i];
       arr[i] = swap;}

Rewrite your for loop the following way as it is shown below in your updated program

#include <stdio.h>
int main() {
   int arr[10]={6,12,0,18,11,99,55,45,34,2};
   int n=10;
   int i=0, j;
 
      for (j =i; j <n; ) {
         if (arr[i] > arr[j]){
           int swap = arr[j];
           arr[j] = arr[i];
           arr[i] = swap;}
     
            if( ++j== n ){
              i++;
              j=i+1;
          }
          
   
      }
    for (int jj = 0; jj < n; jj++)
      printf("%d\t", arr[jj]);

   return 0;
}

In this case the program output is

0   2   6   11  12  18  34  45  55  99

Pay attention to that your approach is inefficient because there are many redundant swaps of elements of the array.

It is better to use the traditional approach to the implementation of the selection sort method. For example

#include <stdio.h>

void selection_sort( int a[], size_t n )
{
    for ( size_t i = 0; i + 1 < n; i++ )
    {
        size_t min_pos = i;
        
        for ( size_t j = i + 1; j < n; j++ )
        {
            if ( a[j] < a[min_pos] ) min_pos = j;
        }
        
        if ( min_pos != i )
        {
            int tmp = a[i];
            a[i] = a[min_pos];
            a[min_pos] = tmp;
        }
    }
}

int main( void ) 
{
    int a[] = { 6, 12, 0, 18, 11, 99, 55, 45, 34, 2 };
    const size_t N = sizeof( a ) / sizeof( *a );
    
    selection_sort( a, N );

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

    return 0;
}

The program output is

0   2   6   11  12  18  34  45  55  99

Collectives™ on Stack Overflow

Why this selection sort algorithm not work?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related