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()
...
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:
/* 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:
/* 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
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);
}
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) {
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.
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.
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.
Quote from: Brian Alvarez on April 14, 2018, 03:00:33 AM
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
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.
Quote from: Patrice Terrier on April 14, 2018, 12:13:32 PM
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
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.
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.
ok my last post.
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
Emil
To produce the same result than in SortShortTagArray
Here is how it must be written for C++:
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.