Editing Schwartzian transform (section)

{{Short description|Programming idiom for efficiently sorting a list by a computed key}}
{{More footnotes needed|date=February 2024}}
In [[computer programming]], the '''Schwartzian transform''' is a technique used to improve the efficiency of [[sorting]] a list of items. This [[programming idiom|idiom]]<ref>{{cite book |year=2002 |chapter=2.3 Sorting While Guaranteeing Sort Stability |editor1-last=Martelli |editor1-first=Alex |editor2-last=Ascher |editor2-first=David |title=Python Cookbook |publisher=O'Reilly & Associates |page=[https://archive.org/details/pythoncookbook00mart/page/43 43] |isbn=0-596-00167-3 |quote=This idiom is also known as the 'Schwartzian transform', by analogy with a related Perl idiom. |chapter-url-access=registration |chapter-url=https://archive.org/details/pythoncookbook00mart/page/43 }}</ref> is appropriate for [[comparison sort|comparison-based sorting]] when the ordering is actually based on the ordering of a certain property (the ''key'') of the elements, where computing that property is an intensive operation that should be performed a minimal number of times. The Schwartzian transform is notable in that it does not use named temporary arrays.

The Schwartzian transform is a version of a [[Lisp programming language|Lisp]] idiom known as '''decorate-sort-undecorate''', which avoids recomputing the sort keys by temporarily associating them with the input items. This approach is similar to {{not a typo|[[memoization]]}}, which avoids repeating the calculation of the key corresponding to a specific input value. By comparison, this idiom assures that each input item's key is calculated exactly once, which may still result in repeating some calculations if the input data contains duplicate items.

The idiom is named after [[Randal L. Schwartz]], who first demonstrated it in [[Perl]] shortly after the release of Perl 5 in 1994. The term "Schwartzian transform" applied solely to Perl [[programming language|programming]] for a number of years, but it has later been adopted by some users of other [[programming language|languages]], such as [[Python (programming language)|Python]], to refer to similar idioms in those languages. However, the algorithm was already in use in other languages (under no specific name) before it was popularized among the Perl community in the form of that particular idiom by Schwartz. The term "Schwartzian transform" indicates a specific idiom, and ''not'' the algorithm in general.

For example, to sort the word list ("aaaa","a","aa") according to word length: first build the list (["aaaa",4],["a",1],["aa",2]), then sort it according to the numeric values getting (["a",1],["aa",2],["aaaa",4]), then strip off the numbers and you get ("a","aa","aaaa"). That was the algorithm in general, so it does not count as a transform. To make it a true Schwartzian transform, it would be done in Perl like this:
<syntaxhighlight lang="perl">
@sorted = map  { $_->[0] }
          sort { $a->[1] <=> $b->[1] or $a->[0] cmp $b->[0] } # Use numeric comparison, fall back to string sort on original
          map  { [$_, length($_)] }    # Calculate the length of the string
               @unsorted;
</syntaxhighlight>