4
\$\begingroup\$

In this task, you have to write a program, that reads a string with a length of up to 1024 characters and prints it out sorted. In order to make an interesting task from a boring one, I set a few restrictions:

You must not change the contents of any variable. A variable can be assigned only once and must not be changed afterwards. For instance, all of the following constructs are forbidden:

int a = 0;
a = 1;

a = 10;
for (a-->0);

string[12] = a

and many more. What is changing a variable and what not is judged by me.

Additionally, you must not use any sorting function or any library function, that must be "imported" somehow. The only library functions, that are allowed to import are those to print out the result and read in the string, if they are not available whithout importing them.

\$\endgroup\$

closed as off-topic by Dennis Feb 6 '16 at 20:51

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – Dennis
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ Most dynamic languages have a sort function that doesn’t require any sort of import. \$\endgroup\$ – Timwi Apr 12 '11 at 16:41
  • \$\begingroup\$ @Tmwi: All kinds of sorting function are forbidden. \$\endgroup\$ – FUZxxl Apr 12 '11 at 16:47
  • 8
    \$\begingroup\$ So any functional implementation is OK? \$\endgroup\$ – Eelvex Apr 12 '11 at 17:27
  • 2
    \$\begingroup\$ You know, there are plenty of languages that don't even know the concept of a variable. Furthermore, some languages have control-structure-like constructs that are not syntax, but could be considered library functions (e.g. cmdlets in PowerShell). Are those forbidden, too? \$\endgroup\$ – Joey Apr 13 '11 at 5:37
  • 3
    \$\begingroup\$ And the analyzer will re-use registers as needed, which points out the silliness of the constraint: every solution is re-using memory, it's just hidden under one or more layers of language abstraction. In the case of my solution, the stack gets overwritten time and time again or if the compiler does tail call elimination it's the return value that gets overwritten. \$\endgroup\$ – dmckee Apr 15 '11 at 14:48

11 Answers 11

5
\$\begingroup\$

Perl, 89 characters

sub t{return if!@_;my$c=shift;t(grep{$_ lt$c}@_),$c,t(grep{$_ ge$c}@_)}print t split//,<>

This exploits the fact that QuickSort is effectively equivalent to the recurrence relation:

sorted x = () if x is empty, otherwise
           sorted (elements in x less than x[0]) :: x[0] ::
           sorted (elements in x greater than or equal to x[0] except for x[0] itself)

Edit

I originally misread the question and thought I had to sort the input strings, not the characters within a string. Hence my solution grows from 80 to 89 characters.

\$\endgroup\$
5
\$\begingroup\$

Python

