Can you qsort part of an array?

Question

I'd like to qsort the first 100 elements in an integer array and leave the remaining elements untouched.

I'm currently trying to do this with the following call:

int cmpfunc(const void *a, const void *b)
{
  int xi = *(const int *) a;
  int yi = *(const int *) b;
  
  return (xi - yi);
}

int my_array[100+some_size];
memset(my_array, 0, sizeof(my_array));
qsort(my_array, 100, sizeof(int), cmpfunc);

However, I'm getting a segmentation fault. Is sorting the first x values of an array in C possible?

Doing a sort of a contiguous section of the array is fine, but depending on how big `some_size` is you may be exhausting the available stack size causing a ... stack overflow (!) and hence segfault. There's lots of [previous discussion](https://stackoverflow.com/q/13908033/21146235) on this. — motto, Apr 03 '23 at 13:50
Yes, you can, your code looks more or less OK to me, the problem is elsewhere in code you didn't show. Go back to the first comment. — Jabberwocky, Apr 03 '23 at 13:51
Max of `some_size` is `3^10 = 59,049`, is that likely to cause an overflow? — Connor, Apr 03 '23 at 13:54
What is your environment? On a PC 60kB of stack shouldn't be an issue. On some Arduino or ESP or any other tiny micro that might be too much. — Gerhardh, Apr 03 '23 at 13:57
Remove the `qsort` alltogether and check if you get the same problem. What exactly is your platform? — Jabberwocky, Apr 03 '23 at 13:58
Ahhh okay, I'm sending this off to a Codewars server! I'm not sure what their setup is, but if they deliberately limit you, that could be the issue. — Connor, Apr 03 '23 at 13:58
@Connor II have no idea what a codewars server is, but it's unlikely they limit the stack size to as low as 60kB. — Jabberwocky, Apr 03 '23 at 14:00
@Jabberwocky They're a coding challenge website, you send off code to them, and they run it on a server and test if you got the correct answer. I'll try the problem again with `calloc` and `realloc`. Unfortunately, removing qsort causes my program to fail a test, and there's no way of knowing if I had a segmentation fault at that particular test or later in the test suite! — Connor, Apr 03 '23 at 14:02
You seem to have asked an XY question. Yes, certainly you can sort a contiguous subset of the elements of a larger array, and you don't need to do anything special to use `qsort()` for that. But I take your primary interest to be why you are getting a segfault, which is an altogether different question that we cannot answer from the information given. At this point, if you want us to address that then you will need to pose a new question about it, which provides a [mre] demonstrating the segfault. — John Bollinger, Apr 03 '23 at 14:10
Just off-topic note about this one: `return (xi - yi);` . It is simple and effective, but may cause underflow/overflow issue with big negative numbers. — SKi, Apr 03 '23 at 14:28

score 5 · Accepted Answer · answered Apr 03 '23 at 13:51

5

From the point of view of the qsort function it makes no difference if there are any more array elements after the first 100, since it only gets a pointer to the start of the array, and the number of elements after the starting pointer.

So, yes, assuming it's possible to sort an array with 100 elements, it's also possible to sort the first 100 elements of a larger array.

answered Apr 03 '23 at 13:51

mkrieger1

19,194
5
54
65

It's more a property of C array to pointer decay rather than `qsort`. – Agent_L Apr 03 '23 at 14:01

Vlad from Moscow · Answer 2 · 2023-04-03T20:21:27.497

You may sort any part of an array supplying correctly a pointer to the initial element of the sorting range of elements and the number of elements in the range.

As for your problem then it is possible that its reason can be integer overflow that results in undefined behavior produced by your comparison function

int cmpfunc(const void *a, const void *b)
{
  int xi = *(const int *) a;
  int yi = *(const int *) b;
  
  return (xi - yi);
}

in the return statement.

Here is a simple example. Let's xi is equal to INT_MAX and yi is equal to -1. Then the expression xi - yi results in the integer overflow and it can be that its value will be for example a negative value while actually the function shall return a positive number because xi is greater than yi.

That is in any case the comparison function is wrong.

You should rewrite the comparison function the following way

int cmpfunc(const void *a, const void *b)
{
  int xi = *(const int *) a;
  int yi = *(const int *) b;
  
  return ( yi < xi ) - ( xi < yi );;
}

Here is a demonstration program.

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

int cmpfunc(const void *a, const void *b)
{
  int xi = *(const int *) a;
  int yi = *(const int *) b;
  
  return ( yi < xi ) - ( xi < yi );;
}

int main( void ) 
{
    int a[] = { INT_MAX, INT_MAX - 1, INT_MAX - 2, -1, -2, 10, 9, 8, 7, 6 };
    const size_t N = sizeof( a ) / sizeof( *a );

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

    size_t n = N / 2;
    qsort( a, n, sizeof( int ), cmpfunc );

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

    qsort( a + n, N - n, sizeof( int ), cmpfunc );

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

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

The program output is

2147483647 2147483646 2147483645 -1 -2 10 9 8 7 6 
-2 -1 2147483645 2147483646 2147483647 
6 7 8 9 10 
-2 -1 2147483645 2147483646 2147483647 6 7 8 9 10

If you will try to use your comparison function with the demonstration program then at least you will get an incorrect result.

For example using an inline compiler I got the following output

2147483647 2147483646 2147483645 -1 -2 10 9 8 7 6 
2147483646 2147483647 -2 -1 2147483645 
6 7 8 9 10 
2147483646 2147483647 -2 -1 2147483645 6 7 8 9 10

As you can see the first part of the array was sorted incorrectly.

Can you qsort part of an array?

2 Answers2