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:      445.7 [445.7, 445.7]
#>    ea_id region      province commune urban_rural population households area_km2
#>  * <int> <fct>       <fct>    <fct>   <fct>            <dbl>      <int>    <dbl>
#>  1 29502 Boucle du … Bale     Bana    Rural              168         22     6.72
#>  2  8912 Boucle du … Bale     Pompoi  Rural              802        109     0.72
#>  3  9641 Boucle du … Banwa    Sanaba  Rural              825        105     8.83
#>  4 10935 Boucle du … Banwa    Tansila Rural              173         21     9.23
#>  5 21106 Boucle du … Kossi    Bouras… Rural               39          4     3.34
#>  6  7017 Boucle du … Kossi    Madouba Rural              599         74     0.74
#>  7 21046 Boucle du … Mouhoun  Bondok… Rural              336         51     5.12
#>  8  8198 Boucle du … Mouhoun  Ouarko… Rural              168         23     8.6 
#>  9 44475 Boucle du … Mouhoun  Tcheri… Rural              262         42     0.37
#> 10 11692 Boucle du … Nayala   Yaba    Rural             1305        172     1.77
#> # ℹ 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:      222.85 [68.83, 376.87]
#>    ea_id region      province commune urban_rural population households area_km2
#>  * <int> <fct>       <fct>    <fct>   <fct>            <dbl>      <int>    <dbl>
#>  1 11801 Boucle du … Bale     Bagassi Rural              102         12     9.29
#>  2  8409 Boucle du … Bale     Ouri    Rural               87         11    10.6 
#>  3  6294 Boucle du … Banwa    Kouka   Rural             2830        390     2.2 
#>  4 23835 Boucle du … Banwa    Solenzo Rural             1000        134     9.13
#>  5 11059 Boucle du … Banwa    Tansila Rural              157         19     8.56
#>  6 12736 Boucle du … Kossi    Djibas… Rural              255         33     8.89
#>  7  7004 Boucle du … Kossi    Madouba Rural               37          5     8.39
#>  8 20962 Boucle du … Mouhoun  Bondok… Rural              162         25     5.45
#>  9  3005 Boucle du … Mouhoun  Dourou… Rural              226         32     7.43
#> 10 43731 Boucle du … Mouhoun  Safane  Rural              246         35     8.6 
#> # ℹ 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>