# Sorting a list of strings without using any built-in sort method

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


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

• Nice! Accepting this one as answer because it's shorter than the currently accepted one. – ProgramFOX Jun 6 '15 at 9:02

x=gets.scan /\w+/;$><<x.dup.map{x.delete(x.min)}*?,  • Very nice, bogosort :D – Doorknob Oct 14 '13 at 19:36 • 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 – Doorknob Oct 15 '13 at 12:39 • Since the items are guaranteed to be alpha characters: x=gets.scan /\w+/ – Steven Rumbalski Oct 15 '13 at 15:25 # 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]  • 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! – ProgramFOX Oct 19 '13 at 16:56 ## SED, 135 s/.*/,&,!,abcdefghijklmnopqrstuvwxyz/;:;s/$$,\([^,]*$$$$.$$[^,]*\)$$.*$$$$,\2\(.$$[^,]*\)$$.*!.*\6.*\3$$/\5\1\4\7/;t;s/^,$$.*$$,!.*/\1/  Based on my previous sorting entry ## 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, 110104 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+/]*?,

• I found that this implementation of gnome sort loops infinitely when the input items are not all unique, e.g. a b b. – Scott Leadley Aug 25 '14 at 2:45

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. • 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). – user3389669 Jun 6 '15 at 18:59
• 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). – Laikoni May 4 '18 at 22:25
• 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! – Laikoni May 4 '18 at 22:46

## 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

• I count 165 characters... – Doorknob Oct 14 '13 at 19:35
• @Doorknob, fixed count... The greasemonkey script evidently gave me the wrong count as I was typing in the code. – SeanC Oct 14 '13 at 19:41
• You can get rid of a space in that Split. – Ry- Oct 17 '13 at 14:56
• 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... – Taylor Scott Mar 25 '17 at 20:42

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

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

## 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)


i am looking for a way to eliminate b.

• Remove the [] around the part after the ? to save 2 chars – Doorknob Oct 15 '13 at 20:24
• @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. – Math chiller Oct 15 '13 at 22:53
• 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 , – Doorknob Oct 16 '13 at 1:45
• No, did you try? Parenthesis still work... – Doorknob Oct 16 '13 at 12:14
• @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.... – Math chiller Oct 16 '13 at 12:27

## 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  # 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)  # 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;  # 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=',')  # 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=",")  ## 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! ## 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. # 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++;}}  # 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) }  • This does not take and return the strings in the given comma-separated format. – Laikoni May 4 '18 at 22:49 # 𝔼𝕊𝕄𝕚𝕟, 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.

# 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!

$_=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. 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!