Mengurutkan daftar string tanpa menggunakan metode pengurutan bawaan apa pun

12

Tujuan Golf Kode ini adalah untuk membuat program yang mengurutkan daftar string (dalam urutan menaik), tanpa menggunakan metode pengurutan bawaan apa pun (seperti Array.Sort()dalam .NET, sort()dalam PHP, ...). Perhatikan bahwa pembatasan ini mengecualikan menggunakan metode bawaan yang mengurutkan larik turun, dan kemudian membalikkan larik.

Beberapa detail:

  • Program Anda harus meminta input, dan input ini adalah daftar string yang hanya berisi karakter alfabet huruf kecil ASCII a-z, dipisahkan dengan koma tanpa spasi. Sebagai contoh:

    code,sorting,hello,golf
    
  • Outputnya harus berupa daftar string yang diberikan, tetapi diurutkan dalam urutan menaik, masih dipisahkan koma tanpa spasi. Sebagai contoh:

    code,golf,hello,sorting
    
ProgramFOX
sumber

Jawaban:

3

GolfScript, 26 25 byte

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

Implementasi Straightfoward dari Bubble Sort.

Cobalah online di Web GolfScript .

Bagaimana itu bekerja

","/     # 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.
Dennis
sumber
Bagus! Menerima yang ini sebagai jawaban karena lebih pendek daripada yang diterima saat ini.
ProgramFOX
10

Ruby 76 54 51 chars

x=gets.scan /\w+/;$><<x.dup.map{x.delete(x.min)}*?,
Tyler Holien
sumber
1
Bagus sekali, bogosort : D
Doorknob
1
Wow, sekarang bahkan lebih menarik! Saya harus melihat ini sebentar sebelum saya menyadari apa yang terjadi. Saya kira sekarang ini sedikit variasi dari jenis seleksi: P
Doorknob
1
Karena item dijamin menjadi karakter alfa:x=gets.scan /\w+/
Steven Rumbalski
7

k (16 karakter)

Mungkin tidak benar-benar memenuhi semangat masalah. Dalam k, tidak ada operator sortir bawaan. <xmengembalikan daftar indeks item dalam x dalam urutan diurutkan.

{x@<x}[","\:0:0]
skeevey
sumber
Yah, ini semacam penyortiran bawaan, jadi sayangnya, saya tidak dapat menandai ini sebagai jawaban. Namun saya menyukai gagasan itu, jadi +1!
ProgramFOX
4

SED, 135

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

Berdasarkan entri penyortiran saya sebelumnya

Hasturkun
sumber
3

Ruby, 99 karakter ( 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*?,

Ini hampir tidak bisa mengalahkan implementasi semacam gelembung saya:

Ruby, 110 104 101 karakter ( 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*?,

Ini tidak list.lengthiterasi, karena skenario terburuk mengambil list.length - 1iterasi dan satu lagi benar-benar tidak masalah, dan menghemat 2 karakter.

Hanya untuk bersenang-senang, versi Quicksort:

Ruby, 113 karakter ( 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+/]*?,
Gagang pintu
sumber
Saya menemukan bahwa implementasi loop semacam gnome ini secara tak terbatas ketika item input tidak semuanya unik, misalnya ab b.
Scott Leadley
3

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

Setidaknya itu ... agak efisien.

Ry-
sumber
Anda dapat menyimpan 11 karakter dengan menggunakan semacam pilihan: m=minimum s[]=[] s l=m l:(s$l\\[m l])(ganti baris Anda 2–4 ​​dengan baris ini).
user3389669
The inittampaknya tidak perlu karena ada tidak trailing ,, atau baris baru trailing. t s=let(a,b)=span(/=',')s in a:t(drop 1 b)dapat dipersingkat dengan menggunakan penjaga pola, menggunakan (>',')dan menjatuhkan ruang antara 1 b: t s|(a,b)<-span(>',')s=a:t(drop 1b).
Laikoni
Menggunakan penyisipan dengan fungsi menyisipkan x#(y:r)|y<x=y:x#r;x#r=x:rlebih pendek. Ini dapat digunakan secara langsung tdan karena tidak digunakan (\\)dan intercalate","dapat diganti dengan tail.((',':)=<<), impor dapat dibatalkan. Secara keseluruhan 101 byte: Cobalah secara online!
Laikoni
2

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
SeanC
sumber
Saya menghitung 165 karakter ...
Gagang Pintu
@ Doorknob, hitungan tetap ... Script greasemonkey ternyata memberi saya hitungan yang salah saat saya mengetikkan kode.
SeanC
1
Anda dapat menyingkirkan ruang di dalamnya Split.
Ry-
Menggunakan c=","dan memanggil cdua kali sebenarnya menambah jumlah byte dalam kasus ini, berkontribusi 7 byte ke jumlah byte, di mana hanya menggunakan "," dua kali akan berkontribusi 6 byte. Anda dapat menurunkan kode byte Anda dengan mengambil input langsung dari sub panggilan ( sub q(s)) dan dengan asumsi s adalah tipe varian \ string. Anda dapat kehilangan satu byte lagi dengan mengubah For i=1 toke for i=1To. Anda dapat kehilangan 5 byte dengan mengubah Debug.Print Join...keDebug.?Join...
Taylor Scott
2

Scala, 122 byte

Sebagai satu-liner (88 byte):

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

(Ini akan mengurutkan daftar hanya dengan melakukan list.permutations.fil...)

Sebagai sebuah program (122 byte):

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

Versi yang lebih panjang jika Anda ingin membacanya dari stdin.

Ini mengulangi semua permutasi dari daftar yang diberikan sampai tersandung pada yang diurutkan. Ini tidak cepat karena dibutuhkan sekitar 12 detik untuk mengurutkan daftar 10 elemen dan lebih dari satu menit untuk 11 elemen.

[Sunting] item harus unik atau <dapat diganti dengan <=. Juga, maaf untuk necro.

gan_
sumber
1

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)

Biola DEMO .

Saya mencari cara untuk menghilangkan b.

Chiller matematika
sumber
Lepaskan bagian di []sekitar setelah ?menyimpan 2 karakter
Doorknob
@ Doorknob saya sudah mencobanya sebelum saya dapatkan SyntaxError: missing : in conditional expressionkarena ?:;(singkatan if/else) hanya seharusnya mengambil dua pecies dari kode untuk dieksekusi (yaitu true?b++:b--;) menggunakan [, ]adalah hack, im masih tidak yakin mengapa ia bekerja, saya pikir itu dipahami sebagai array kosong deklarasi, seperti menempatkan string atau angka acak sebagai perintah yang berdiri sendiri. tetapi Anda masih bisa merasa bebas untuk memperbaiki.
Math chiller
Hmm, saya kira saya salah. Operator koma dapat menjalankan beberapa bagian kode sekaligus. Menggunakan karya kurung, jadi saya kira ?:prioritas operator lebih rendah daripada,
Gagang Pintu
Tidak, sudahkah Anda mencoba? Parenthesis masih berfungsi ...
Gagang Pintu
@ Doorknob kanan Anda , namun saya mencoba {, }dan itu tidak berhasil - saya mengerti SyntaxError: missing : after property id. Adapun kurung didahului selalu pertama. saya masih ingin upvote ....
Math chiller
1

PHP 83 byte

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

Sebuah O (n 3 ) pelaksanaan semacam seleksi. The Ókarakter 211; tanda koma sedikit terbalik.

Penggunaan sampel:

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

$ php list-sort.php < in.dat
code,golf,hello,sorting
primo
sumber
1

Python 3 (80 karakter)

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

Berikut ini adalah variasi dari pernyataan sementara yang memiliki panjang yang sama:

while l:x=min(l);m+=[x];l.remove(x)
Steven Rumbalski
sumber
1

Mathematica 66 56

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

Beberapa solusi lain tanpa simbol bawaan Ordering:

Bogosort: 84 74

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

Sortir Bubble: 93 83

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

Solusi lain yang tidak efisien seperti bogosort: 82 72

#~Row~","&/@Permutations[InputString[]~StringSplit~","]~Select~OrderedQ;
alephalpha
sumber
0

R

Sortir Bubble: 122 118 karakter

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 karakter

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

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"

Ini tidak pernah memiliki kesempatan untuk menang, tetapi memutuskan untuk membagikannya karena saya menyukai logikanya meskipun itu berantakan :) Gagasan di baliknya, adalah mengubah setiap kata menjadi integer (selesai menggunakan fungsi ord ), kami menyimpan nomornya sebagai kunci dalam hash dan string sebagai nilai, dan kemudian kita beralih semakin banyak melalui semua bilangan bulat (1..10 ** 100 dalam kasus ini) dan dengan cara itu kita mendapatkan string kita diurutkan.