s=raw_input()
print chr(0)*s.count(chr(0))+chr(1)*s.count(chr(1))+chr(2)*s.count(chr(2))+chr(3)*s.count(chr(3))+chr(4)*s.count(chr(4))+chr(5)*s.count(chr(5))+chr(6)*s.count(chr(6))+chr(7)*s.count(chr(7))+chr(8)*s.count(chr(8))+chr(9)*s.count(chr(9))+chr(10)*s.count(chr(10))+chr(11)*s.count(chr(11))+chr(12)*s.count(chr(12))+chr(13)*s.count(chr(13))+chr(14)*s.count(chr(14))+chr(15)*s.count(chr(15))+chr(16)*s.count(chr(16))+chr(17)*s.count(chr(17))+chr(18)*s.count(chr(18))+chr(19)*s.count(chr(19))+chr(20)*s.count(chr(20))+chr(21)*s.count(chr(21))+chr(22)*s.count(chr(22))+chr(23)*s.count(chr(23))+chr(24)*s.count(chr(24))+chr(25)*s.count(chr(25))+chr(26)*s.count(chr(26))+chr(27)*s.count(chr(27))+chr(28)*s.count(chr(28))+chr(29)*s.count(chr(29))+chr(30)*s.count(chr(30))+chr(31)*s.count(chr(31))+chr(32)*s.count(chr(32))+chr(33)*s.count(chr(33))+chr(34)*s.count(chr(34))+chr(35)*s.count(chr(35))+chr(36)*s.count(chr(36))+chr(37)*s.count(chr(37))+chr(38)*s.count(chr(38))+chr(39)*s.count(chr(39))+chr(40)*s.count(chr(40))+chr(41)*s.count(chr(41))+chr(42)*s.count(chr(42))+chr(43)*s.count(chr(43))+chr(44)*s.count(chr(44))+chr(45)*s.count(chr(45))+chr(46)*s.count(chr(46))+chr(47)*s.count(chr(47))+chr(48)*s.count(chr(48))+chr(49)*s.count(chr(49))+chr(50)*s.count(chr(50))+chr(51)*s.count(chr(51))+chr(52)*s.count(chr(52))+chr(53)*s.count(chr(53))+chr(54)*s.count(chr(54))+chr(55)*s.count(chr(55))+chr(56)*s.count(chr(56))+chr(57)*s.count(chr(57))+chr(58)*s.count(chr(58))+chr(59)*s.count(chr(59))+chr(60)*s.count(chr(60))+chr(61)*s.count(chr(61))+chr(62)*s.count(chr(62))+chr(63)*s.count(chr(63))+chr(64)*s.count(chr(64))+chr(65)*s.count(chr(65))+chr(66)*s.count(chr(66))+chr(67)*s.count(chr(67))+chr(68)*s.count(chr(68))+chr(69)*s.count(chr(69))+chr(70)*s.count(chr(70))+chr(71)*s.count(chr(71))+chr(72)*s.count(chr(72))+chr(73)*s.count(chr(73))+chr(74)*s.count(chr(74))+chr(75)*s.count(chr(75))+chr(76)*s.count(chr(76))+chr(77)*s.count(chr(77))+chr(78)*s.count(chr(78))+chr(79)*s.count(chr(79))+chr(80)*s.count(chr(80))+chr(81)*s.count(chr(81))+chr(82)*s.count(chr(82))+chr(83)*s.count(chr(83))+chr(84)*s.count(chr(84))+chr(85)*s.count(chr(85))+chr(86)*s.count(chr(86))+chr(87)*s.count(chr(87))+chr(88)*s.count(chr(88))+chr(89)*s.count(chr(89))+chr(90)*s.count(chr(90))+chr(91)*s.count(chr(91))+chr(92)*s.count(chr(92))+chr(93)*s.count(chr(93))+chr(94)*s.count(chr(94))+chr(95)*s.count(chr(95))+chr(96)*s.count(chr(96))+chr(97)*s.count(chr(97))+chr(98)*s.count(chr(98))+chr(99)*s.count(chr(99))+chr(100)*s.count(chr(100))+chr(101)*s.count(chr(101))+chr(102)*s.count(chr(102))+chr(103)*s.count(chr(103))+chr(104)*s.count(chr(104))+chr(105)*s.count(chr(105))+chr(106)*s.count(chr(106))+chr(107)*s.count(chr(107))+chr(108)*s.count(chr(108))+chr(109)*s.count(chr(109))+chr(110)*s.count(chr(110))+chr(111)*s.count(chr(111))+chr(112)*s.count(chr(112))+chr(113)*s.count(chr(113))+chr(114)*s.count(chr(114))+chr(115)*s.count(chr(115))+chr(116)*s.count(chr(116))+chr(117)*s.count(chr(117))+chr(118)*s.count(chr(118))+chr(119)*s.count(chr(119))+chr(120)*s.count(chr(120))+chr(121)*s.count(chr(121))+chr(122)*s.count(chr(122))+chr(123)*s.count(chr(123))+chr(124)*s.count(chr(124))+chr(125)*s.count(chr(125))+chr(126)*s.count(chr(126))+chr(127)*s.count(chr(127))+chr(128)*s.count(chr(128))+chr(129)*s.count(chr(129))+chr(130)*s.count(chr(130))+chr(131)*s.count(chr(131))+chr(132)*s.count(chr(132))+chr(133)*s.count(chr(133))+chr(134)*s.count(chr(134))+chr(135)*s.count(chr(135))+chr(136)*s.count(chr(136))+chr(137)*s.count(chr(137))+chr(138)*s.count(chr(138))+chr(139)*s.count(chr(139))+chr(140)*s.count(chr(140))+chr(141)*s.count(chr(141))+chr(142)*s.count(chr(142))+chr(143)*s.count(chr(143))+chr(144)*s.count(chr(144))+chr(145)*s.count(chr(145))+chr(146)*s.count(chr(146))+chr(147)*s.count(chr(147))+chr(148)*s.count(chr(148))+chr(149)*s.count(chr(149))+chr(150)*s.count(chr(150))+chr(151)*s.count(chr(151))+chr(152)*s.count(chr(152))+chr(153)*s.count(chr(153))+chr(154)*s.count(chr(154))+chr(155)*s.count(chr(155))+chr(156)*s.count(chr(156))+chr(157)*s.count(chr(157))+chr(158)*s.count(chr(158))+chr(159)*s.count(chr(159))+chr(160)*s.count(chr(160))+chr(161)*s.count(chr(161))+chr(162)*s.count(chr(162))+chr(163)*s.count(chr(163))+chr(164)*s.count(chr(164))+chr(165)*s.count(chr(165))+chr(166)*s.count(chr(166))+chr(167)*s.count(chr(167))+chr(168)*s.count(chr(168))+chr(169)*s.count(chr(169))+chr(170)*s.count(chr(170))+chr(171)*s.count(chr(171))+chr(172)*s.count(chr(172))+chr(173)*s.count(chr(173))+chr(174)*s.count(chr(174))+chr(175)*s.count(chr(175))+chr(176)*s.count(chr(176))+chr(177)*s.count(chr(177))+chr(178)*s.count(chr(178))+chr(179)*s.count(chr(179))+chr(180)*s.count(chr(180))+chr(181)*s.count(chr(181))+chr(182)*s.count(chr(182))+chr(183)*s.count(chr(183))+chr(184)*s.count(chr(184))+chr(185)*s.count(chr(185))+chr(186)*s.count(chr(186))+chr(187)*s.count(chr(187))+chr(188)*s.count(chr(188))+chr(189)*s.count(chr(189))+chr(190)*s.count(chr(190))+chr(191)*s.count(chr(191))+chr(192)*s.count(chr(192))+chr(193)*s.count(chr(193))+chr(194)*s.count(chr(194))+chr(195)*s.count(chr(195))+chr(196)*s.count(chr(196))+chr(197)*s.count(chr(197))+chr(198)*s.count(chr(198))+chr(199)*s.count(chr(199))+chr(200)*s.count(chr(200))+chr(201)*s.count(chr(201))+chr(202)*s.count(chr(202))+chr(203)*s.count(chr(203))+chr(204)*s.count(chr(204))+chr(205)*s.count(chr(205))+chr(206)*s.count(chr(206))+chr(207)*s.count(chr(207))+chr(208)*s.count(chr(208))+chr(209)*s.count(chr(209))+chr(210)*s.count(chr(210))+chr(211)*s.count(chr(211))+chr(212)*s.count(chr(212))+chr(213)*s.count(chr(213))+chr(214)*s.count(chr(214))+chr(215)*s.count(chr(215))+chr(216)*s.count(chr(216))+chr(217)*s.count(chr(217))+chr(218)*s.count(chr(218))+chr(219)*s.count(chr(219))+chr(220)*s.count(chr(220))+chr(221)*s.count(chr(221))+chr(222)*s.count(chr(222))+chr(223)*s.count(chr(223))+chr(224)*s.count(chr(224))+chr(225)*s.count(chr(225))+chr(226)*s.count(chr(226))+chr(227)*s.count(chr(227))+chr(228)*s.count(chr(228))+chr(229)*s.count(chr(229))+chr(230)*s.count(chr(230))+chr(231)*s.count(chr(231))+chr(232)*s.count(chr(232))+chr(233)*s.count(chr(233))+chr(234)*s.count(chr(234))+chr(235)*s.count(chr(235))+chr(236)*s.count(chr(236))+chr(237)*s.count(chr(237))+chr(238)*s.count(chr(238))+chr(239)*s.count(chr(239))+chr(240)*s.count(chr(240))+chr(241)*s.count(chr(241))+chr(242)*s.count(chr(242))+chr(243)*s.count(chr(243))+chr(244)*s.count(chr(244))+chr(245)*s.count(chr(245))+chr(246)*s.count(chr(246))+chr(247)*s.count(chr(247))+chr(248)*s.count(chr(248))+chr(249)*s.count(chr(249))+chr(250)*s.count(chr(250))+chr(251)*s.count(chr(251))+chr(252)*s.count(chr(252))+chr(253)*s.count(chr(253))+chr(254)*s.count(chr(254))+chr(255)*s.count(chr(255))
\$\endgroup\$
  • 2
    \$\begingroup\$ And now adapt it for Unicode :P \$\endgroup\$ – Joey Apr 13 '11 at 5:40
  • 6
    \$\begingroup\$ print''.join(map(lambda x:unichr(x)*s.count(unichr(x)),range(0x10000))) would be a lot more compact, but a lot less entertaining. \$\endgroup\$ – user1011 Apr 13 '11 at 6:07
  • \$\begingroup\$ @Joey: Assuming it's written the same way as this, that solution would be 36771719 characters. Unicode goes from 0 to 1114111. Interestingly enough, 1114111 is also a prime number. \$\endgroup\$ – Joey Adams Apr 13 '11 at 23:10
  • \$\begingroup\$ Err, wait, it didn't occur to me that chr only works on 0-255. \$\endgroup\$ – Joey Adams Apr 14 '11 at 7:02
  • \$\begingroup\$ taps foot impatiently \$\endgroup\$ – gnibbler Apr 14 '11 at 7:06
