Sort the letters of string in alphabetical order

Sort the letters of string in alphabetical order is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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:

O(n logn) sorts

Heap sort | Merge sort | Patience sort | Quick sort

O(n log²n) sorts
Shell Sort

O(n²) 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

Works with: Dyalog 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

As in the case of the Wren entry, we write a function to bubble sort the characters of a string since this method is not, of course, used in Go's standard 'sort' package. <lang go>package main

import (

   "fmt"
   "strings"

)

func bubbleSort(s string, trim bool) string { // allow optional removal of whitespace

   chars := []rune(s)
   n := len(chars)
   for {
       n2 := 0
       for i := 1; i < n; i++ {
           if chars[i-1] > chars[i] {
               tmp := chars[i]
               chars[i] = chars[i-1]
               chars[i-1] = tmp
               n2 = i
           }
       }
       n = n2
       if n == 0 {
           break
       }
   }
   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 := bubbleSort(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>main :: IO () main =

 print $
   qSort
     "Is this misspelling of alphabetical as alphabitical a joke ?"

qSort :: (Ord a) => [a] -> [a] qSort [] = [] qSort (x : xs) = cmp (<=) <> (x : cmp (>))

 where
   cmp p = qSort [v | v <- xs, p v x]</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

1. 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 []

1. ------------------------- 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 ?"
       )))
   ))

1. ----------------------- GENERIC ------------------------

1. 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, ([], []))

1. quoted :: Char -> String -> String

def quoted(c):

   A string flanked on both sides
      by a specified quote character.
   
   return lambda s: c + s + c

1. 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