Skip to contents

Serpentine Sorting for Implicit Stratification

Source: R/sort.R
serp.Rd

serp() implements hierarchic serpentine sorting (also called "snake" sorting), transforming a multi-dimensional hierarchy into a one-dimensional path that preserves spatial contiguity. This is the algorithm used by SAS PROC SURVEYSELECT with SORT=SERP.

Serpentine sorting alternates direction at each hierarchy level:

  • First variable: ascending

  • Second variable: ascending in odd groups of first, descending in even groups

  • Third variable: alternates based on combined grouping of first two

  • And so on...

This provides implicit stratification when combined with systematic or sequential sampling, ensuring samples spread evenly across geographic/administrative hierarchies.

Usage

serp(...)

Arguments

...

Columns to sort by, in hierarchical order (e.g., region, district, commune). Used inside dplyr::arrange(), similar to dplyr::desc().

Value

A numeric vector (sort key) for use by dplyr::arrange().

Details

Algorithm

The algorithm builds a composite sort key by:

  1. Converting each variable to integer ranks

  2. For variable i, determining group membership from variables 1..(i-1)

  3. If the cumulative group number is even, flipping ranks (descending)

  4. Using multi-column ordering to produce final sort positions

Use with Systematic Sampling

Serpentine sorting is particularly effective with systematic sampling. By ordering the frame in a snake-like pattern, a systematic sample automatically spreads across all regions and sub-regions.

Comparison with Nested Sorting

Standard sorting creates large "jumps" at hierarchy boundaries. Serpentine sorting minimizes these by reversing direction – the last district of region 1 is adjacent to the last district of region 2.

References

Chromy, J. R. (1979). Sequential sample selection methods. Proceedings of the Survey Research Methods Section, ASA, 401-406.

Chromy, J. R., & Williams, R. L. (1980). SAS sample selection macros. Proceedings of the Fifth Annual SAS Users Group International, 392-396.

See also

dplyr::arrange(), dplyr::desc()

Examples

library(dplyr)
#> 
#> Attaching package: ‘dplyr’
#> The following objects are masked from ‘package:stats’:
#> 
#>     filter, lag
#> The following objects are masked from ‘package:base’:
#> 
#>     intersect, setdiff, setequal, union

# Basic serpentine sorting with mtcars
mtcars |>
  arrange(serp(cyl, gear, carb)) |>
  select(cyl, gear, carb) |>
  head(15)
#>                cyl gear carb
#> Toyota Corona    4    3    1
#> Merc 240D        4    4    2
#> Merc 230         4    4    2
#> Honda Civic      4    4    2
#> Volvo 142E       4    4    2
#> Datsun 710       4    4    1
#> Fiat 128         4    4    1
#> Toyota Corolla   4    4    1
#> Fiat X1-9        4    4    1
#> Porsche 914-2    4    5    2
#> Lotus Europa     4    5    2
#> Ferrari Dino     6    5    6
#> Mazda RX4        6    4    4
#> Mazda RX4 Wag    6    4    4
#> Merc 280         6    4    4

# Compare nested vs serpentine sorting
# Nested: gear always ascending within cyl
mtcars |>
  arrange(cyl, gear) |>
  select(cyl, gear) |>
  head(12)
#>                cyl gear
#> Toyota Corona    4    3
#> Datsun 710       4    4
#> Merc 240D        4    4
#> Merc 230         4    4
#> Fiat 128         4    4
#> Honda Civic      4    4
#> Toyota Corolla   4    4
#> Fiat X1-9        4    4
#> Volvo 142E       4    4
#> Porsche 914-2    4    5
#> Lotus Europa     4    5
#> Hornet 4 Drive   6    3

# Serpentine: gear direction alternates by cyl group
mtcars |>
  arrange(serp(cyl, gear)) |>
  select(cyl, gear) |>
  head(12)
