C++ TAGARRAY replacement how?

[Patrice Terrier]

What is the easiest way to translate the PB's quicksort code below, using TAGARRAY, into C/C++

DIM A1(LB TO UB) AS INTEGER, A2(LB TO UB) AS INTEGER
nCount = UB
ARRAY SORT A1() FOR nCount, TAGARRAY A2()

...

[Charles Pegge]

Hi Patrice,

You need to fill your  tagArray A2 with index numbers 0..n, then create a callback for processing comparisons, using the tag index numbers to reference data in A1.

This allows you to sort any kind of data using your own comparison method in the callback.

http://www.cplusplus.com/reference/cstdlib/qsort/

Adapted for sorting integers:

Code (c) Select Expand


/* qsort example */

#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort */

int ValueArray[] = { 40, 10, 100, 90, 20, 25 };
int IndexArray[] = { 0,   1,   2,  3,  4,  5 };

int compare (const void * a, const void * b)
{
  return ( ValueArray[*(int*)a] - ValueArray[*(int*)b] );
}

int main ()
{
  int n;
  qsort (IndexArray, 6, sizeof(int), compare);
  for (n=0; n<6; n++)
     printf ("%d ",ValueArray[IndexArray[n]]);
  return 0;
}


extended to support floats:

Code (c) Select Expand


/* qsort example */

#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort */

int   ValueArrayI[] = { 40, 10, 100, 90, 20, 25 };
float ValueArrayF[] = { 40, 10, 100, 90, 20, 25 };
int   IndexArray[]  = { 0,   1,   2,  3,  4,  5 };

int compareInt (const void * a, const void * b)
{
  return ( ValueArrayI[*(int*)a] - ValueArrayI[*(int*)b] );
}

int compareFloat (const void * a, const void * b)
{
  float c=ValueArrayF[*(int*)a] - ValueArrayF[*(int*)b];
  if (c>0)
  {
    return 1;
  }
  else if (c<0)
  {
    return -1;
  }
  else
  {
    return 0;
  }
}

int main ()
{
  int n;

  //INT SORT
  qsort (IndexArray, 6, sizeof(int), compareInt);
  for (n=0; n<6; n++)
  printf ("%d  ",ValueArrayI[IndexArray[n]]);
  printf("\n");
 
  //FLOAT SORT
  qsort (IndexArray, 6, sizeof(int), compareFloat);
  for (n=0; n<6; n++)
     printf ("%f  ",ValueArrayF[IndexArray[n]]);
  printf("\n"); 
  return 0;
}


Well, I would not call it easy

Apparently, there is a new C++ standard in the pipeline with type-specific sorts - much more efficient.

Charles

[Patrice Terrier]

Charles,

Thank you, but finaly i came along with my own QuickSort (something i can understand  )

Example:
   short A1[10] = { 2, 1, 3, 6, 8, 7, 0, 9, 4, 5 };
   short A2[10] = { 7, 8, 6, 3, 1, 2, 9, 0, 5, 4 };
   SortShortTagArray (A1, A2, sizeof(A1) / sizeof(A1[0]));

void SortShortTagArray (OUT short A1[], OUT short A2[], IN long nCount) {

    long nStack[1000];
    long nBeg = 0;
    long nEnd = nCount - 1;
    long nB, nE, nS, nPiv;
    nB = nE = nS = nPiv = 0;

    do {
        do {
            nPiv = (long) ((nEnd + nBeg) / 2);
            nB = nBeg;
            nE = nEnd;
            do {
                while (A1[nB] < A1[nPiv]) {
                    ++nB;
                }
                while (A1[nE] > A1[nPiv]) {
                    --nE;
                }
                if (nB > nE) { break; }
                if (nB < nE) {
                    swap(A1[nB],A1[nE]);
                    swap(A2[nB],A2[nE]); // <---- TagArray
                }
                ++nB;
                --nE; }
            while (nB <= nE);

            if (nB < nEnd) {
                nStack[nS] = nB;
                nStack[nS + 1] = nEnd;
                nS += 2;
            }

            nEnd = nE; }
        while (nBeg < nEnd);

        if (nS == 0) { break; }
        nS -= 2;
        nBeg = nStack[nS];
        nEnd = nStack[nS + 1]; }

    while(-1);

}

[Patrice Terrier]

In order to use SortShortTagArray with <vector> instead of C Array,
then use this :

void SortShortTagArray (OUT vector<short> &A1, OUT vector<short> &A2, IN long nCount) {

[Charles Pegge]

I have not tried the pivot method, Patrice. I use merge which sorts with  n/2 * log2(n-1) comparisons or less.

If you were sorting a pack of cards you would group them into 26 pairs with the highest value cards on top, then merge the pairs into 4s then into 8s ...picking the lowest cards first, until you end up with one pile. The code must be able to handle uneven piles correctly.