4
\$\begingroup\$

Haskell (70 103 94 82 71 60)

Insertion sort.

m%(x:y)|x>m=m:x:y|2>1=x:m%y
m%_=[m]
main=interact$foldr(%)[]

Edit: Forgot I/O

Edit: Use pattern guards to get rid of if

Edit: Revisions suggested by MtnViewMark

Edit: Replace s with a fold

Edit: Reorder clauses, so base case can match with _

Edit: Change main to implement FUZxxl's suggestion.

\$\endgroup\$
  • \$\begingroup\$ Your answer is neither a complete program nor do you use pattern guards to shorten the code. \$\endgroup\$ – FUZxxl Apr 12 '11 at 18:15
  • \$\begingroup\$ main=getLine>>=putStrLn.s and defining i as an operator: m%[]=[m] etc... will save some characters \$\endgroup\$ – MtnViewMark Apr 12 '11 at 20:02
  • \$\begingroup\$ Replace s with a fold: main=getLine>>=putStrLn.foldr(%)[] \$\endgroup\$ – MtnViewMark Apr 13 '11 at 4:26
  • \$\begingroup\$ You may consider using interact like this: main=interact$foldr(%)[] \$\endgroup\$ – FUZxxl Apr 14 '11 at 15:56
  • \$\begingroup\$ I didn't suggest interact originally before because it will cause the newline character to be sorted in as well. However, now re-reading the question, it is totally silent about handling of newlines. So, yes, great idea! \$\endgroup\$ – MtnViewMark Apr 15 '11 at 0:34
