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.