PERINGATAN : Jangan jalankan kode ini di komputer Anda, karena itu loop melalui triliunan + bilangan bulat. Jika Anda ingin mengujinya, Anda dapat menurunkan batas rentang atas dan memasukkan string yang tidak panjang. Jika karena alasan apa pun ini melanggar aturan, harap beri tahu saya dan saya akan menghapus entri!

psxls
sumber
0

JS: 107 karakter - 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)

Saya melihat jawaban @ triedToGetProgrammingStraight dan mencoba memperbaikinya, tetapi akhirnya menerapkannya sedikit berbeda.

Dom Hastings
sumber
0

Java, 134 byte

Metode yang mengimplementasikan 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++;}}
SuperJedi224
sumber
0

Swift, 101 byte

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

Tidak Disatukan:

//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)
}
Palle
sumber
Ini tidak mengambil dan mengembalikan string dalam format yang dipisah koma.
Laikoni
0

𝔼𝕊𝕄𝕚𝕟, 24 karakter / 30 byte (tidak kompetitif)

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

Try it here (Firefox only).

Menggunakan semacam seleksi!

Penjelasan

ï⇔Ĕ⍪;↻ïꝈ)ΞÿѨŗ ï,⇀$≔МƵï;Ξ // 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

Pada dasarnya secara rekursif menghapus dan mendorong minimum dari input ke array lain.

Mama Fun Roll
sumber
0

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[]);

Cobalah online!

Saya menemukan permutationsmetode dan akhirnya Bogosort (varian non-acak).

Diformat dan dikomentari:

// 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
    ;

Tanpa pemformatan dan penguraian menjadi hanya 90 byte:

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

Cobalah online!

Paŭlo Ebermann
sumber
0

Perl 5 , 77 byte

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

Cobalah online!

Semacam gelembung sederhana.

Xcali
sumber
0

ruby -plaF, , 70 byte

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

O (n), jika Anda berpura-pura mengubah ukuran dan memadatkan array adalah gratis (sangat tidak gratis).

Kami membuat array bertingkat yang dalam dan tidak merata odengan meletakkan string dengan byte b 1 , b 2 ... b n ke dalam array pada posisi o [b 1 ] [b 2 ] ... [b n ]. Hasilnya terlihat seperti[,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,["a,",,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, [,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, ["abc,"], ["abd,"], ["abe,"]], ["ac,"], ["ad,"]],, ["c,"]]

Lalu kami meratakan dan mengeluarkannya.

histokrat
sumber
0

Menggunakan kembali jawaban saya sendiri di Sortir Daftar Integer

Tcl , 211 byte

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 ,]

Cobalah online!

sergiol
sumber