3
\$\begingroup\$

C

Simply by using recursion instead of loops. This particular version only works on characters between '0' and 'z', but that's just to keep the stack from overflowing too often. Supporting all of ASCII.

#include <stdio.h>

void walk(char *s, char m){
    if (*s == '\0') return;
    if (*s == m) putchar(m);
    walk(s+1,m);
}

void sort(char *s, char m){
  walk(s,m);
  if (m<127) sort(s,m+1);
}

int main(int argc, char**argv){
  if (argc > 1) {
    printf("%s: ",argv[1]);
    sort(argv[1],1);
    printf("\n");
  }
}

Sample run:

$ ./a.out  thingamabob
thingamabob: aabbghimnot
$ ./a.out  supercalifragilisticexpalodoucious
supercalifragilisticexpalodoucious: aaacccdeefgiiiiilllooopprrssstuuux
$ ./a.out  "The quick red fox jumped over the lazy brown dog"
The quick red fox jumped over the lazy brown dog:          Tabcdddeeeeefghhijklmnoooopqrrrtuuvwxyz

Too easy, really.

\$\endgroup\$
  • \$\begingroup\$ You sad, it stack-overflows too often? Then your algorithm is probably not good for this task. \$\endgroup\$ – FUZxxl Apr 12 '11 at 18:13
  • 4
    \$\begingroup\$ @FUZxxl: Actually, I never made it overflow the stack, and the size of the stack is an implementation detail. I wouldn't worry about it on Mac System 6 or an Apple ][. More to the point if you set a silly task you get silly answers. \$\endgroup\$ – dmckee Apr 12 '11 at 18:17
  • \$\begingroup\$ @dmckee: Maybe this task was really silly. I had the idea of giving a task to implement something using only constant variables, and chose sorting for this. \$\endgroup\$ – FUZxxl Apr 12 '11 at 18:19
  • 3
    \$\begingroup\$ You misspelt supercalifragilisticexpialidocious! :) \$\endgroup\$ – Timwi Apr 12 '11 at 22:02
  • \$\begingroup\$ @Timwi: LOL. You may be shocked if I every spell anything like that right. \$\endgroup\$ – dmckee Apr 12 '11 at 22:04
3
\$\begingroup\$

C++ (with libgc)

This isn't code-golf, so I went for speed. This implements counting sort. Rather than updating an array (which isn't allowed), it updates a 4-way trie by reconstructing nodes as necessary. It allocates trie nodes on the stack and copies them to the heap every 1000 characters, yielding a 600% performance boost.

This requires libgc, a garbage collector for C/C++. To work on large files (without stack-overflowing), it also requires the compiler to optimize tail recursion so it won't leak memory and/or stack-overflow.

Despite all the object fiddling and garbage collection, this manages to run about 25-40% as fast as a simple array-based counting sort (see below).

#include <gc/gc_cpp.h>
#include <stdio.h>

template<class T>
struct Node : public gc
{
    T a, b, c, d;

    Node(T a, T b, T c, T d)
        : a(a), b(b), c(c), d(d)
        {}

    Node(T s)
        : a(s), b(s), c(s), d(s)
        {}

    T get(int n) {
        switch (n) {
            case 0:  return a;
            case 1:  return b;
            case 2:  return c;
            case 3:  return d;
            default: return NULL;
        }
    }
};

