Sorting of multiple arrays

[tstanley]

It would be convienent if there was a way to sort multiple arrays when the arrays are dependent on each other.  For example if there is an array of X values and an array of Y values, where the values make coordinates such as (x0, y0), (x1, y1), etc., and I want to sort the values by the X coordinate.  Or in other words it would be convienent if there was a function that could sort two (or more) arrays based upon the values in just one of the arrays.

The main reason I want this is to make nice looking X-Y plots with lines connecting the points, but the data is not in numerical order by X coordinate.

[Steve D.]

I think it would help if you could explain why using qsort on an array of structures is not an option.

[tstanley]

Typically I'm doing this to data right before I'm going to going to plot it, and the CVI plotting functions don't accept arrays of structures.  Granted, it's not hard to move the data into an array of structures, sort it, then move it back, but I've run into having to do this enough times that I thought it would be nice to have a more convienent way of doing it.

[nickb]

Hello -

I recently wrote a function that should accomplish what you're looking for - you call it similarly to qsort, but you pass each of the secondary arrays you want sorted and each array's item length through a varargs parameter.  This function assumes that all of the arrays have the same length. 

Below is an example of it's usage (sorry for the long text, it looks like I can't attach files to these replys...).  Hopefully this is helpful - let me know if you have any questions!

#include <cvirte.h>
#include <ansi_c.h>
#include <toolbox.h>

int CVIFUNC linked_qsort (void *baseElem, size_t baseElemSize, size_t numElem,
  CompareFunction compareFunc, int numLinked, ...)
{
  int i, j, started = 0, error = UIENoError;
  void *accumulated = NULL, **ptrs = NULL;
  char *writePtr, *readPtr;
  size_t *itemSizes, totalItemsSize;
  va_list arrayList;

  /* create a list of pointers for pointing into each array - as well
     as an array describing the size of the items in each array */
  nullChk (ptrs = calloc (numLinked, sizeof *ptrs));
  nullChk (itemSizes = calloc (numLinked, sizeof *itemSizes));

  va_start (arrayList, numLinked);
  started = 1;

  /* get each secondary array, initialize the list of pointers and
     assign out the item sizes */
  totalItemsSize = baseElemSize;
  for (i = 0; i < numLinked; i++) {
    ptrs[i] = va_arg (arrayList, void *);
    itemSizes[i] = va_arg (arrayList, size_t);
    totalItemsSize += itemSizes[i];
  }
  /* allocate a new array big enough to hold all the elements of
     all the arrays - including the primary array */
  nullChk (accumulated = calloc (numElem * (numLinked + 1), totalItemsSize));

  /* loop through all of the arrays passed in, filling the newly
     allocated 'accumulated' array.  Ensure the item from the primary
     array is the first item in the 'accumulated' array */
  writePtr = accumulated;
  readPtr = baseElem;
  for (i = 0; i < numElem; i++) {
    readPtr = (char *)baseElem + baseElemSize * i;
    writePtr = (char *)accumulated + totalItemsSize * i;
    memcpy (writePtr, readPtr, baseElemSize);
    writePtr += baseElemSize;
    for (j = 0; j < numLinked; j++) {
      readPtr = (char *)ptrs[j] + itemSizes[j] * i;
      memcpy (writePtr, readPtr, itemSizes[j]);
      writePtr += itemSizes[j];
    }
  }

  /* sort the newly created 'accumulated' array using the sort function passed
     in by the user.  Note that because the primary element's items are always
     the first item in each of the 'accumulated' array's items, the sorting
     works as expected, and moves all the previously linked secondary array items. */
  qsort (accumulated, numElem, totalItemsSize, (int (*)(const void *, const void *))compareFunc);

  /* assign the values from the newly sorted 'accumulated' array back
     out to the secondary and primary arrays they came from. */
  readPtr = accumulated;
  writePtr = baseElem;
  for (i = 0; i < numElem; i++) {
    writePtr = (char *)baseElem + baseElemSize * i;
    readPtr = (char *)accumulated + totalItemsSize * i;
    memcpy (writePtr, readPtr, baseElemSize);
    readPtr += baseElemSize;
    for (j = 0; j < numLinked; j++) {
      writePtr = (char *)ptrs[j] + itemSizes[j] * i;
      memcpy (writePtr, readPtr, itemSizes[j]);
      readPtr += itemSizes[j];
    }
  }

Error:
  if (started)
    va_end (arrayList);
  if (accumulated)
    free (accumulated);
  if (ptrs)
    free (ptrs);
  if (itemSizes)
    free (itemSizes);
  return error < 0 ? error : UIENoError;
}

int main (int argc, char *argv[])
{
  int a[] = {2, 4, 3, 1};
  char *b[] = {"two", "four", "three", "one"};
  char *c[] = {"dos", "cuatro", "tres", "uno"};
#pragma pack(2)
  struct TestLinkedSortStruct {
    short num;
    char *english, *spanish;
  } s[] = { {2, "two", "dos"},
            {4, "four", "cuatro"},
            {3, "three", "tres"},
            {1, "one", "uno"}
  };

  linked_qsort (a, sizeof (a[0]), 4, IntCompare, 3,
        b, sizeof (b[0]),
        c, sizeof (c[0]),
        s, sizeof (s[0]));

  return 0;
}

NickB

National Instruments