How can I sort my input array if it is defined as const?

user_1757475 0
Viewed 92

I am trying to sort my input array pAddrSourceArray in and ascending way, but the input array is defined as const as it is shown in below header, that cannot be changed since it is imposed.

So far I have the idea of how to sort the array, however I am struggling to overcome the fact that the input array is defined as constant. I cannot (or I don't know) how to create an auxiliary array with the content of the input one, so that I can sort this auxiliary one and then assign to the output array pAddrResultArray

Any hints of how to solve this?

void sortArray(uint32_t samplesCount, const int16_t *pAddrSourceArray, int16_t *pAddrResultArray)
{
    int16_t *pInputArray = pAddrSourceArray; // This is wrong, I know it should be const  int16_t *pInputArray = pAddrSourceArray;

    int16_t min_idx;

    // One by one move boundary of unsorted subarray
    for (uint32_t indxUnsort = 0; indxUnsort < samplesCount - 1; indxUnsort++ )
    {

        // Find the minimum element in unsorted array
        min_idx = indxUnsort;
        for (uint32_t k = indxUnsort + 1; k < samplesCount; k++)
        {
            if (pInputArray[k] < pInputArray[min_idx])
            {
                min_idx = k;
            }
        }

        // Store actual local min value
        int16_t localMin = pInputArray[min_idx];
        // Update new min at current indxUsort position
        pInputArray[min_idx] = pInputArray[indxUnsort];
        // Append the new local min found
        pInputArray[indxUnsort] = localMin;
    }

    // Assign sorted array to output array
    pAddrResultArray = pInputArray;
}
constants sorting c arrays
3 Answers

You are not supposed to sort the source array in place, but you can simply copy it to the destination array and sort that one in place with a method of your choice:

#include <string.h>
#include <stdlib.h>

int cmp_int16_t(const void *p1, const void *p2) {
    const int16_t *s1 = p1;
    const int16_t *s2 = p2;
    return (*s1 > *s2) - (*s1 < *s2);
}

void sortArray(uint32_t samplesCount, const int16_t *pAddrSourceArray, int16_t *pAddrResultArray) {
    memmove(pAddrResultArray, pAddrSourceArray, samplesCount * sizeof(*pAddrResultArray));
    qsort(pAddrResultArray, samplesCount, sizeof(*pAddrResultArray), cmp_int16_t);
}
user_45932670

Here is one way to do it. It takes each input value in turn from the input array, and inserts it into the output array at the position of the first element of the output array that is greater than the input array if any, otherwise at the end of output array, shuffling the remaining elements of the output array up by one. This ensures that output array filled so far is always in ascending order.

Since the output array contents so far are already sorted in ascending order, the position to insert the input value can be determined using a binary search.

The overall average time complexity of O(N^2) is dominated by the insertion of elements into the output array, although the binary search to find the insertion position so far helps a bit, being O(log n) compared to O(n) for a linear search.

void sortArray(uint32_t samplesCount, const int16_t* pAddrSourceArray, int16_t* pAddrResultArray)
{
    uint32_t s;

    for (s = 0; s < samplesCount; s++)
    {
        /* Get next value from input. */
        int16_t xs = pAddrSourceArray[s];
        uint32_t a, b;

        /* Find position where next value belongs in the output so far by a binary search. */
        a = 0;
        b = s;
        while (a < b)
        {
            uint32_t m = (a + b) / 2;

            if (xs < pAddrResultArray[m])
            {
                b = m;
            }
            else
            {
                a = m + 1;
            }
        }
        /* Insert value at position in output array, shuffling up remaining elements. */
        while (a < s)
        {
            int16_t xa = pAddrResultArray[a];

            pAddrResultArray[a] = xs;
            xs = xa;
            a++;
        }
        pAddrResultArray[a] = xs;
    }
}
user_52644910

if you know it should be const, then declare it as:

const int16_t *pInputArray

but when you initialized a non-const pointer with a const int16_t * you should receive at least a warning from the compiler (telling something similar to initializer discards 'const' qualifier).

As in

void f(const int *a)
{
        int *b = a;
}

which on compiling gives:

pru58405.c:4:7: warning: initializing 'int *' with an expression of type 'const int *' discards qualifiers
      [-Wincompatible-pointer-types-discards-qualifiers]
        int *b = a;
             ^   ~
1 warning generated.

The constness of the objects you manage in your programs depend strongly on the types you use for the variables. Once you declare it nonconst, you can access it and modify without problem (except if it is located in a true read only segment, in which case, you'll probably get an exception if you try to modify the values)

As you posted an incomplete, non verifiable example (read the page entitled How to create a Minimal, Reproducible Example) it is impossible to go further in what we can do for you. My apologies for that.

user_38994310
Related