Sorting an array of integers in alternate fashion using qsort function.

Question

/*I recently learnt qsort function. This c code is giving incorrect output. Need help with this. PROBLEM- Sorting an array of integers in alternate fashion. (the elements at even indices and those at odd indices are sorted separately) OUTPUT- 0 4 1 2 5 8 7 5 9 3 10 5 */

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

// This function is used in qsort to decide the relative order
// of elements at addresses p and q.
int comparator(const void *p, const void *q)
{
    // Get the values at given addresses
    int l = *(const int *)p;
    int r = *(const int *)q;

    return (l-r);
}

// A utility function to print an array
void printArr(int arr[], int n)
{
    int i;
    for (i = 0; i < n; i = i+1)
        printf("%d ", arr[i]);
}

// Driver program to test above function
int main()
{
    int arr[] = {1,4,7,2,9,3,0,8,6,5};

    int size0 = sizeof(arr) / sizeof(arr[0]);
    int size1 = (int) ((float)sizeof(arr) / sizeof(arr[0]) / 2 + 0.5);
    int size2 = size0 - size1;

    qsort((void *)arr+1, size2, 2*sizeof(arr[0]), comparator);   
    //sort odd positions

    qsort((void *)arr, size1, 2*sizeof(arr[0]), comparator);
    //sort even positions

    printf("Output array is\n");
    printArr(arr, size0);
    printf("\n%d %d", size0, size1);

    return 0;
}

Answer 1

qsort needs a contiguous block of memory to function properly.

If you need to sort odd and even indexed elements separately, you could start by separating the elements, sort them indipendently and then merge the two parts.

You can do that even without allocating any extra memory:

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

int less_int(const void *lhs, const void *rhs)
{
    return *(const int *)lhs < *(const int *)rhs ? -1
        : *(const int *)lhs > *(const int *)rhs ? 1 : 0;
}

int greater_int(const void *lhs, const void *rhs)
{
    return *(const int *)lhs > *(const int *)rhs ? -1
        : *(const int *)lhs < *(const int *)rhs ? 1 : 0;
}

void sort_ascending(int* arr, size_t n)
{
    qsort(arr, n, sizeof *arr, less_int);
}

void sort_descending(int* arr, size_t n)
{
    qsort(arr, n, sizeof *arr, greater_int);
}

inline void swap_int(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

size_t partition_odd_even(int* arr, size_t n )
{
    size_t n_odds = n - n / 2;
    for (size_t i = 1, j = n_odds + n_odds % 2; i < n_odds; i += 2, j += 2)
    {
        swap_int(arr + i, arr + j);
    }
    return n_odds;
}

void interleave_odd_even(int* arr, size_t n )
{
    size_t n_odds = n - n / 2;
    for (size_t i = 1; i < n_odds; ++i )
    {
        for (size_t j = n_odds - i; j < n_odds + i; j += 2)
        {
            swap_int(arr + j, arr + j + 1);
        }
    }
}

void print_arr(int* arr, size_t n);

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

    size_t n_odds = partition_odd_even(arr, arr_size);
    size_t n_evens = arr_size - n_odds;
//  print_arr(arr, arr_size);

    sort_ascending(arr, n_odds);
//  print_arr(arr, n_odds);

    sort_descending(arr + n_odds, n_evens);
//  print_arr(arr + n_odds, n_evens);

    interleave_odd_even(arr, arr_size);
    print_arr(arr, arr_size);

    return 0;
}

void print_arr(int* arr, size_t n)
{
    for(size_t i = 0; i < n; ++i)
    {
        printf(" %d", arr[i]);  
    }
    puts("");
}

Which gives:

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

EDIT

As noted in the comments below by greybeard the code above is not really time efficient as the merge part is O(N²). Using a temporary array which contains only the elements to be sorted in a particular way, the following program only need O(N) extra time and O(N/K) space, where K is the number of different sorting order needed (2 in OP's question).

Jonathan Leffler also pointed out that it could be made more general allowing the algorithm "to handle 3, 4, … N evenly interlaced sub-arrays, possibly with different sort orders for each". I implemented it in the following snippet by passing to the sort function an array of pointer to compare functions.

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

// compare functions
typedef int (*PCMPFN)(const void*, const void*);

int ascending_cmp_int(const void *lhs, const void *rhs)
{
    return *(const int *)lhs < *(const int *)rhs ? -1
        : *(const int *)lhs > *(const int *)rhs ? 1 : 0;
}

int descending_cmp_int(const void *lhs, const void *rhs)
{
    return *(const int *)lhs > *(const int *)rhs ? -1
        : *(const int *)lhs < *(const int *)rhs ? 1 : 0;
}

// This function is never called. Whithout knowing the actual implementation
// of 'qsort' we can't make any assumption
int untouched_cmp_int(const void *lhs, const void *rhs)
{
    (void)lhs;  // Those parameters are unused here, this is to avoid a warning
    (void)rhs; 
    return 0;
}

// Copy the elements of the source array starting from index 'start' with stride 'step'
size_t strided_split(int* dest, const int *src, size_t n, size_t start, size_t step)
{
    size_t j = 0;
    for (size_t i = start; i < n; i += step, ++j)
    {
        dest[j] = src[i];
    }
    return j;
}

// Inverse of the previous
void strided_merge(int* dest, const int *src, size_t n, size_t start, size_t step)
{
    for (size_t i = start, j = 0; j < n; i += step, ++j)
    {
        dest[i] = src[j];
    }
}

// Apply different sort orders to different elements
void alternate_sort(int* arr, const size_t n, PCMPFN comps[], const size_t k)
{
    int tmp[n/k + 1];         // Please note that VLA are optional in C11

    for ( size_t i = 0; i < k; ++i )
    {
        if ( comps[i] == untouched_cmp_int )
            continue;
        // First select the elements 
        size_t n_copied = strided_split(tmp, arr, n, i, k);
        // then sort only them as needed
        qsort(tmp, n_copied, sizeof tmp[0], comps[i]);
        // Once sorted, copy back the elements in the source array
        strided_merge(arr, tmp, n_copied, i, k);
    }
}

void print_arr(const int* arr, const size_t n);

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

    PCMPFN compares[] = {
        descending_cmp_int, untouched_cmp_int, ascending_cmp_int
    };
    const size_t K = sizeof compares / sizeof *compares;

    alternate_sort(arr, N, compares, K);
    print_arr(arr, N);

    return 0;
}

