Error when calling function to sort array of n numbers

user_15612483 0
Viewed 93

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?

function-definition selection-sort sorting c arrays
4 Answers

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
user_28772410

The problem is, you write

 int n, a[n];

when n has indeterminate value.

In other words, n is of a type which can have trap representation, does not have it's address taken, is a locally scoped automatic storage variable and not initialized - thereby having an indeterminate value. While using that as the array size will most definitely create issues.

To avoid this, you can make use of n after you have successfully taken the value from user and assigned it to n. Pseudocode would look like

integer n = 0;

if ( scan_from_user_and_check_success (&n) ) //function returns 0 in failure
{
    array a[n];

    // use `a[n]`

}
user_21739170

I think the problem is here:

int n, a[n];

You are trying to dynamically allocate an array of integers with size n. At compile time, n has indeterminate value. Unfortunately you did not allocate anything. You have only declared an array that has no allocation.

Please read this article about dynamic allocation.

user_5363770

Sourav's answer is correct. However, I've took the liberty to make some modifications to your code so as to follow good programming practices.

The selection_sort prototype missed the int array name.

void selection_sort(int a[], int);

Varibale n was no initialized (but that was not the problem here)

int n = 0;

The array declaration should be included after the n input (this was the problem)*.

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

int a[n];

Finally, you are not considering the empty array case in your slection_sort function.

  • Although declaring variables at the beginning of a funtion is a good programming practice, in this example you can't get away with it because you are getting the array size from standard input. In a second approach to this problem you should try and use dinamically allocated memory for the int array. However, if you're new to C or to solving this kind of problem, this program is just fine.
user_156959740
Related