シュワルツ変換（シュワルツへんかん、）は、リストの要素のソートを効率良く行うためのプログラミングの手法の一つである。 このイディオム は、要素の順序が実際には要素のあるプロパティ（キー）の順序に基づいていて、キーの計算に多くの計算資源を要するため計算回数を最小限にしたい状況で行う比較ソートに適している。シュワルツ変換の特徴として、名前付きの一時配列を使わないことが挙げられる。
シュワルツ変換は LISP において （DSU）として知られるイディオムの一種であり、一時的に入力要素とキーを関連付けることでキーの再計算を避けるイディオムである。このアプローチはメモ化に似ていて、メモ化では特定の入力値に関連しているキーの再計算を避けている。比較すると、シュワルツ変換は各入力要素のキーを計算回数が厳密に一度であることを保証する。ただし、入力要素に重複がある場合、同値な要素に対して複数回キーの計算を行う。
シュワルツ変換の名はランダル・L・シュワルツ（）に因む。シュワルツは Perl 5 リリース直後の1994年にこのイディオムを Perl で初めて実装した。「シュワルツ変換」の語は専ら Perl の文脈でのみ用いられてきたが、後に Python など他のプログラミング言語のユーザの間でも、類似のイディオムに言及する際に用いられるようになった。しかしこのアルゴリズムは、シュワルツによる特定のイディオムとして Perl コミュニティの間で普及するより以前に、既に他の言語で（特定の名前を与えられずに）用いられている。「シュワルツ変換」の語は特定のイディオムを示すのであって、一般のアルゴリズムを示すのではない。
例として、リスト ("aaaa","a","aa") を各語の長さに基づいて並び替えることを考える。 まず文字列と長さの配列からリスト (["aaaa",4],["a",1],["aa",2]) を生成し（）、次にタプルの数値に基づいてこのリストをソートし (["a",1],["aa",2],["aaaa",4]) を得て（）、最後にソート済みリスト要素から数値を取り除き（）、目的のリスト ("a","aa","aaaa") を得る。このアルゴリズムの Perl での実装を以下に示す： @sorted = map { $_-> } sort { $a-> <=> $b-> or $a-> cmp $b-> } # 先に長さを比較し、長さの等しい場合のみ文字列の比較を行う map { [$_, length($_)] } # 文字列の長さを計算する @unsorted;
Perl 一般のシュワルツ変換は以下である:
@sorted = map { $_-> } sort { $a-> cmp $b-> or $a-> cmp $b-> } map { [$_, foo($_)] } @unsorted;
ここで foo($_) は $_（リスト要素）を順番に受け取り、リスト要素の代わりに比較に使う値を与える式を表す。
上記コードは右から左へ（あるいは下から上へ）順に: ソート元のリスト @unsorted は map 操作へ渡され、各要素は自分自身とソート順を決定する値（キー）からなる配列にラップされる（結果は [元要素, キー] の未ソートのリスト） map されたリストを sort に渡し、直前に計算したキー基づいてソートする（結果は [元要素, キー] のソート済みリスト） 最後に map でリスト内の配列から目的の要素を取り出し、元リストのソート結果を得る（結果は元要素のソート済みリスト）
最初の map 操作でリスト要素と対応するキーを無名配列に持たせているが、Perl においてこれらの無名配列は、ソート処理が完了した直後にガベージコレクタが呼び出されることが保証されている。
効率 シュワルツ変換を用いずソートする場合、例えば Perl では以下のように書ける： @sorted = sort { foo($a) cmp foo($b) } @unsorted;
コードは単純になるが、この素朴な方法は、キー関数 の計算が高価になる場合、シュワルツ変換の方法より非効率となる。それは素朴な実装では2要素の比較が必要となるたびに、括弧内のコードが評価されるためである。最適比較ソートの比較の計算量は （ここで はリストの長さ）であり、素朴な実装では一度の比較のたび が 2 回呼び出されるため、 回だけ が呼ばれる。対照的に、シュワルツ変換の方法では、最初の 操作の段階でソート対象のリストの各要素に対し 1 回だけ が呼び出されるため、合計の呼び出し回数は 回となる。
しかし、関数 が比較的安価である場合、シュワルツ変換は必ずしも素朴な実装より効率的ではなく、（decorate-undecorate による）追加のオーバーヘッドのために素朴な実装より計算量を要することがある。
利用例
歴史 オンライン上で確認できるシュワルツ変換の例としては、1994年12月16日にランダル・シュワルツがニュースグループ comp.unix.shell のスレッドに投稿、また comp.lang.perl へのクロスポストが最初である。スレッドは、下記の形式のリストの行末の単語でソートを行うにはどうすればいいか、という質問で始められている（リストは元の投稿からの抜粋）。
adjn:Joshua Ng adktk:KaLap Timothy Kwong admg:Mahalingam Gobieramanan admln:Martha L. Nangalama
シュワルツはこの質問の回答として以下のコードを示した： #!/usr/bin/perl require 5; # New features, new bugs! print map { $_-> } sort { $a-> cmp $b-> } map { [$_, /(\S+)$/] } <>;
このコードは以下の結果を与える：
admg:Mahalingam Gobieramanan adktk:KaLap Timothy Kwong admln:Martha L. Nangalama adjn:Joshua Ng
"" という語そのものは、トム・クリスチャンセンの投稿に由来する。クリスチャンセンは後に、名付けをする意図はなく、単に元の投稿を示しただけであったことを明らかにしている。最終的にクリスチャンセンは "" という名を提案したが、普及しなかった（この命名は "schwartz" がドイツ語で英語の "black" を意味することから来る洒落である）。
他言語との比較
いくつかの Perl 以外のプログラミング言語は、シュワルツ変換（DSU）と同等の最適化のためのインタフェースを提供している。
Python Python 2.4 より以前は、ユーザは LISP 由来の decorate–sort–undecorate (DSU) イディオム を用い、大抵はリスト要素のオブジェクトをタプル にラップしてソートしていた。
Python 2.4 以降では、 関数と in-place な メソッドのいずれも、引数 を（Perl のコード例の に相当する）キー関数をユーザ側で指定することができるようになった。
Python 3 から、キー関数はユーザ定義のソート順序を与える唯一の方法となり、それ以前に提供されていた比較関数の引数は廃止された。
Ruby Ruby 1.8.6 以降、抽象クラス （これは を含む）は メソッドを持つ。 は（Perl の例での のような）「キー関数」をコードブロックとして指定できる。
D言語
Racket
PHP
Elixir
Raku
出典
外部リンク
Sorting with the Schwartzian Transform by Randal L. Schwartz Mark-Jason Dominus explains the Schwartzian Transform http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52234 Python Software Foundation (2005). 1.5.2 I want to do a complicated sort: can you do a Schwartzian Transform in Python?. Retrieved June 22, 2005. Memoize Perl module - making expensive functions faster by caching their results.