typedef Node<int> TrieC;
typedef Node<TrieC*> TrieB;
typedef Node<TrieB*> TrieA;
typedef Node<TrieA*> Trie;

static Trie *initialize();
static Trie *sortInput(Trie *root);
static Trie *sortUsingStack(Trie *orig, Trie *root, int c, int count);
template<class T> static Node<T> *merge(Node<T> *node, Node<T> *base);
static Node<int> *merge(Node<int> *node, Node<int> *base);
static void  print(Trie *trie);
static void  repeat(int c, int n);

static Trie *initialize()
{
    return new Trie(new TrieA(new TrieB(new TrieC(0))));
}

static Trie *sortInput(Trie *root)
{
    int c = getchar();
    if (c == EOF)
        return root;
    else
        return sortInput(sortUsingStack(root, root, c, 1000));
}

static Trie *sortUsingStack(Trie *orig, Trie *root, int chr, int count)
{
    if (chr == EOF)
        return merge(root, orig);

    int a = (chr >> 6) & 3;
    int b = (chr >> 4) & 3;
    int c = (chr >> 2) & 3;
    int d =  chr       & 3;

    TrieA *na = root->get(a);
    TrieB *nb = na->get(b);
    TrieC *nc = nb->get(c);
    int    nd = nc->get(d);

    int nd2 = nd + 1;

    TrieC nc2(
        d == 0 ? nd2 : nc->a,
        d == 1 ? nd2 : nc->b,
        d == 2 ? nd2 : nc->c,
        d == 3 ? nd2 : nc->d);

    TrieB nb2(
        c == 0 ? &nc2 : nb->a,
        c == 1 ? &nc2 : nb->b,
        c == 2 ? &nc2 : nb->c,
        c == 3 ? &nc2 : nb->d);

    TrieA na2(
        b == 0 ? &nb2 : na->a,
        b == 1 ? &nb2 : na->b,
        b == 2 ? &nb2 : na->c,
        b == 3 ? &nb2 : na->d);

    Trie root2(
        a == 0 ? &na2 : root->a,
        a == 1 ? &na2 : root->b,
        a == 2 ? &na2 : root->c,
        a == 3 ? &na2 : root->d);

    if (count > 0)
        return sortUsingStack(orig, &root2, getchar(), count - 1);
    else
        return merge(&root2, orig);
}

/* Copy tree, but use nodes from base if they're the same. */
template<class T> static Node<T> *merge(Node<T> *node, Node<T> *base)
{
    if (node == base)
        return node;
    else
        return new Node<T>(merge(node->a, base->a),
                           merge(node->b, base->b),
                           merge(node->c, base->c),
                           merge(node->d, base->d));
}

static Node<int> *merge(Node<int> *node, Node<int> *base)
{
    (void) base;
    return new Node<int>(node->a, node->b, node->c, node->d);
}

static void printC(TrieC *t, int start)
{
    repeat(start, t->a);
    repeat(start + 1, t->b);
    repeat(start + 2, t->c);
    repeat(start + 3, t->d);
}

static void printB(TrieB *t, int start)
{
    printC(t->a, start);
    printC(t->b, start + 4);
    printC(t->c, start + 8);
    printC(t->d, start + 12);
}

static void printA(TrieA *t, int start)
{
    printB(t->a, start);
    printB(t->b, start + 16);
    printB(t->c, start + 32);
    printB(t->d, start + 48);
}

static void print(Trie *t)
{
    printA(t->a, 0);
    printA(t->b, 64);
    printA(t->c, 128);
    printA(t->d, 192);
}

/* Print the character c, n times. */
static void repeat(int c, int n)
{
    if (n > 0) {
        putchar(c);
        repeat(c, n-1);
    }
}

int main(void)
{
    print(sortInput(initialize()));
    putchar('\n');
    return 0;
}

The array-based counting sort I used for comparison (getchar/putchar is the bottleneck):

#include <stdio.h>

int main(void)
{
    int tally[256] = {};
    int c, i, j;

    while ((c = getchar()) != EOF)
        tally[c]++;

    for (i = 0; i < 256; i++)
        for (j = 0; j < tally[i]; j++)
            putchar(i);
    putchar('\n');

    return 0;
}
\$\endgroup\$
3
\$\begingroup\$

Haskell

This implements a counting sort by building a 4-way trie. It's an adaptation of my C++ answer, and is roughly 25% faster than it.

import Data.Bits
import Data.List
import Data.Word

import qualified Data.ByteString as S
import qualified Data.ByteString.Lazy as L

data Node a = Node !a !a !a !a

