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

Question

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

Dennis · Accepted Answer · 2015-06-06 20:34:08Z

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 at 9:02

minitech · Answer 2 · 2015-06-06 20:39:33Z

up vote 1 down vote

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.

edited Jun 6 at 20:39

answered Oct 16 '13 at 19:05

minitech
4,17811127

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 at 18:59

@user3389669: Thank you! – minitech Jun 6 at 19:10

add a comment |

gan_ · Answer 3 · 2015-06-06 02:58:52Z

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.

SuperJedi224 · Answer 4 · 2015-06-04 21:24:16Z

up vote 0 down vote

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++;}}

answered Jun 4 at 21:24

SuperJedi224
2,036627

add a comment |

Cruncher · Answer 5 · 2014-07-29 13:54:24Z

up vote 3 down vote

MATLAB - 29 (Miracle sort)

while !issorted(A) do
end_while

Explanation:

Since computers are not perfect, the chance of a bit arbitrarily swapping for no reason is non-zero. Therefore by the infinite monkey theorem, if you keep checking if the array is sorted, it will be eventually.

I don't believe issorted is considered a built-in sort. But I guess that line is grey.

edited Jul 29 '14 at 13:54

answered Nov 8 '13 at 17:10

Cruncher
1,075518

3

And I thought bogosort was a bad algorithm. – Kevin Cox Nov 22 '13 at 4:03

This should be put into Wikipedia. – Tengyu Liu Jul 29 '14 at 14:04

add a comment |

alephalpha · Answer 6 · 2013-10-20 05:15:44Z

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;

Dom Hastings · Answer 7 · 2013-10-16 20:05:36Z

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.

psxls · Answer 8 · 2013-10-16 13:44:50Z

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!

Doorknob · Answer 9 · 2013-10-15 22:40:18Z

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+/]*?,

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

Tyler Holien · Answer 10 · 2013-10-15 15:33:52Z

up vote 7 down vote

Ruby 76 54 51 chars

x=gets.scan /\w+/;$><<x.dup.map{x.delete(x.min)}*?,

edited Oct 15 '13 at 15:33

answered Oct 14 '13 at 18:47

Tyler Holien
1713

1

Very nice, bogosort :D – Doorknob♦ Oct 14 '13 at 19:36

1

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

1

Since the items are guaranteed to be alpha characters: x=gets.scan /\w+/ – Steven Rumbalski Oct 15 '13 at 15:25

Awesome, thanks! – Tyler Holien Oct 15 '13 at 15:31

add a comment |

Steven Rumbalski · Answer 11 · 2013-10-15 15:14:42Z

up vote 1 down vote

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)

answered Oct 15 '13 at 15:14

Steven Rumbalski
1,11347

add a comment |

Hasturkun · Answer 12 · 2013-10-15 12:10:39Z

up vote 1 down vote

SED, 135

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

Based on my previous sorting entry

answered Oct 15 '13 at 12:10

Hasturkun
1,036515

add a comment |

plannapus · Answer 13 · 2013-10-15 12:00:35Z

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=",")

primo · Answer 14 · 2013-10-15 11:11:28Z

PHP 83 bytes

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

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

tryingToGetProgrammingStraight · Answer 15 · 2013-10-15 11:08:21Z

up vote 0 down vote

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.

edited Oct 15 '13 at 11:08

answered Oct 14 '13 at 21:37

tryingToGetProgrammingStraight
242110

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. – tryingToGetProgrammingStraight 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.... – tryingToGetProgrammingStraight Oct 16 '13 at 12:27

| show 1 more comment

SeanC · Answer 16 · 2013-10-14 19:40:32Z

up vote 0 down vote

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

edited Oct 14 '13 at 19:40

answered Oct 14 '13 at 18:54

SeanC
808314

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

1

You can get rid of a space in that Split. – minitech Oct 17 '13 at 14:56

add a comment |

slackwear · Answer 17 · 2013-10-14 18:01:51Z

up vote 5 down vote

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]

answered Oct 14 '13 at 18:01

slackwear
2,978921

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

add a comment |

asked	1 year ago
viewed	5098 times
active	3 months ago

current community

your communities

more stack exchange communities

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

17 Answers 17

GolfScript, 26 25 bytes

How it works

Haskell, 141

Scala, 122 bytes

As a one-liner (88 bytes):

As a program (122 bytes):

Java, 134 bytes

MATLAB - 29 (Miracle sort)

Mathematica 66 56

Bogosort: 84 74

Bubble Sort: 93 83

Another solution as inefficient as bogosort: 82 72

JS: 107 chars - Bubble Sort

Perl, 159

Ruby, 99 chars (Gnome sort)

Ruby, 110 104 101 chars (Bubble sort)

Ruby, 113 chars (Quicksort)

Ruby 76 54 51 chars

Python 3 (80 chars)

SED, 135

R

Bubble Sort: 122 118 characters

Bogosort: 100 characters

PHP 83 bytes

javascript 128

vba, 165

k (16 chars)

Your Answer

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

Visit Chat

Linked

Hot Network Questions

current community

your communities

more stack exchange communities

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

17 Answers 17

GolfScript, 26 25 bytes

How it works

Haskell, 141

Scala, 122 bytes

As a one-liner (88 bytes):

As a program (122 bytes):

Java, 134 bytes

MATLAB - 29 (Miracle sort)

Mathematica 66 56

Bogosort: 84 74

Bubble Sort: 93 83

Another solution as inefficient as bogosort: 82 72

JS: 107 chars - Bubble Sort

Perl, 159

Ruby, 99 chars (Gnome sort)

Ruby, 110 104 101 chars (Bubble sort)

Ruby, 113 chars (Quicksort)

Ruby 76 54 51 chars

Python 3 (80 chars)

SED, 135

R

Bubble Sort: 122 118 characters

Bogosort: 100 characters

PHP 83 bytes

javascript 128

vba, 165

k (16 chars)

Your Answer

Sign up or log in

Post as a guest

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

Visit Chat

Linked

Related

Hot Network Questions