12
\$\begingroup\$

The goal of this Code Golf is to create a program that sorts a list of strings (in ascending order), without using any built-in sort method (such as Array.Sort() in .NET, sort() in PHP, ...). Note that this restriction excludes using a built-in method that sorts an array descending, and then reversing the array.

Some details:

  • Your program should prompt for input, and this input is a list of strings containing only ASCII lower-case alphabetic characters a-z, comma-separated without spaces. For example:

    code,sorting,hello,golf
    
  • The output should be the given list of strings, but sorted in ascending order, still comma-separated without spaces. For example:

    code,golf,hello,sorting
    
\$\endgroup\$

23 Answers 23

3
\$\begingroup\$

GolfScript, 26 25 bytes

","/.,{{.2$<{\}*}*]}*","*

Straightfoward implementation of Bubble Sort.

Try it online in Web GolfScript.

How it works

","/     # Split the input string at commas.
.,       # Get the number of chunks.
{        # Do that many times:
  {      #   Reduce; for each element but the first:
    .2$< #     Push 1 if the last two strings are in descending order, 0 if not.
    {\}* #     Swap these strings that many times.
  }*]    #   Collect the strings dumped by reduce in an array.
}*       #
","*     # Join, separating by commas.
\$\endgroup\$
  • \$\begingroup\$ Nice! Accepting this one as answer because it's shorter than the currently accepted one. \$\endgroup\$ – ProgramFOX Jun 6 '15 at 9:02
10
\$\begingroup\$

Ruby 76 54 51 chars

x=gets.scan /\w+/;$><<x.dup.map{x.delete(x.min)}*?,
\$\endgroup\$
  • 1
    \$\begingroup\$ Very nice, bogosort :D \$\endgroup\$ – Doorknob Oct 14 '13 at 19:36
  • 1
    \$\begingroup\$ Wow, now it's even more interesting! I had to look at this for a while before I realized what was happening. I suppose now it's a slight variation of selection sort :P \$\endgroup\$ – Doorknob Oct 15 '13 at 12:39
  • 1
    \$\begingroup\$ Since the items are guaranteed to be alpha characters: x=gets.scan /\w+/ \$\endgroup\$ – Steven Rumbalski Oct 15 '13 at 15:25
7
\$\begingroup\$

k (16 chars)

Probably doesn't really live up to the spirit of the problem. In k, there is no built in sort operator. <x returns a list of indices of items in x in sorted order.

{x@<x}[","\:0:0]
\$\endgroup\$
  • \$\begingroup\$ Well, this is a kind of built-in sorting, so unfortunately, I can't mark this as answer. I like the idea, however, so +1! \$\endgroup\$ – ProgramFOX Oct 19 '13 at 16:56
4
\$\begingroup\$

SED, 135

s/.*/,&,!,abcdefghijklmnopqrstuvwxyz/;:;s/\(,\([^,]*\)\(.\)[^,]*\)\(.*\)\(,\2\(.\)[^,]*\)\(.*!.*\6.*\3\)/\5\1\4\7/;t;s/^,\(.*\),!.*/\1/

Based on my previous sorting entry

\$\endgroup\$
3
\$\begingroup\$

Ruby, 99 chars (Gnome sort)

a=gets.scan /\w+/
p=1
while a[p]
a[p]>a[p-1]?p+=2:(a[p],a[p-1]=a[p-1],a[p])
p-=1if p>1
end
$><<a*?,

This just barely beats my bubble sort implementation:

Ruby, 110 104 101 chars (Bubble sort)

s=gets.scan /\w+/
(z=s.size).times{(0..(z-2)).map{|i|s[i],s[i+1]=s[i+1],s[i]if s[i]>s[i+1]}}
$><<s*?,

This does list.length iterations, because worst-case scenario takes list.length - 1 iterations and one more really doesn't matter, and saves 2 chars.

Just for fun, a Quicksort version:

Ruby, 113 chars (Quicksort)

q=->a{if a[1]
p=a.shift
l=[]
g=[]
a.map{|x|(x>p ?g:l).push x}
q[l]+[p]+q[g]
else
a
end}
$><<q[gets.scan /\w+/]*?,
\$\endgroup\$
  • \$\begingroup\$ I found that this implementation of gnome sort loops infinitely when the input items are not all unique, e.g. a b b. \$\endgroup\$ – Scott Leadley Aug 25 '14 at 2:45
3
\$\begingroup\$

Haskell, 141

import Data.List
m=minimum
s[]=[]
s l=m l:s(l\\[m l])
t[]=[]
t s=let(a,b)=span(/=',')s in a:t(drop 1 b)
main=interact$intercalate",".s.t.init

At least it’s… sort of efficient.