sortByteString :: L.ByteString -> L.ByteString
sortByteString s = fromTrie $ L.foldl' f z s
    where
        f n x =
            let a = (x `shiftR` 6) .&. 3
                b = (x `shiftR` 4) .&. 3
                c = (x `shiftR` 2) .&. 3
                d =  x             .&. 3
             in (chg a . chg b . chg c . chg d) (+1) n
        z = let n a = Node a a a a
             in (n . n . n . n) 0

        chg :: Word8 -> (a -> a) -> Node a -> Node a
        chg 0 f (Node a b c d) = Node (f a) b c d
        chg 1 f (Node a b c d) = Node a (f b) c d
        chg 2 f (Node a b c d) = Node a b (f c) d
        chg 3 f (Node a b c d) = Node a b c (f d)

        fromTrie t =
            let gather (Node a b c d) = [a, b, c, d]
                counts = gather t >>= gather >>= gather >>= gather
             in L.concat $ zipWith (L.replicate) counts [0..]

main = L.interact ((`L.snoc` 10) . sortByteString)
\$\endgroup\$
3
\$\begingroup\$

Scala

object Sort extends Application
{
    def merge(s1:String,s2:String):String=
    {
        if(s1.isEmpty) return s2
        if(s2.isEmpty) return s1
        if(s1.head<s2.head)
            return s1.head+merge(s1.tail,s2)
        else
            return s2.head+merge(s1,s2.tail)
    }
    def mergesort(s:String):String=
    {
        if(s.length<=1)
            return s
        else
            return merge(mergesort(s take(s.length/2)),mergesort(s drop(s.length/2)))
    }
    print(mergesort(Console.readLine))
}
\$\endgroup\$
2
\$\begingroup\$

SED

s/$/\n !"#$%\&'()*+,-.\/0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~/;:a;s/\(.\)\(.*\)\(.\)\(.*\n.*\3.*\1\)/\3\1\2\4/;ta;s/\n.*//

Doesn't modify anything but pattern space (script would be pointless otherwise)

Lookup table borrowed from http://sed.sf.net/grabbag/scripts/sodelnum.sed

\$\endgroup\$
  • \$\begingroup\$ +1 :) Impressive! Don't try this at home :) with a too big file (3600 bytes). \$\endgroup\$ – user unknown Apr 13 '11 at 3:45
2
\$\begingroup\$

Ruby (71 chars)

Shamelessly stole the idea from gnibbler, but improved it, a lot

def s x
return if x>255
print x.chr*(ARGV[0].count x.chr)
s x+1
end
s 0

Usage:

$ ruby codegolfsort.rb "supercalifragilisticexpalodoucious"
aaacccdeefgiiiiilllooopprrssstuuux
\$\endgroup\$
  • \$\begingroup\$ You also misspelled supercalifragilisticexpialidocious. I think if one more person does it, it counts as a meme. \$\endgroup\$ – Joey Adams Apr 15 '11 at 17:01
1
\$\begingroup\$

Python

S=lambda x:S([y for y in x if y<x[0]])+x[0]*x.count(x[0])+S([y for y in x if y>x[0]])if x else''
print S(raw_input())
\$\endgroup\$
  • \$\begingroup\$ I believe the for loop modifies the value of y, so I think it is not allowed... \$\endgroup\$ – Timwi Apr 12 '11 at 22:35
  • \$\begingroup\$ The same could be said for any of the recursive solutions. \$\endgroup\$ – Keith Randall Apr 12 '11 at 23:54
  • \$\begingroup\$ Would you be happier if I used filter(lambda y:y<x[0],x)? Or is that not allowed also? \$\endgroup\$ – Keith Randall Apr 12 '11 at 23:55
  • \$\begingroup\$ I can’t speak for the OP, but personally I would allow that: after all, my solution does that too :) \$\endgroup\$ – Timwi Apr 13 '11 at 17:26
1
\$\begingroup\$

Ruby

