Error when calling function to sort array of n numbers

Question

I am trying to write a function by the name of selection_sort. This function should, when presented with an array of n integers, search the array to find the largest element then move it to the last position of the array. Once it has done this it should call itself recursively to sort the first n-1 elements of the array.

Here is my code:

#include <stdio.h>

void selection_sort(int [], int);

int main(void)
{
  int n, a[n];
  printf("How many numbers do you wish to sort? ");
  scanf("%d", &n);

  printf("Well go on, type them in... "); 
  for(int i = 0; i < n; i++)
    scanf("%d", &a[i]);

  selection_sort(a, n); 

  printf("Here is the sorted array: ");
  for(int i = 0; i < n; i++) 
    printf("%d ", a[i]);
  printf("\n");

 return 0;
}

void selection_sort(int a[], int n)
{
  if(n == 1) return;
  
  int temp, largest = 0;
  
  for(int i = 1; i < n; i++) {
    if(a[i] > a[largest])  
      largest = i;
  }

  temp = a[largest];
  a[largest] = a[n-1];
  a[n-1] = temp; 
   
  selection_sort(a, n-1);
}

When I run this code I get segmentation fault: 11. It doesn't look like any part of my code is going out of the boundaries of the array. I understand that an array of length n is indexed from 0 to n-1. What is going on?

Answer 1

This declaration of an array

int n, a[n];

has undefined behavior because the variable n used as the size of an array is not initialized and has an indeterminate value.

You need at first to assign a positive value to the variable n and only after that to declare the array a.

int n;
 
printf("How many numbers do you wish to sort? ");
scanf("%d", &n);

int a[n]; 

Also your function can invoke undefined behavior if the user will pass a non-positive value as the second argument due to this condition

if(n == 1) return;

Change it the following way

if(n < 2) return;

You could make your function more "recursive" if to write an auxiliary recursive function that searches the largest element in an array.

Here is a demonstrative program.

#include <stdio.h>

size_t max_element( const int a[], size_t n )
{
    if ( n < 2 ) return 0;
    
    size_t i1 = max_element( a, n / 2 );
    size_t i2 = n / 2 + max_element( a + n / 2, n - n / 2 );
    
    return a[i1] < a[i2] ? i2 : i1;
}

void selection_sort( int a[], size_t n )
{
    if ( !( n < 2 ) )
    {
        size_t largest = max_element( a, n );
        
        if ( largest != n-1 )
        {
            int tmp = a[n-1];
            a[n-1] = a[largest];
            a[largest] = tmp;
        }
        
        selection_sort( a, n - 1 );
    }
}

int main(void) 
{
    size_t n;
    
    do
    {
        printf( "How many numbers do you wish to sort (enter a positive number)?  "  );
    } while ( scanf( "%zu", &n ) != 1 || n < 1 );
    
    int a[n];
    
    printf( "Well go on, type them in... " ); 
    for ( size_t i = 0; i < n; i++ )
    {
        scanf( "%d", a + i );
    }
    
    selection_sort( a, n ); 

    printf( "Here is the sorted array: " );
    for ( size_t i = 0; i < n; i++ )
    {
        printf( "%d ", a[i] );
    }       
    putchar( '\n' );
    
    return 0;
}

The program output might look like

How many numbers do you wish to sort (enter a positive number)?  10
Well go on, type them in... 9 8 7 6 5 4 3 2 1 0
Here is the sorted array: 0 1 2 3 4 5 6 7 8 9