\$\endgroup\$
  • \$\begingroup\$ You can save 11 characters by using selection sort: m=minimum s[]=[] s l=m l:(s$l\\[m l]) (replace your lines 2–4 with these lines). \$\endgroup\$ – user3389669 Jun 6 '15 at 18:59
  • \$\begingroup\$ The init doesn't seem to be necessary as there is neither a trailing ,, nor a trailing newline. t s=let(a,b)=span(/=',')s in a:t(drop 1 b) can be shortened by using a pattern guard, using (>',') and dropping the space between 1 b: t s|(a,b)<-span(>',')s=a:t(drop 1b). \$\endgroup\$ – Laikoni May 4 '18 at 22:25
  • \$\begingroup\$ Using insertion with the insert function x#(y:r)|y<x=y:x#r;x#r=x:r is shorter. It can be used directly in t and as it does not use (\\) and intercalate"," can be replaced by tail.((',':)=<<), the import can be dropped. All together 101 bytes: Try it online! \$\endgroup\$ – Laikoni May 4 '18 at 22:46
2
\$\begingroup\$

vba, 165

Sub q()
c=","
s=InputBox("?")
Z=Split(s, c)
t=UBound(Z)
For i=1 To t-1
For j=i To t
If Z(i)>Z(j) Then a=Z(i):Z(i)=Z(j):Z(j)=a
Next
Next
Debug.Print Join(Z,c)
End Sub
\$\endgroup\$
  • \$\begingroup\$ I count 165 characters... \$\endgroup\$ – Doorknob Oct 14 '13 at 19:35
  • \$\begingroup\$ @Doorknob, fixed count... The greasemonkey script evidently gave me the wrong count as I was typing in the code. \$\endgroup\$ – SeanC Oct 14 '13 at 19:41
  • 1
    \$\begingroup\$ You can get rid of a space in that Split. \$\endgroup\$ – Ry- Oct 17 '13 at 14:56
  • \$\begingroup\$ Using c="," and calling c twice actually adds to the byte count in this case, contributing 7 bytes to the byte count, where as just using "," twice would contribute 6 bytes. You can lower your byte code by taking input directly from the sub call (sub q(s)) and assuming s is of type variant\string. You can lose one more byte by changing For i=1 to to for i=1To. you can lose 5 bytes by changing Debug.Print Join... to Debug.?Join... \$\endgroup\$ – Taylor Scott Mar 25 '17 at 20:42
2
\$\begingroup\$

Scala, 122 bytes

As a one-liner (88 bytes):

.permutations.filter(_.sliding(2).map(w=>w(0)<w.last).fold(true)((a,b)=>a&&b)).toSeq(0)

(it will sort a list by just doing list.permutations.fil... )

As a program (122 bytes):

println(readLine.split(",").toSeq.permutations.filter(_.sliding(2).map(w=>w(0)<w.last).fold(true)((a,b)=>a&&b)).toSeq(0))

A longer version if you want it to read from stdin.

This iterate over all the permutations of the given list until it stumble on a sorted one. It's not fast as it takes about 12 seconds to sort a 10 elements list and well over a minute for a 11 elements one.

[Edit] items need to be unique or < can be replaced by <=. Also, sorry for necro.

\$\endgroup\$
1
\$\begingroup\$

javascript 128

a=prompt().split(',');b=[];for(i in a){b.push(a[i]);k=0;for(j in b){j=k;b[j]>a[i]?[c=b[j],b.splice(j,1),b.push(c)]:k++}}alert(b)

DEMO fiddle.

i am looking for a way to eliminate b.

\$\endgroup\$
  • \$\begingroup\$ Remove the [] around the part after the ? to save 2 chars \$\endgroup\$ – Doorknob Oct 15 '13 at 20:24
  • \$\begingroup\$ @Doorknob i have tried it before i get SyntaxError: missing : in conditional expression because ?:; (the shorthand if/else) is only supposed to take two pecies of code to execute (i.e. true?b++:b--;) using [,] is a hack, im still not sure why it works, i think its understood as a empty array declaration, like placing a random string or number as a stand-alone command. but you can still feel free to upvote. \$\endgroup\$ – Math chiller Oct 15 '13 at 22:53
  • \$\begingroup\$ Hmm, I suppose I was mistaken. The comma operator can execute multiple pieces of code at once. Using parenthesis works, so I suppose the ?: operator's precedence is lower than , \$\endgroup\$ – Doorknob Oct 16 '13 at 1:45
  • \$\begingroup\$ No, did you try? Parenthesis still work... \$\endgroup\$ – Doorknob Oct 16 '13 at 12:14
  • \$\begingroup\$ @Doorknob your right, however i tried {,} and it didnt work - i get SyntaxError: missing : after property id. as for precedence parentheses is always first. i still would like a upvote.... \$\endgroup\$ – Math chiller Oct 16 '13 at 12:27
1
\$\begingroup\$

