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.

[Stefan Midegaal]

only for Information.. 

your SortShortTagArray is wrong..

i have delete it and replace with 5 Line of code.
her operation of Knobs as well..

your use a Angle of 270° instead of 90° for the Tick Knob.
and many other Trouble also which i have add\fixed by me self.

[Brian Alvarez]

What a coincidence, i was going to do this in the next few days. I need to support TAGARRAY so that PLuriBASIC can compile itself as a 64 BIT compiler.

I need to be able to pass an array of any datatype as TAGARRAY.

[Stefan Midegaal]

What a coincidence, i was going to do this in the next few days. I need to support TAGARRAY so that PLuriBASIC can compile itself as a 64 BIT compiler.

I need to be able to pass an array of any datatype as TAGARRAY.

but not the function from Patrice whichs Fails.
TAGARRAY = Quicksort
quicksort is too error prone
using BubbleSort with 5 Line of Code and all works fine.

greets

[Patrice Terrier]

Did you realy run the above code?

If you run it, here is what you got for the sorted A2 tagarray
   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]));

A2[0] = 9
A2[1] = 8
A2[2] = 7
A2[3] = 6
A2[4] = 5
A2[5] = 4
A2[6] = 3
A2[7] = 2
A2[8] = 1
A2[9] = 0

This is exactly what i was intended for.

[Stefan Midegaal]

Did you realy run the above code?

If you run it, here is what you got for the sorted A2 tagarray
   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]));

A2[0] = 9
A2[1] = 8
A2[2] = 7
A2[3] = 6
A2[4] = 5
A2[5] = 4
A2[6] = 3
A2[7] = 2
A2[8] = 1
A2[9] = 0

This is exactly what i was intended for.

using Bubblesort is faster and safe
and using as say before max 10 line of code.

greets

[Patrice Terrier]

The problem was to emulate the PowerBASIC tagarray.
If you have a good C++ replacement, why don't you post it there, rather than saying than this code doesn't work, that is a false allegation.

Trolling is not the best way to make you friends and help others.

[Patrice Terrier]

Emil

Please use your real name, that is a mandatory to post on this forum.

This thread was to post a C++ arraytag replacement.
Delphi code is of no use there, because nobody of us is using it.

You are welcome to post your bubble sort replacement if converted to C++ to fullfill the purpose of this thread.

[Stefan Midegaal]

ok my last post.

Code Select Expand

void BubbleSwap(OUT short Value1, short Value2) {
 
short lTemp;
lTemp = Value1;
Value1 = Value2;
Value2 = lTemp;
}

void BubbleSort(OUT vector<short> &A1, OUT vector<short> &A2, IN long nCount) {
long IntI, IntK;

--nCount;

for (IntI = 0; IntI < nCount; IntI++) {
for (IntK = (IntI + 1); IntK < nCount; IntK++) {
if (A1[IntI] > A1[IntK]) {
BubbleSwap(A1[IntI], A1[IntK]);
BubbleSwap(A2[IntI], A2[IntK]);
}
}
}
}

works 100% with GDPlus

bye

[Patrice Terrier]

Emil

To produce the same result than in SortShortTagArray

Here is how it must be written for C++:

Code Select Expand

void BubbleSort(OUT short A1[], OUT short A2[], IN long nCount) {
    long IntI, IntK;
    for (IntI = 0; IntI < nCount; IntI++) {
        for (IntK = (IntI + 1); IntK < nCount; IntK++) {
            if (A1[IntI] > A1[IntK]) {
                swap(A1[IntI], A1[IntK]);
                swap(A2[IntI], A2[IntK]);
            }
        }
    }
}

Note: The original GDPlus written in PowerBASIC uses tagarray.

QuickSort BubbleSort comparison.
https://www.quora.com/Which-is-faster-quick-sort-or-bubble-sort-and-why

Thank you.