Zig 0.17.0-dev (Split by item)

Shortcut keys
?
Show these tips
S
Focus search field
Esc
Clear focus & close tips
U
Jump to source code
↑
Move up in search results
↓
Move down in search results
↵
Go to active search result
This is an example of documentation generated by ZigDoc, an alternative to Zig's built-in Auto Doc feature. See also examples in other modes/formats. The project being documented here (as the example) is the Zig standard library. Private Function

chosePivot

Private Function
std.sort.pdq.chosePivot
fn chosePivot(a: usize, b: usize, pivot: *usize, context: anytype) Hint

chooses a pivot in items[a..b]. swaps likely_sorted when items[a..b] seems to be already sorted.

Params

  • a: usize
  • b: usize
  • pivot: *usize
  • context

File

sort/pdq.zig:350
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
fn chosePivot(a: usize, b: usize, pivot: *usize, context: anytype) Hint {
    // minimum length for using the Tukey's ninther method
    const shortest_ninther = 50;
    // max_swaps is the maximum number of swaps allowed in this function
    const max_swaps = 4 * 3;

    const len = b - a;
    const i = a + len / 4 * 1;
    const j = a + len / 4 * 2;
    const k = a + len / 4 * 3;
    var swaps: usize = 0;

    if (len >= 8) {
        if (len >= shortest_ninther) {
            // find medians in the neighborhoods of `i`, `j` and `k`
            sort3(i - 1, i, i + 1, &swaps, context);
            sort3(j - 1, j, j + 1, &swaps, context);
            sort3(k - 1, k, k + 1, &swaps, context);
        }

        // find the median among `i`, `j` and `k` and stores it in `j`
        sort3(i, j, k, &swaps, context);
    }

    pivot.* = j;
    return switch (swaps) {
        0 => .increasing,
        max_swaps => .decreasing,
        else => .unknown,
    };
}