void print_arr(const int* arr, const size_t n)
{
    for(size_t i = 0; i < n; ++i)
    {
        printf(" %d", arr[i]);  
    }
    puts("");
}

Answer 2

It is possible to use qsort() for sorting of even/odd elements separately. However, the setup must be changed slightly to accomplish this.

As Peter mentioned correctly (and I didn't consider before as I must admit) sorting for even elements will "destroy" the result for odd elements as swapping considers the element size which is denoted as pair of even and odd element.

This in mind, a solution can be done for all that if the result of first sorting is saved before second sorting is done.

In my sample, I copied the relevant elements after first sorting and merged them in after second sorting.

This is my sample testQSortEvenOdd.c:

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

int compEven(const int *p1, const int *p2)
{
  return (p1[0] > p2[0]) - (p1[0] < p2[0]);
}

int compOdd(const int *p1, const int *p2)
{
  return (p1[1] > p2[1]) - (p1[1] < p2[1]);
}

void printArray(size_t n, int *arr, int step)
{
  for (; n--; arr += step) printf(" %d", *arr);
  putchar('\n');
}

int main()
{
  int arr[] = { 1, 4, 7, 2, 9, 3, 0, 8, 6, 5 };
  enum { size = sizeof arr / sizeof *arr };
  assert(!(size & 1));
  /* sort odd positions */
  qsort(arr, (size + 1) / 2, 2 * sizeof *arr,
    (int(*)(const void*, const void*))&compOdd);
  /* output of sorted array for odd positions */
  puts("Odd elements sorted:");
  printArray(size / 2, arr + 1, 2);
  int arrRes[(size + 1) / 2];
  for (size_t i = 1; i < size; i += 2) arrRes[i / 2] = arr[i];
  /* sort even positions */
  qsort(arr, (size + 1) / 2, 2 * sizeof *arr,
    (int(*)(const void*, const void*))&compEven);
  /* output of sorted array for even positions */
  puts("Even elements sorted:");
  printArray((size + 1) / 2, arr, 2);
  /* merge array with copy */
  for (size_t i = 1; i < size; i += 2) arr[i] = arrRes[i / 2];
  puts("Merged elements:");
  printArray(size, arr, 1);
  /* done */
  return 0;
}

Tested in Cygwin on Windows 10 (64 bit):

$ gcc --version
gcc (GCC) 6.4.0

$ gcc -std=c11 -o testQSortEvenOdd testQSortEvenOdd.c 

$ ./testQSortEvenOdd
Odd elements sorted:
 2 3 4 5 8
Even elements sorted:
 0 1 6 7 9
Merged elements:
 0 2 1 3 6 4 7 5 9 8

$

Some additional notes:

1. The way I (and the questioner) used qsort(), it handles two consecutive int values at once. Hence, it must be granted that the array has an appropriate number of elements. (Otherwise, qsort() either does out-of-bound access or cannot consider the last element.) To consider this fact, I inserted the

   assert(!(size & 1));

   which can be read as "Assure that the array has an even number of elements."

2. I decided to make separate functions compEven() and compOdd() as IMHO it simplified things. I changed the signature of both to my needs and got complains (warnings) from gcc about wrong function signature. Therefore, I casted the function pointers to the expected type (to make gcc silent).

3. Jonathon gave a nice hint to make the comparison functions robust against underflow issues. return p1[0] - p2[0]; can cause wrong results when the difference becomes greater than INT_MAX or smaller than INT_MIN. Instead he recommends to use:

   return (p1[0] > p2[0]) - (p1[0] < p2[0]);

   which never can have any overflow/underflow issues.

How it works:

In case a < b: (a > b) - (a < b) ⇒ 0 - 1 ⇒ -1

In case a == b: (a > b) - (a < b) ⇒ 0 - 0 ⇒ 0

In case a > b: (a > b) - (a < b) ⇒ 1 - 0 ⇒ 1

Very clever Jonathan Leffler – I'm impressed.

Answer 3

qsort:

void qsort( void *ptr, size_t count, size_t size, int (*comp)(const void *, const void *) );

Sorts the given array pointed to by ptr in ascending order. The array contains count elements of size bytes. Function pointed to by comp is used for object comparison.

ptr - pointer to the array to sort

count - number of element in the array

size - size of each element in the array in bytes

comp - comparison function which returns ​a negative integer value if the first argument is less than the second,

In your program, you are passing size of each element as 2*sizeof(arr[0]) which results in 8 bytes which is incorrect input to qsort(). Hence you are getting incorrect output.