NEPLg2 Standard Library - sort
Web Playground
Web Playground

sort: alloc/sort.nepl に関する機能を提供するライブラリ

目的もくてき:

注意ちゅうい:

TEST
#entry main
#target std
#import "std/test" as *
#import "alloc/collections/vec/sort" as *
#import "alloc/collections/vec" as *
#import "core/math" as *
fn mk <()*>Vec<i32>> ():
    let v0 vec_new<i32>;
    let v1 vec_push<i32> v0 3;
    let v2 vec_push<i32> v1 1;
    vec_push<i32> v2 2

fn sorted3 <()*>Vec<i32>> ():
    let v0 vec_new<i32>;
    let v1 vec_push<i32> v0 1;
    let v2 vec_push<i32> v1 2;
    vec_push<i32> v2 3

fn main <()*>()> ():
    sort_quick<i32> mk;
    assert sort_is_sorted<i32> sorted3;
TEST
#entry main
#target std
#import "std/test" as *
#import "alloc/collections/vec/sort" as *
#import "alloc/collections/vec" as *
#import "core/math" as *
fn main <()*>()> ():
    let u0 vec_new<i32>;
    let u1 vec_push<i32> u0 4;
    let u2 vec_push<i32> u1 3;
    let u3 vec_push<i32> u2 2;
    let u4 vec_push<i32> u3 1;
    sort_merge<i32> u4;
    assert true;

sort_lt: 主な用途

目的もくてき:

実装じっそう:

注意ちゅうい:

計算量けいさんりょう:

sort_le: 主な用途

目的もくてき:

実装じっそう:

注意ちゅうい:

計算量けいさんりょう:

sort_gt: 主な用途

目的もくてき:

実装じっそう:

注意ちゅうい:

計算量けいさんりょう:

sort_ge: 主な用途

目的もくてき:

実装じっそう:

注意ちゅうい:

計算量けいさんりょう:

sort_get_unchecked: 主な用途

目的もくてき:

実装じっそう:

注意ちゅうい:

計算量けいさんりょう:

sort_set_unchecked: 主な用途

目的もくてき:

実装じっそう:

注意ちゅうい:

計算量けいさんりょう:

sort_swap: 主な用途

目的もくてき:

実装じっそう:

注意ちゅうい:

計算量けいさんりょう:

sort_is_sorted: 主な用途

目的もくてき:

実装じっそう:

注意ちゅうい:

計算量けいさんりょう:

sort_insertion: 主な用途

目的もくてき:

実装じっそう:

注意ちゅうい:

計算量けいさんりょう:

sort_selection: 主な用途

目的もくてき:

実装じっそう:

注意ちゅうい:

計算量けいさんりょう:

sort_bubble: 主な用途

目的もくてき:

実装じっそう:

注意ちゅうい:

計算量けいさんりょう:

sort_cocktail: 主な用途

目的もくてき:

実装じっそう:

注意ちゅうい:

計算量けいさんりょう:

sort_gnome: 主な用途

目的もくてき:

実装じっそう:

注意ちゅうい:

計算量けいさんりょう:

sort_shell: 主な用途

目的もくてき:

実装じっそう:

注意ちゅうい:

計算量けいさんりょう:

sort_comb: 主な用途

目的もくてき:

実装じっそう:

注意ちゅうい:

計算量けいさんりょう:

sort_quick_partition: 主な用途

目的もくてき:

実装じっそう:

注意ちゅうい:

計算量けいさんりょう:

sort_quick_range: 主な用途

目的もくてき:

実装じっそう:

注意ちゅうい:

計算量けいさんりょう:

sort_quick: 主な用途

目的もくてき:

実装じっそう:

注意ちゅうい:

計算量けいさんりょう:

sort_heap_sift_down: 主な用途

目的もくてき:

実装じっそう:

注意ちゅうい:

計算量けいさんりょう:

sort_heap: 主な用途

目的もくてき:

実装じっそう:

注意ちゅうい:

計算量けいさんりょう:

sort_buf_get

merge sort 用ようの作業さぎょう buffer から値あたいを読よむ

目的もくてき

  • sort_merge_range_data が一時いちじ buffer に退避たいひした要素ようそを、MemPtr<.T> 基準きじゅんで取とり出だせるようにします。

実装じっそう

  • idx * size_of<.T> で byte offset を計算けいさんし、buffer 先頭せんとうから load<.T> します。

注意ちゅうい

  • buf は .T の配列はいれつとして有効ゆうこうである必要ひつようがあります。
  • idx の境界きょうかい確認かくにんは呼よび出だし側がわが担当たんとうします。

計算量けいさんりょう

  • O(1)

sort_buf_set

merge sort 用ようの作業さぎょう buffer へ値あたいを書かく

目的もくてき

  • 一時いちじ buffer に現在げんざいの要素ようそ列れつを複写ふくしゃし、merge 中ちゅうに安定あんていした読よみ取とり元もとを確保かくほします。

実装じっそう

  • idx * size_of<.T> を求もとめ、buffer 先頭せんとうから store<.T> します。