s=gets
puts 0.chr*(s.count 0.chr)+1.chr*(s.count 1.chr)+2.chr*(s.count 2.chr)+3.chr*(s.count 3.chr)+4.chr*(s.count 4.chr)+5.chr*(s.count 5.chr)+6.chr*(s.count 6.chr)+7.chr*(s.count 7.chr)+8.chr*(s.count 8.chr)+9.chr*(s.count 9.chr)+10.chr*(s.count 10.chr)+11.chr*(s.count 11.chr)+12.chr*(s.count 12.chr)+13.chr*(s.count 13.chr)+14.chr*(s.count 14.chr)+15.chr*(s.count 15.chr)+16.chr*(s.count 16.chr)+17.chr*(s.count 17.chr)+18.chr*(s.count 18.chr)+19.chr*(s.count 19.chr)+20.chr*(s.count 20.chr)+21.chr*(s.count 21.chr)+22.chr*(s.count 22.chr)+23.chr*(s.count 23.chr)+24.chr*(s.count 24.chr)+25.chr*(s.count 25.chr)+26.chr*(s.count 26.chr)+27.chr*(s.count 27.chr)+28.chr*(s.count 28.chr)+29.chr*(s.count 29.chr)+30.chr*(s.count 30.chr)+31.chr*(s.count 31.chr)+32.chr*(s.count 32.chr)+33.chr*(s.count 33.chr)+34.chr*(s.count 34.chr)+35.chr*(s.count 35.chr)+36.chr*(s.count 36.chr)+37.chr*(s.count 37.chr)+38.chr*(s.count 38.chr)+39.chr*(s.count 39.chr)+40.chr*(s.count 40.chr)+41.chr*(s.count 41.chr)+42.chr*(s.count 42.chr)+43.chr*(s.count 43.chr)+44.chr*(s.count 44.chr)+45.chr*(s.count 45.chr)+46.chr*(s.count 46.chr)+47.chr*(s.count 47.chr)+48.chr*(s.count 48.chr)+49.chr*(s.count 49.chr)+50.chr*(s.count 50.chr)+51.chr*(s.count 51.chr)+52.chr*(s.count 52.chr)+53.chr*(s.count 53.chr)+54.chr*(s.count 54.chr)+55.chr*(s.count 55.chr)+56.chr*(s.count 56.chr)+57.chr*(s.count 57.chr)+58.chr*(s.count 58.chr)+59.chr*(s.count 59.chr)+60.chr*(s.count 60.chr)+61.chr*(s.count 61.chr)+62.chr*(s.count 62.chr)+63.chr*(s.count 63.chr)+64.chr*(s.count 64.chr)+65.chr*(s.count 65.chr)+66.chr*(s.count 66.chr)+67.chr*(s.count 67.chr)+68.chr*(s.count 68.chr)+69.chr*(s.count 69.chr)+70.chr*(s.count 70.chr)+71.chr*(s.count 71.chr)+72.chr*(s.count 72.chr)+73.chr*(s.count 73.chr)+74.chr*(s.count 74.chr)+75.chr*(s.count 75.chr)+76.chr*(s.count 76.chr)+77.chr*(s.count 77.chr)+78.chr*(s.count 78.chr)+79.chr*(s.count 79.chr)+80.chr*(s.count 80.chr)+81.chr*(s.count 81.chr)+82.chr*(s.count 82.chr)+83.chr*(s.count 83.chr)+84.chr*(s.count 84.chr)+85.chr*(s.count 85.chr)+86.chr*(s.count 86.chr)+87.chr*(s.count 87.chr)+88.chr*(s.count 88.chr)+89.chr*(s.count 89.chr)+90.chr*(s.count 90.chr)+91.chr*(s.count 91.chr)+92.chr*(s.count 92.chr)+93.chr*(s.count 93.chr)+94.chr*(s.count 94.chr)+95.chr*(s.count 95.chr)+96.chr*(s.count 96.chr)+97.chr*(s.count 97.chr)+98.chr*(s.count 98.chr)+99.chr*(s.count 99.chr)+100.chr*(s.count 100.chr)+101.chr*(s.count 101.chr)+102.chr*(s.count 102.chr)+103.chr*(s.count 103.chr)+104.chr*(s.count 104.chr)+105.chr*(s.count 105.chr)+106.chr*(s.count 106.chr)+107.chr*(s.count 107.chr)+108.chr*(s.count 108.chr)+109.chr*(s.count 109.chr)+110.chr*(s.count 110.chr)+111.chr*(s.count 111.chr)+112.chr*(s.count 112.chr)+113.chr*(s.count 113.chr)+114.chr*(s.count 114.chr)+115.chr*(s.count 115.chr)+116.chr*(s.count 116.chr)+117.chr*(s.count 117.chr)+118.chr*(s.count 118.chr)+119.chr*(s.count 119.chr)+120.chr*(s.count 120.chr)+121.chr*(s.count 121.chr)+122.chr*(s.count 122.chr)+123.chr*(s.count 123.chr)+124.chr*(s.count 124.chr)+125.chr*(s.count 125.chr)+126.chr*(s.count 126.chr)+127.chr*(s.count 127.chr)+128.chr*(s.count 128.chr)+129.chr*(s.count 129.chr)+130.chr*(s.count 130.chr)+131.chr*(s.count 131.chr)+132.chr*(s.count 132.chr)+133.chr*(s.count 133.chr)+134.chr*(s.count 134.chr)+135.chr*(s.count 135.chr)+136.chr*(s.count 136.chr)+137.chr*(s.count 137.chr)+138.chr*(s.count 138.chr)+139.chr*(s.count 139.chr)+140.chr*(s.count 140.chr)+141.chr*(s.count 141.chr)+142.chr*(s.count 142.chr)+143.chr*(s.count 143.chr)+144.chr*(s.count 144.chr)+145.chr*(s.count 145.chr)+146.chr*(s.count 146.chr)+147.chr*(s.count 147.chr)+148.chr*(s.count 148.chr)+149.chr*(s.count 149.chr)+150.chr*(s.count 150.chr)+151.chr*(s.count 151.chr)+152.chr*(s.count 152.chr)+153.chr*(s.count 153.chr)+154.chr*(s.count 154.chr)+155.chr*(s.count 155.chr)+156.chr*(s.count 156.chr)+157.chr*(s.count 157.chr)+158.chr*(s.count 158.chr)+159.chr*(s.count 159.chr)+160.chr*(s.count 160.chr)+161.chr*(s.count 161.chr)+162.chr*(s.count 162.chr)+163.chr*(s.count 163.chr)+164.chr*(s.count 164.chr)+165.chr*(s.count 165.chr)+166.chr*(s.count 166.chr)+167.chr*(s.count 167.chr)+168.chr*(s.count 168.chr)+169.chr*(s.count 169.chr)+170.chr*(s.count 170.chr)+171.chr*(s.count 171.chr)+172.chr*(s.count 172.chr)+173.chr*(s.count 173.chr)+174.chr*(s.count 174.chr)+175.chr*(s.count 175.chr)+176.chr*(s.count 176.chr)+177.chr*(s.count 177.chr)+178.chr*(s.count 178.chr)+179.chr*(s.count 179.chr)+180.chr*(s.count 180.chr)+181.chr*(s.count 181.chr)+182.chr*(s.count 182.chr)+183.chr*(s.count 183.chr)+184.chr*(s.count 184.chr)+185.chr*(s.count 185.chr)+186.chr*(s.count 186.chr)+187.chr*(s.count 187.chr)+188.chr*(s.count 188.chr)+189.chr*(s.count 189.chr)+190.chr*(s.count 190.chr)+191.chr*(s.count 191.chr)+192.chr*(s.count 192.chr)+193.chr*(s.count 193.chr)+194.chr*(s.count 194.chr)+195.chr*(s.count 195.chr)+196.chr*(s.count 196.chr)+197.chr*(s.count 197.chr)+198.chr*(s.count 198.chr)+199.chr*(s.count 199.chr)+200.chr*(s.count 200.chr)+201.chr*(s.count 201.chr)+202.chr*(s.count 202.chr)+203.chr*(s.count 203.chr)+204.chr*(s.count 204.chr)+205.chr*(s.count 205.chr)+206.chr*(s.count 206.chr)+207.chr*(s.count 207.chr)+208.chr*(s.count 208.chr)+209.chr*(s.count 209.chr)+210.chr*(s.count 210.chr)+211.chr*(s.count 211.chr)+212.chr*(s.count 212.chr)+213.chr*(s.count 213.chr)+214.chr*(s.count 214.chr)+215.chr*(s.count 215.chr)+216.chr*(s.count 216.chr)+217.chr*(s.count 217.chr)+218.chr*(s.count 218.chr)+219.chr*(s.count 219.chr)+220.chr*(s.count 220.chr)+221.chr*(s.count 221.chr)+222.chr*(s.count 222.chr)+223.chr*(s.count 223.chr)+224.chr*(s.count 224.chr)+225.chr*(s.count 225.chr)+226.chr*(s.count 226.chr)+227.chr*(s.count 227.chr)+228.chr*(s.count 228.chr)+229.chr*(s.count 229.chr)+230.chr*(s.count 230.chr)+231.chr*(s.count 231.chr)+232.chr*(s.count 232.chr)+233.chr*(s.count 233.chr)+234.chr*(s.count 234.chr)+235.chr*(s.count 235.chr)+236.chr*(s.count 236.chr)+237.chr*(s.count 237.chr)+238.chr*(s.count 238.chr)+239.chr*(s.count 239.chr)+240.chr*(s.count 240.chr)+241.chr*(s.count 241.chr)+242.chr*(s.count 242.chr)+243.chr*(s.count 243.chr)+244.chr*(s.count 244.chr)+245.chr*(s.count 245.chr)+246.chr*(s.count 246.chr)+247.chr*(s.count 247.chr)+248.chr*(s.count 248.chr)+249.chr*(s.count 249.chr)+250.chr*(s.count 250.chr)+251.chr*(s.count 251.chr)+252.chr*(s.count 252.chr)+253.chr*(s.count 253.chr)+254.chr*(s.count 254.chr)+255.chr*(s.count 255.chr)
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.