Sort the letters of string in alphabetical order
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
For comparing various sorts, see compare sorts.
For other sorting algorithms, see sorting algorithms, or:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort
- Task
Write a function/program/subroutine/procedure to sort the characters of a string in lexicographical order.
A character for this purpose should be whatever is natural for your language.
Show the results here on this page. White-space may be optionally removed.
The case (uppercase and lowercase) of any letters should be preserved.
Write the function even if your language has a built-in function for it.
ALGOL 68
As with the Wren, Go and probably other samples, this defines a bubble sort to sort the text. Non-alphabetic characters are retained. <lang algol68>BEGIN
# returns s with the characters sorted into lexicographic order # OP LSORT = ( STRING s )STRING: BEGIN [ 1 : UPB s[ @ 1 ] ]CHAR c := s[ @ 1 ]; FOR u FROM UPB c - 1 BY -1 TO LWB c WHILE BOOL sorted := TRUE; FOR p FROM LWB c BY 1 TO u DO IF c[ p ] > c[ p + 1 ] THEN CHAR t := c[ p ]; c[ p ] := c[ p + 1 ]; c[ p + 1 ] := t; sorted := FALSE FI OD; NOT sorted DO SKIP OD; c END; # SORT # print( ( LSORT "The quick brown fox jumps over the lazy dog, apparently", newline ) ) print( ( LSORT "Now is the time for all good men to come to the aid of their country.", newline ) )
END</lang>
- Output:
,Taaabcdeeeefghhijkllmnnoooopppqrrrsttuuvwxyyz .Naaccddeeeeeeffghhhiiiillmmmnnooooooooorrrstttttttuwy
APL
<lang APL>sort ← ⊂∘⍋⌷⊣</lang>
- Output:
sort 'Now is the time for all good men to come to the aid of their country.' .Naaccddeeeeeeffghhhiiiillmmmnnooooooooorrrstttttttuwy
C#
Dubbing the following sorting method as "Slacksort". This "Slacksort" method can easily be adapted for reverse sorting, or removing other characters besides space. Not recommended for larger strings though. <lang csharp>using System; using static System.Console; class Program {
static void Main(string[] args) { var nl = "\n"; var omit_spaces = true; var str = "forever ring programming language"; Write( "working..." + nl ); Write( "Sort the letters of string in alphabitical order:" + nl ); Write( "Input: " + str + nl ); Write( "Output: " ); for (var ch = omit_spaces ? 33 : 0; ch < 256; ch++) foreach (var itm in str) if (ch == itm) Console.Write(itm); Write( nl + "done..." ); }
}</lang> Note: this is a bit of a tribute to the original task description and initial Ring entry, so the typographical errors have intentionally not been corrected.
- Output:
working... Sort the letters of string in alphabitical order: Input: forever ring programming language Output: aaaeeefgggggiilmmnnnooprrrrruv done...
Go
<lang go>package main
import (
"fmt" "sort" "strings"
)
// type and methods satisfying sort.Interface type runeSlice []rune func (x runeSlice) Len() int { return len(x) } func (x runeSlice) Less(i, j int) bool { return x[i] < x[j] } func (x runeSlice) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
func sortLettersInString(s string, trim bool) string { // allow optional removal of whitespace
chars := runeSlice(s) sort.Sort(chars) s = string(chars) if trim { s = strings.TrimLeft(s, " \t\r\n") } return s
}
func main() {
ss := []string{ "forever go programming language", "Now is the time for all good men to come to the aid of their country.", } trims := []bool{true, false} for i, s := range ss { res := sortLettersInString(s, trims[i]) fmt.Printf("Unsorted->%s\n", s) fmt.Printf("Sorted ->%s\n\n", res) }
}</lang>
- Output:
Unsorted->forever go programming language Sorted ->aaaeeefgggggilmmnnoooprrrruv Unsorted->Now is the time for all good men to come to the aid of their country. Sorted -> .Naaccddeeeeeeffghhhiiiillmmmnnooooooooorrrstttttttuwy
Haskell
<lang haskell>import Data.List (sort)
main :: IO () main =
print $ sort "Is this misspelling of alphabetical as alphabitical a joke ?"</lang>
- Output:
" ?Iaaaaaaaabbcceeefghhhiiiiiijkllllllmnoopppsssssttt"
Or, sketching a rough re-phrase of the question:
<lang haskell>import Data.List (partition)
main :: IO () main =
print $ qSort "Is this misspelling of alphabetical as alphabitical a joke ?"
qSort :: (Ord a) => [a] -> [a] qSort [] = [] qSort (x : xs) = qSort below <> (x : qSort above)
where (below, above) = partition (<= x) xs</lang>
- Output:
" ?Iaaaaaaaabbcceeefghhhiiiiiijkllllllmnoopppsssssttt"
Phix
Not sure this algorithm actually has a name, but it certainly ain't the fastest, though it possibly is just about the shortest...
(If pressed I would dub this "Unoptimised bubble sort without the swapped flag")
with javascript_semantics function string_sort(string s) integer temp for n=1 to length(s)-1 do for m=n+1 to length(s) do if s[n]>s[m] then temp = s[n] s[n] = s[m] s[m] = temp end if end for end for return s end function string s = "Now is the time for all good men to come to the aid of their country." printf(1,"Original:\"%s\",\n Sorted:\"%s\"\n Builtin:\"%s\"\n",{s,string_sort(s),sort(s)})
- Output:
Original:"Now is the time for all good men to come to the aid of their country.", Sorted:" .Naaccddeeeeeeffghhhiiiillmmmnnooooooooorrrstttttttuwy" Builtin:" .Naaccddeeeeeeffghhhiiiillmmmnnooooooooorrrstttttttuwy"
case insensitive
You can make this case insensitive by applying lower() on each internal comparison, whereas with the builtins that is done (more efficiently) by extracting a custom tagsort.
(Just to keep you on your toes I've also replaced the algorithm with a fractionaly saner insertion sort.)
with javascript_semantics function string_sort(string s) for i=2 to length(s) do integer j = i, sj = s[j] while j>=2 and lower(sj)<lower(s[j-1]) do s[j] = s[j-1] j -= 1 end while s[j] = sj end for return s end function string s = "Now is the time for all good men to come to the aid of their country." sequence cia = extract(s,custom_sort(lower(s),tagset(length(s)))) printf(1,"Original:\"%s\",\n Sorted:\"%s\"\n Builtin:\"%s\"\n",{s,string_sort(s),cia})
- Output:
Original:"Now is the time for all good men to come to the aid of their country.", Sorted:" .aaccddeeeeeeffghhhiiiillmmmNnnooooooooorrrstttttttuwy" Builtin:" .aaccddeeeeeeffghhhiiiillmmmNnnooooooooorrrstttttttuwy"
Python
<lang python>Sorted string
from functools import reduce
- qSort :: [a] -> [a]
def qSort(xs):
Sorted elements of the list xs, where the values of xs are assumed to be of some orderable type. if xs: h = xs[0] below, above = partition( lambda v: v <= h )(xs[1:])
return qSort(below) + [h] + qSort(above) else: return []
- ------------------------- TEST -------------------------
def main():
A character-sorted version of a test string print(quoted('"')( .join(qSort(list( "Is this misspelling of alphabetical as alphabitical a joke ?" ))) ))
- ----------------------- GENERIC ------------------------
- partition :: (a -> Bool) -> [a] -> ([a], [a])
def partition(p):
The pair of lists of those elements in xs which respectively do, and don't satisfy the predicate p. def go(a, x): ts, fs = a return (ts + [x], fs) if p(x) else (ts, fs + [x]) return lambda xs: reduce(go, xs, ([], []))
- quoted :: Char -> String -> String
def quoted(c):
A string flanked on both sides by a specified quote character. return lambda s: c + s + c
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
" ?Iaaaaaaaabbcceeefghhhiiiiiijkllllllmnoopppsssssttt"
Raku
<lang perl6>sub sort_within_string ( $_ is copy ) {
constant @lexographic_order = sort *.fc, map &chr, 1..255;
return join , gather for @lexographic_order -> $l { my $count = s:g/$l//; take $l x $count; LAST { warn "Original string had non-ASCII chars: {.raku}" if .chars } }
} say trim .&sort_within_string for q:to/END/.lines; The quick brown fox jumps over the lazy dog, apparently Now is the time for all good men to come to the aid of their country. END </lang>
- Output:
,aaabcdeeeefghhijkllmnnoooopppqrrrsTttuuvwxyyz .aaccddeeeeeeffghhhiiiillmmmNnnooooooooorrrstttttttuwy
REXX
For REXX, it is normally faster to convert a string of characters to a one─character array of characters,
sort the array, and then convert the array back to a (simple) string.
A simple bubble sort is used for this example.
The particular string used is from a typing drill devised by Charles E. Weller in the early 20th century. <lang rexx>/*REXX program sorts an array (of any kind of items) using the bubble─sort algorithm.*/ parse arg y /*generate the array elements (items).*/ if y= then y= "Now is the time for all good men to come to the aid of their country."
say 'before sort: ───►'y"◄───" /*show the before string of characters*/
call make@ y /*convert a string into an array (@.) */ call bSort # /*invoke the bubble sort with # items.*/ call makeS /*convert an array (@.) into a string. */
say ' after sort: ───►'$"◄───" /*show the before string of characters*/
exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ bSort: procedure expose @.; parse arg n /*N: is the number of @ array elements.*/
do m=n-1 by -1 until ok; ok= 1 /*keep sorting the @ array until done.*/ do j=1 for m; k= j+1; if @.j<=@.k then iterate /*elements in order? */ _= @.j; @.j= @.k; @.k= _; ok= 0 /*swap two elements; flag as not done.*/ end /*j*/ end /*m*/; return
/*──────────────────────────────────────────────────────────────────────────────────────*/ make@: parse arg z; #= length(z); do j=1 for #; @.j= substr(z, j, 1); end; return makeS: parse arg a; $=; do j=1 for #; $= $ || @.j; end; return</lang>
- output when using the default input:
before sort: ───►Now is the time for all good men to come to the aid of their country.◄─── after sort: ───► .Naaccddeeeeeeffghhhiiiillmmmnnooooooooorrrstttttttuwy◄───
Ring
<lang ring> see "working..." + nl see "Sort the letters of string in alphabitical order:" + nl str = "forever ring programming language" see "Input: " + str + nl
for n = 1 to len(str)-1
for m = n+1 to len(str) if ascii(str[n]) > ascii(str[m]) temp = str[n] str[n] = str[m] str[m] = temp ok next
next
str = substr(str," ","") see "Output: " + str + nl see "done..." + nl </lang>
- Output:
working... Sort the letters of string in alphabitical order: Input: forever ring programming language Output: aaaeeefgggggiilmmnnnooprrrrruv done...
Wren
Well, we'll write a function for a bubble sort which we don't have in Wren-sort because it's normally much slower than the other methods. However, it's fast enough here. <lang ecmascript>var bubbleSort = Fn.new { |s, trim| // allow optional removal of whitespace
var chars = s.toList var n = chars.count while (true) { var n2 = 0 for (i in 1...n) { if (chars[i - 1].codePoints[0] > chars[i].codePoints[0]) { chars.swap(i, i - 1) n2 = i } } n = n2 if (n == 0) break } s = chars.join() return trim ? s.trim() : s
}
var strs = [
["forever wren programming language", true], ["Now is the time for all good men to come to the aid of their country.", false]
] for (str in strs) {
System.print(["Unsorted->" + str[0], "Sorted ->" + bubbleSort.call(str[0], str[1])].join("\n")) System.print()
}</lang>
- Output:
Unsorted->forever wren programming language Sorted ->aaaeeeefggggilmmnnnooprrrrruvw Unsorted->Now is the time for all good men to come to the aid of their country. Sorted -> .Naaccddeeeeeeffghhhiiiillmmmnnooooooooorrrstttttttuwy
XPL0
<lang XPL0>string 0; \use zero-terminated strings
func StrLen(Str); \Return number of characters in an ASCIIZ string char Str; int I; for I:= 0 to -1>>1 do
if Str(I) = 0 then return I;
func Sort(Str); \Bubble sort string Str char Str; int J, I, T; [for J:= StrLen(Str)-1 downto 0 do
for I:= 0 to J-1 do if Str(I) > Str(I+1) then [T:= Str(I); Str(I):= Str(I+1); Str(I+1):= T];
return Str; ];
[Text(0, Sort("The quick brown fox jumps over the lazy dog.")); CrLf(0); Text(0, Sort("Pack my box with five dozen liquor jugs.")); CrLf(0); ]</lang>
- Output:
.Tabcdeeefghhijklmnoooopqrrstuuvwxyz .Pabcdeefghiiijklmnoooqrstuuvwxyz