注意ちゅうい

  • buf は .T の配列はいれつとして有効ゆうこうである必要ひつようがあります。
  • val は store<.T> によって buffer へ書かき込こまれます。

計算量けいさんりょう

  • O(1)

sort_merge_range_data

merge sort の 1 区間くかんを再帰的さいきてきに統合とうごうする

目的もくてき

  • data_ptr が指さす [l, r) 区間くかんを merge sort で整列せいれつします。
  • 比較元ひかくもとを壊こわさないため、buf に現在げんざいの内容ないようを退避たいひしてから統合とうごうします。

実装じっそう

  • 中央ちゅうおう mid で 2 分割ぶんかつし、左右さゆうを再帰的さいきてきに sort したあと、buf に複写ふくしゃした要素ようそを 2 本ほんの読よみ取とり位置いちで merge します。

注意ちゅうい

  • data_ptr と buf は .T を r 個分こぶんまで安全あんぜんに読よみ書かきできる領域りょういきである必要ひつようがあります。
  • 境界きょうかい確認かくにんは内部ないぶで省略しょうりゃくしているため、l <= r と十分じゅうぶんな容量ようりょうは呼よび出だし側がわの責任せきにんです。

計算量けいさんりょう

  • 時間じかん計算量けいさんりょうは O(n log n)、追加ついか空間くうかん計算量けいさんりょうは O(n) です。

sort_merge

Vec<.T> を merge sort で破壊的はかいてきに整列せいれつする

目的もくてき

  • 安定あんていな O(n log n) sort として Vec<.T> を昇順しょうじゅんへ並ならべ替かえます。

使用例しようれい

TEST
#entry main
#target std
#import "std/test" as *
#import "alloc/collections/vec" as *
#import "alloc/collections/vec/sort" as *
#import "core/result" as *
fn main <()*>i32> ():
    let v <Vec<i32>>:
        new<i32>
        |> push 3
        |> push 1
        |> push 2
    sort_merge<i32> v;
    0

実装じっそう

  • Vec の data を raw address へ下おろし、.T 配列はいれつ 1 本分ほんぶんの作業さぎょう buffer を alloc_ptr<.T> で確保かくほして sort_merge_range_data を呼よびます。

注意ちゅうい

  • 作業さぎょう buffer 確保かくほに失敗しっぱいした場合ばあいは unwrap_ok により到達不能とうたつふのうになります。現状は sort_merge が Result を返かえさないためです。
  • ソートは in-place なので v の並ならび順じゅんは関数かんすう呼よび出だし後ごに変更へんこうされます。

計算量けいさんりょう

  • 時間じかん計算量けいさんりょうは O(n log n)、追加ついか空間くうかん計算量けいさんりょうは O(n) です。

sort_slice_quick: 生ポインタ配列を quick sort で並べ替える

目的もくてき:

  • data_ptr から始まる長さ len の連続領域を in-place で昇順ソートします。

実装じっそう:

  • sort_quick_range_data を直接呼び出す薄いラッパです。

注意ちゅうい:

  • data_ptr は .T の len 要素ぶん有効である必要があります。
  • メモリ所有権・境界チェックは呼び出し側が管理します。

計算量けいさんりょう:

  • 平均 O(n log n), 最悪 O(n^2)

sort_i32: i32 配列ポインタを in-place で昇順ソートする

目的もくてき:

  • 競技プログラミング向けに sort_i32(ptr, n) の薄い API を提供します。

実装じっそう:

  • sort_slice_quick<i32> を呼び出します。

注意ちゅうい:

  • data_ptr は n 個の i32 が格納された有効な領域である必要があります。

計算量けいさんりょう:

  • 平均 O(n log n), 最悪 O(n^2)

sort_quick_ret: quick sort 後の Vec を返す

目的もくてき:

  • 破壊的ソートを行った同じ Vec を返し、後続処理で検証や連結処理をしやすくします。

実装じっそう:

  • sort_quick を呼んだあと v をそのまま返します。

注意ちゅうい:

  • ソート自体は in-place です。

計算量けいさんりょう:

  • sort_quick と同じです。

sort_heap_ret: heap sort 後の Vec を返す

目的もくてき:

  • 破壊的ソートを行った同じ Vec を返し、後続処理で検証や連結処理をしやすくします。

実装じっそう:

  • sort_heap を呼んだあと v をそのまま返します。

注意ちゅうい:

  • ソート自体は in-place です。

計算量けいさんりょう:

  • sort_heap と同じです。

sort_merge_ret: merge sort 後の Vec を返す

目的もくてき:

  • 破壊的ソートを行った同じ Vec を返し、後続処理で検証や連結処理をしやすくします。

実装じっそう:

  • sort_merge を呼んだあと v をそのまま返します。

注意ちゅうい:

  • ソート自体は in-place です。

計算量けいさんりょう:

  • sort_merge と同じです。

sort: 主な用途

目的もくてき:

  • sort の主な用途と呼び出し方を示します。

実装じっそう:

  • 定義済み処理をそのまま呼び出す薄いラッパで構成されています。

注意ちゅうい:

  • 引数の値は関数呼び出しで移動するため、再利用時は束縛し直してください。

計算量けいさんりょう:

  • 本体処理に準じます。