PHP 83 bytes

<?for($x=fgetcsv(STDIN);$x;)${$x[0]>min($x)?x:a}[]=array_shift($x)?><?=join(~Ó,$a);

An O(n3) implementation of a selection sort. The Ó is character 211; a bit-inverted comma.

Sample usage:

$ more in.dat
code,sorting,hello,golf

$ php list-sort.php < in.dat
code,golf,hello,sorting
\$\endgroup\$
1
\$\begingroup\$

Python 3 (80 chars)

l=input().split(',')
m=[]
while l:m+=[l.pop(l.index(min(l)))]
print(','.join(m))

Here is a variation of the while-statement that is of equal length:

while l:x=min(l);m+=[x];l.remove(x)
\$\endgroup\$
1
\$\begingroup\$

Mathematica 66 56

Row[#[[Ordering@#]]&[InputString[]~StringSplit~","],","]

Some other solutions without the build-in symbol Ordering:

Bogosort: 84 74

NestWhile[RandomSample,InputString[]~StringSplit~",",!OrderedQ@#&]~Row~","

Bubble Sort: 93 83

Row[InputString[]~StringSplit~","//.{x___,i_,j_,y___}/;j~Order~i==1:>{x,j,i,y},","]

Another solution as inefficient as bogosort: 82 72

#~Row~","&/@Permutations[InputString[]~StringSplit~","]~Select~OrderedQ;
\$\endgroup\$
1
\$\begingroup\$

Python 3.5+, 73 bytes

This takes inspiration from Steven Rumbalski's answer but uses list comprehension instead of a while loop; the number of iterations comes from the copied list l which is the reason this requires additional unpacking generalizations and Python 3.5

l=input().split(',');print(*[l.pop(l.index(min(l)))for _ in[*l]],sep=',')
\$\endgroup\$
0
\$\begingroup\$

R

Bubble Sort: 122 118 characters

a=scan(,"",sep=",");h=T;while(h){h=F;for(i in 1:(length(a)-1)){j=i+1;if(a[i]>a[j]){a[j:i]=a[i:j];h=T}}};cat(a,sep=",")

Bogosort: 100 characters

a=scan(,"",sep=",");while(any(apply(embed(a,2),1,function(x)x[1]<x[2]))){a=sample(a)};cat(a,sep=",")
\$\endgroup\$
0
\$\begingroup\$

Perl, 159

perl -F"," -lape "$m=$m<length()?length():$m for@F;$_{10**(2*$m)*sprintf'0.'.'%02d'x$m,map-96+ord,split//}=$_ for@F;$_=join',',map$_{$_+0},grep exists$_{$_+0},'0'.1..'0'.10**100"

This never stood a chance to win, but decided to share it because I liked the logic even if it's a mess :) The idea behind it, is to convert each word into an integer (done using the ord function), we save the number as a key in a hash and the string as a value, and then we iterate increasingly through all integers (1..10**100 in this case) and that way we get our strings sorted.

WARNING: Don't run this code on your computer, since it loops through trillions+ of integers. If you want to test it, you can lower the upper range limit and input non-lengthy strings. If for any reason this is against the rules, please let me know and I'll delete the entry!

\$\endgroup\$
0
\$\begingroup\$

JS: 107 chars - Bubble Sort

a=prompt().split(/,/);for(i=a.length;i--;)for(j=0;j<i;)a[j]>a[j+1]?[b=a[j],a[j]=a[++j],a[j]=b]:j++;alert(a)

I looked at @tryingToGetProgrammingStraight's answer and tried to improve it, but ended up implementing it slightly differently.

\$\endgroup\$
0
\$\begingroup\$

Java, 134 bytes

A method that implements Gnome Sort.

void s(String[]a){int m=a.length-1,i=0;while(i<m){while(i>=0&&a[i].compareTo(a[i+1])>0){String t=a[i];a[i]=a[i+1];a[i+1]=t;i--;}i++;}}
\$\endgroup\$
0
\$\begingroup\$

Swift, 101 bytes

func s(a:[String])->[String]{return a.count<2 ? a:(s(a.filter{$0<a[0]})+[a[0]]+s(a.filter{$0>a[0]}))}

Ungolfed:

//quicksort
func sort(a:[String]) -> [String]
{
    //return the array if its length is less than or equal to 1
    if a.count <= 1
    {
        return a
    }
    //choose the first element as pivot
    let pivot = a[0]
    //retrieve all elements less than the pivot
    let left = a.filter{ $0 < pivot }
    //retrieve all elements greater than the pivot
    let right = a.filter{ $0 > pivot }
    //sort the left partition, append a new array containing the pivot,
    //append the sorted right partition
    return sort(left) + Array<String>(arrayLiteral: pivot) + sort(right)
}
\$\endgroup\$
  • \$\begingroup\$ This does not take and return the strings in the given comma-separated format. \$\endgroup\$ – Laikoni May 4 '18 at 22:49
0
\$\begingroup\$

𝔼𝕊𝕄𝕚𝕟, 24 chars / 30 bytes (noncompetitive)

ï⇔Ĕ⍪;↻ïꝈ)ΞÿѨŗ ï,⇀$≔МƵï;Ξ

Try it here (Firefox only).

Using selection sort!

Explanation

ï⇔Ĕ⍪;↻ïꝈ)ΞÿѨŗ ï,⇀$≔МƵï;Ξ // implicit: ï=input, Ξ=[]
ï⇔Ĕ⍪;                    // split ï along commas and set it to ï
     ↻ïꝈ)                // while ï's length > 0
         Ξÿ              // push to Ξ:
           Ѩŗ ï,⇀$≔МƵï;  // removed minimum item(s) from ï using builtin
                       Ξ // get sorted array

