ucw/doc/sort.txt

   1 Sorting
   2 =======
   3
   4 A very common need is sorting data. Therefore libUCW contains few
   5 routines to accomplish that task. They are much more universal than
   6 qsort(), since they allow you to sort structures indexed by a macro,
   7 sort data externally, if they do not fit into memory, merge data with
   8 the same keys and sort data of variable length.
   9
  10 All routines described below are <<generic:,generic algorithms>>.
  11
  12 - <<array-simple,Simple array sorting>>
  13   * <<mandatory-simple,Mandatory macros>>
  14   * <<optional-simple,Optional macros>>
  15   * <<example-simple,Example>>
  16 - <<array,Advanced array sorting>>
  17 - <<external,External sorting>>
  18
  19 [[array-simple]]
  20 Simple array sorting
  21 --------------------
  22
  23 If you want to sort some data in memory and you aren't too picky about
  24 setting how, you just use the routine defined in
  25 `sorter/array-simple.h`. It is an optimised hybrid
  26 quick-sort/insert-sort algorithm (quick-sort is used to split the
  27 input into small parts, each is then sorted by insert-sort).
  28
  29 You need to define few macros and include the header. You get a
  30 sorting function in return. It will be called
  31 <<fun__GENERIC_LINK_|ASORT_PREFIX|sort|,`ASORT_PREFIX(sort)`>>.
  32
  33 [mandatory-simple]
  34 Mandatory macros
  35 ~~~~~~~~~~~~~~~~
  36 - `ASORT_PREFIX(name)` -- The identifier generating macro.
  37 - `ASORT_KEY_TYPE` -- Data type of a single array entry key.
  38
  39 [optional-simple]
  40 Optional macros
  41 ~~~~~~~~~~~~~~~
  42 - `ASORT_ELT(i)` -- Indexing macro. Returns the key of the
  43   corresponding entry. If not provided, usual array with sequential
  44   indexing is assumed.
  45 - `ASORT_LT(x,y)` -- Comparing macro. If not provided, compares by the
  46   `<` operator.
  47 - `ASORT_SWAP(i,j)` -- Swap elements with indices `i` and `j`. If not
  48   provided, it assumes `ASORT_ELT` is l-value and it just swaps keys.
  49 - `ASORT_TRESHOLD` -- Sequences of at most this amount of elements are
  50   sorted by quick-sort, smaller are sorted by insert-sort. Defaults to
  51   `8` (result of experimentation).
  52 - `ASORT_EXTRA_ARGS` -- Pass some extra arguments to the function.
  53   They are visible from all the macros. Must start with a comma.
  54
  55 !!ucw/sorter/array-simple.h ASORT_PREFIX
  56
  57 [example-simple]
  58 Example
  59 ~~~~~~~
  60
  61 Let's sort an array of integers, in the usual way.
  62
  63   #define ASORT_PREFIX(X) intarr_##X
  64   #define ASORT_TYPE int
  65   #include <ucw/sorter/array-simple.h>
  66
  67 This generates an intarr_sort(int *array, uns array_size) function that
  68 can be used the obvious way.
  69
  70 A more complicated example could be sorting a structure, where items
  71 with odd indices are stored in one array, even in another. Each item
  72 could be a structure containing a string and an integer. We would like
  73 to sort them by the strings.
  74
  75   struct elem {
  76     char *string;
  77     int integer;
  78   };
  79
  80   #include <string.h>   // Because of strcmp
  81   #define ASORT_PREFIX(X) complicated_##X
  82   #define ASORT_TYPE struct elem
  83   #define ASORT_ELT(i) ((i % 2 ? even_array : odd_array)[i / 2])
  84   #define ASORT_LT(x, y) (strcmp((x).string, (y).string) < 0)
  85   #define ASORT_EXTRA_ARGS , struct elem *odd_array, struct elem *even_array
  86   #include <ucw/sorter/sorter/array-simple.h>
  87
  88 Now we got a complicated_sort(uns array_size, struct elem *odd_array,
  89 struct *even_array) function to perform our sorting.