Define a sort key in a given data array using the indicated comparison function, stride and sort order.
Copy constructor (copy semantics).
Assignment (copy semantics).
Try if GenSort can be used for this single key. If it succeeds, it returns the resulting number of elements. Otherwise it returns 0.
- HeapSort = 1
- InsSort = 2
- use Heapsort algorithm
- QuickSort = 4
- use insertion sort algorithm
- NoDuplicates = 8
- use Quicksort algorithm
- Ascending = -1,Descending=1
Class Sort does not sort the data themselves, but
returns an index to them. This gives more flexibility and
allows the sort to be stable; but it is slower.
Very fast sorting of the data themselves can be done with the
functions in class GenSort.
Three sort algorithms are provided:
The sort is a four step process:
Sort sort;
sort.sortKey (idata, TpInt); // define 1st sort key
sort.sortKey (ddata, TpDouble,0,Sort::Descending); // define 2nd sort key
uInt* inx=0;
sort.sort (nrdata, inx);
for (uInt i=0; i<nrdata; i++) { // show sorted data
cout << idata[inx[i]] << " " << ddata[inx[i]] << endl;
}
delete inx;
Now nr contains the nr of records (=nrdata)
and inx an array of (sorted) indices.
The index array inx has to be deleted by the user.
In the second example we sort the data stored in an array of structs on the double (ascending) and the string (descending). We can pass the data to the Sort constructor, and the offsets of the struct elements to the sortKey function.
struct Ts {
String as;
double ad;
}
uInt* inx=0;
Sort sort (tsarr, sizeof(Ts));
sort.sortKey ((char*)&tsarr[0].ad - (char*)tsarr, TpDouble);
sort.sortKey ((char*)&tsarr[0].as - (char*)tsarr, TpString,
Sort::Descending);
sort.sort (nrts, inx);
Note that the first argument in function sortKey gives
the offset of the variable in the struct.
Alternatively, and probably slightly easier, we could pass the data to the sortKey function:
struct Ts {
String as;
double ad;
}
uInt* inx=0;
Sort sort;
sort.sortKey (&tsarr[0].ad, TpDouble, sizeof(Ts));
sort.sortKey (&tsarr[0].as, TpString, sizeof(Ts), Sort::Descending);
sort.sort (nrts, inx);
Finally, we could provide a comparison function for the struct. (The function is shown inline, but should be implemented out-of-line.) This method is not recommended, because it means more work for the user. Moreover, the descending sort on the string has to be coded in the comparison function, which is not very flexible.
struct Ts {
String as;
double ad;
}
int compareTs (const void* val1, const void* val2)
{
const Ts& t1 = *(Ts*)val1;
const Ts& t2 = *(Ts*)val2;
if (t1.ad < t2.ad) return -1;
if (t1.ad > t2.ad) return 1;
if (t1.as < t2.as) return 1; // string must be descending
if (t1.as > t2.as) return -1;
return 0;
}
uInt* inx=0;
Sort sort;
sort.sortKey (tsarr, compareTs, sizeof(Ts));
sort.sort (nrts, inx);
The last example illustrates the use of the Sort::NoDuplicates flag and an input index array. First we remove duplicate strings, and then sort the result.
struct Ts {
String as;
double ad;
}
uInt* inxNoDup=0;
Sort sort;
sort.sortKey (&tsarr[0].as, TpString, sizeof(Ts));
uInt nrout = sort.sort (nrts, inxNoDup, Sort::NoDuplicates);
Sort sort2;
sort2.sortKey (&tsarr[0].ad, TpDouble, sizeof(Ts));
sort2.sortKey (&tsarr[0].as, TpString, sizeof(Ts), Sort::Descending);
uInt* inx=0;
sort2.sort (nrout, inxNoDup, inx);
Enumerate the sort order:
Construct a Sort object for the given data array with elements of elementSize bytes. This data array will be used when an offset is given to the sortKey functions. You can still pass additional data arrays to the sortKey functions.
Copy constructor (copy semantics).
Assignment (copy semantics).
Define a sort key (the most significant key should be defined first). The key contains:
When the data array has been passed to the Sort constructor, the data pointer and the increment arguments can be replaced by a single argument: the offset of the key in each element of the array.
Sort the data array of nrrec records. The result is an array of indices giving the requested order. It returns the number of resulting records. The indices array is resized to that number.
Get all unique records in a sorted array. The array order is
given in the indexVector (as possibly returned by the sort function).
The default indexVector is 0..nrrec-1.
The index of each first unique record is returned in the uniqueVector.
They are indices in the supplied indexVector, so
/src>data[indexVector(uniqueVector(i))]
is giving the i-th unique record.
Note that the records indexed by indexVector(uniqueVector(i))
till indexVector(uniqueVector(i+1)) are all the same.
It returns the number of unique records. The unique array
is resized to that number.
Add a sort key giving a data type or a compare function.
Do an insertion sort, optionally skipping duplicates.
Do a quicksort, optionally skipping duplicates (qkSort is the actual quicksort function).
Do a heapsort, optionally skipping duplicates.
Siftdown algorithm for heapsort.
Compare the keys of 2 records.
Swap 2 indices.