Basically recursively removes and pushes the minimum from the input to another array.

\$\endgroup\$
0
\$\begingroup\$

Ceylon (Bogosort), 119

String s(String i)=>",".join([*i.split(','.equals)].permutations.select((p)=>!any{for([x,y]in p.paired)y<x})[0]else[]);

Try it online!

I found the permutations method and thus ended up with Bogosort (a non-random variant).

Formatted and commented:

// a function `s` mapping a String `i` to a String
String s(String i) =>
    // the end result is created by joining the iterable in (...).
    ",".join(
        // take the input, split it on commas, make the result a sequence.
        [*
            i.split(','.equals)   // → {String+}
           ]                      // → [String+]
        // get the iterable of all permutations of this sequence.
        // Yes, this is an iterable of O(n!) sequences (though likely
        // lazily computed, we don't need all in memory at once).
        .permutations              // → {[String+]*}
        // filter this iterable for ordered sequences.
        // Using select instead of filter makes this
        // eager instead of lazy, so we are actually iterating
        // through all n! sequences, and storing the ordered
        // ones. (All of those are equal.)
        .select(
            // this is our function to check whether this sequence
            // is ordered in ascending order.
            (p)=>
               // return if none of the following iterable of booleans is true.
                !any {
                   // This is a for-comprehension. Inside an named argument list
                   // (what we have here, although there is no name) for a
                   // function which wants an iterable, this becomes an iterable,
                   // lazily built from the existing iterable p.paired,
                   // which is just an iterable with all pairs of subsequent
                   // elements.
                      for([x,y] in p.paired)
                        // for each such pair, we evaluate this expression, which
                        // is true when the sequence is not ordered correctly.
                           y < x         // → Boolean
                        // → {Boolean*}
                    }  //   → Boolean
                 //  → Boolean([String+])
               ) // → [[String+]*]
         // we now have a sequence of (correctly sorted) sequences.
         // just take the first one.
         // If we had used `.filter` before, this would have to be `.first`.
               [0]    // → [String+]|Null
         // in case this is null, which can only happen if the original array was
         // empty, so there were no permutations, just use the empty sequence
         //  again. (Actually, split never returns an empty array, so this can't
         //  happen, but the type checker can't know that.)
               else []    // → [String*]
    // so that is what we pass to the join method.
        )   // → String
    ;

Without the formatting and parsing it becomes just 90 bytes:

String[]s(String[]i)=>i.permutations.select((p)=>!any{for([x,y]in p.paired)y<x})[0]else[];

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Perl 5, 77 bytes

map{$F[$_]gt$F[$_+1]&&(@F[$_,$_+1]=@F[$_+1,$_])for 0..@F-2}@F;$_=join',',"@F"

Try it online!

Simple bubble sort.

\$\endgroup\$
0
\$\begingroup\$

ruby -plaF, , 70 bytes

o=[]
$F.map{|s|i=o;s.bytes{|b|i=i[b]=[*i[b]]};i[0]=s<<?,}
$_=o*''
chop

O(n), if you pretend that resizing and compacting an array is free (it is very not free).

We create a deeply and unevenly nested array o by putting a string with bytes b1,b2...bn into the array at position o[b1][b2]...[bn]. The result looks like [,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,["a,",,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, [,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, ["abc,"], ["abd,"], ["abe,"]], ["ac,"], ["ad,"]],, ["c,"]]

Then we flatten and output it.

\$\endgroup\$
0
\$\begingroup\$

Reusing my own answer on Sort an Integer List

Tcl, 211 bytes

set L [split [gets stdin] ,]
set i 0
time {incr j;set x 0;while \$x<$i {if \"[lindex $L $i]"<"[lindex $L $x]" {set L [lreplace [linsert $L $x [lindex $L $i]] $j $j]};incr x};incr i} [llength $L]
puts [join $L ,]

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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