#>                cyl gear
#> Toyota Corona    4    3
#> Datsun 710       4    4
#> Merc 240D        4    4
#> Merc 230         4    4
#> Fiat 128         4    4
#> Honda Civic      4    4
#> Toyota Corolla   4    4
#> Fiat X1-9        4    4
#> Volvo 142E       4    4
#> Porsche 914-2    4    5
#> Lotus Europa     4    5
#> Ferrari Dino     6    5

# Implicit stratification with systematic sampling
# Sort BFA EAs in serpentine order, then draw systematic sample
sampling_design() |>
  draw(n = 100, method = "systematic") |>
  execute(arrange(bfa_eas, serp(region, province)),
                  seed = 1)
#> # A tbl_sample: 100 × 17
#> # Weights:      149 [149, 149]
#>    ea_id    region   province commune urban_rural population households area_km2
#>  * <chr>    <fct>    <fct>    <fct>   <fct>            <dbl>      <int>    <dbl>
#>  1 EA_00461 Boucle … Bale     Bana    Rural             1348        176     7.3 
#>  2 EA_11103 Boucle … Bale     Poura   Urban             1660        225    19.0 
#>  3 EA_12339 Boucle … Banwa    Solenzo Rural             1077        129    20.5 
#>  4 EA_12897 Boucle … Banwa    Tansila Rural             1205        154    26.6 
#>  5 EA_03729 Boucle … Kossi    Dokui   Rural             1476        236    18.2 
#>  6 EA_12514 Boucle … Kossi    Sono    Rural             1296        187    23.6 
#>  7 EA_03213 Boucle … Mouhoun  Dedoug… Rural              821        146     0.25
#>  8 EA_12920 Boucle … Mouhoun  Tcheri… Rural             1266        152   133.  
#>  9 EA_14010 Boucle … Nayala   Yaba    Rural             1285        173    40.1 
#> 10 EA_07208 Boucle … Sourou   Lankoue Rural              858        115     0.48
#> # ℹ 90 more rows
#> # ℹ 9 more variables: accessible <lgl>, dist_road_km <dbl>,
#> #   food_insecurity_pct <dbl>, cost <dbl>, .weight <dbl>, .sample_id <int>,
#> #   .stage <int>, .weight_1 <dbl>, .fpc_1 <int>

# Combine explicit stratification with serpentine sorting
# Stratify by urban/rural, use serpentine within strata
sampling_design() |>
  stratify_by(urban_rural) |>
  draw(n = 100, method = "systematic") |>
  execute(arrange(bfa_eas, urban_rural, serp(region, province)),
                  seed = 1234)
#> # A tbl_sample: 200 × 17
#> # Weights:      74.5 [26.49, 122.51]
#>    ea_id    region   province commune urban_rural population households area_km2
#>  * <chr>    <fct>    <fct>    <fct>   <fct>            <dbl>      <int>    <dbl>
#>  1 EA_00258 Boucle … Bale     Bagassi Rural             1744        210    30.2 
#>  2 EA_10333 Boucle … Bale     Ouri    Rural              909        109    56.5 
#>  3 EA_06855 Boucle … Banwa    Kouka   Rural             1424        164     9.9 
#>  4 EA_12392 Boucle … Banwa    Solenzo Rural             1294        154    50.5 
#>  5 EA_00754 Boucle … Kossi    Barani  Rural              883        116    18.4 
#>  6 EA_03729 Boucle … Kossi    Dokui   Rural             1476        236    18.2 
#>  7 EA_08677 Boucle … Kossi    Nouna   Rural             1539        200     1.58
#>  8 EA_03160 Boucle … Mouhoun  Dedoug… Rural             1107        196    14.8 
#>  9 EA_10142 Boucle … Mouhoun  Ouarko… Rural             1201        167    41.8 
#> 10 EA_04509 Boucle … Nayala   Gassan  Rural              937        114     1.8 
#> # ℹ 190 more rows
#> # ℹ 9 more variables: accessible <lgl>, dist_road_km <dbl>,
#> #   food_insecurity_pct <dbl>, cost <dbl>, .weight <dbl>, .sample_id <int>,
#> #   .stage <int>, .weight_1 <dbl>, .fpc_1 <int>