Zusammenführen, sortieren

In dieser Challenge implementieren Sie die Merge-Subroutine von merge sort. Insbesondere müssen Sie eine Funktion oder ein Programm, ein Verb oder Ähnliches erstellen, das zwei Listen verwendet, die in aufsteigender Reihenfolge sortiert sind, und diese in einer Liste zusammenfasst, die in aufsteigender Reihenfolge sortiert ist. Bedarf:

- Ihr Algorithmus muss eine asymptotisch lineare Zeit in der Größe der Eingabe benötigen. Bitte geben Sie keine O (n ^ 2) -Lösungen mehr an.

• Sie dürfen keine integrierten Funktionen verwenden, mit denen eine Liste sortiert oder zusammengeführt werden kann. Ermessen des Autors.
• Der Code sollte in der Lage sein, wiederholte Elemente zu verarbeiten.
• Mach dir keine Sorgen über leere Listen.

Beispiele:

merge([1],[0,2,3,4])
[0,1,2,3,4]

merge([1,5,10,17,19],[2,5,9,11,13,20])
[1, 2, 5, 5, 9, 10, 11, 13, 17, 19, 20]

Das ist Code-Golf , also kann der kürzeste Code gewinnen!

Rebmu ( 35 32 Zeichen)

u[iG^aNXa[rvA]apGtkFaM?fA]apGscA

Prüfung

>> rebmu/args [u[iG^aNXa[rvA]apGtkFaM?fA]apGscA] [[1 5 10 17 19] [2 5 9 11 13 20]] 
== [1 2 5 5 9 10 11 13 17 19 20]

>> rebmu/args [u[iG^aNXa[rvA]apGtkFaM?fA]apGscA] [[2 5 9 11 13 20] [1 5 10 17 19]] 
== [1 2 5 5 9 10 11 13 17 19 20]

Über

Rebmu ist ein Dialekt von Rebol, der es erlaubt, in Situationen, die Kürze erfordern, regulären Code zu „mushen“. Unmushed funktioniert der Code wie folgt:

u [                     ; until
    i g^ a nx a [       ; if greater? args next args
       rv a             ; reverse args
    ]                   ; (we want the block containing the next value first)

    ap g tk f a         ; append output take first args
    m? f a              ; empty? first args
]                       ; (first block is now empty)

ap g sc a               ; append output second args
                        ; (add the remainder of the second)

Ich glaube, dass dies die O (n) -Anforderung erfüllt, da der till-Block höchstens so oft wie die Länge der Eingabe durchgeschleift wird (und reversenur die Reihenfolge des Containers der Eingabeblöcke ändert, nicht die Blöcke selbst). Verwenden takeist vielleicht eine Freiheit, aber immer noch ein kleiner Effizienzschaden.

Rebol ( 83 75 Zeichen)

Nur ein kleines bisschen anders: In Rebol sind Pfade ein kürzerer Ausdruck als firstoder second. aist der Eingabeblock, der die beiden Blöcke enthält:

until[if a/2/1 < a/1/1[reverse a]append o:[]take a/1 tail? a/1]append o a/2

OP's Lösungen:

Haskell 49 44 40

k@(p:r)%l@(q:s)|p>=q=q:k%s|0<1=l%k
a%_=a

Python 131 105 101 99 93

Mit Dank an @Evpok:

f=lambda u,v:v and(v[-1]<u[-1]and f(v,u)or[b.append(a)for a,b in[(v.pop(),f(u,v))]]and b)or u

Python (79)

from itertools import*
def m(*a):
 while any(a):yield min(compress(a,a)).pop(0)

Python (95, wenn wir keinen Generator zurückgeben dürfen)

from itertools import*
def m(*a):
 r=[]
 while any(a):r+=[min(compress(a,a)).pop(0)]
 return r

Itertools ist die Lösung für alle weltweiten Probleme.

Bonus: Die beiden arbeiten an einer beliebigen Anzahl von Listen und sorgen sich um leere Listen (wie in, nehmen sie gerne 2 leere Listen und geben eine leere Liste zurück oder nehmen 1 leere und 1 nicht leere Liste, und sie werden die nicht leere zurückgeben. Ein weiteres zusätzliches Merkmal der 2 nicht ergebenden: Sie werden auch ohne Argumente ausgeführt und geben nur eine leere Liste zurück.)

Ungolfed:

from itertools import *  # Import all items from itertools
def m(*a):               # Define the function m, that takes any number of arguments, 
                         #  and stores those arguments in list a
    r=[]                 # Create an empty list r                         
    while any(a):        # While any element in a returns True as value:
        b=compress(a,a)  # Remove any element from a that isn't True (empty lists)
                         #  The example in the official documentation is this one:
                         #  compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F
        c=min(b)         # Sort the lists by first value, and take the first one of these.
        d=c.pop(0)       # Take the first element from c
        r.append(d)      # Append this first element to r
    return r             # Gives back r

C - 75

Dies funktioniert auf NULLterminierten Arrays von int *, obwohl es für Zeiger auf andere Typen genauso gut funktionieren würde, wenn die entsprechende Vergleichsfunktion für **b < **a(z strcmp(*b, *a) < 0. B. ) eingesetzt würde.

void m(int**a,int**b,int**c){while(*a||*b)*c++=!*a||*b&&**b<**a?*b++:*a++;}

Ungolfed:

void merge(int **a, int **b, int **c)
{
    while(*a || *b)
        *c++ = !*a || *b && **b < **a
            ? *b++
            : *a++;
}

Golfscript, 29 27 30 29 26 Bytes

~{[email protected]=@<{}{\}if(@@.}do;~]p

oder

~{[email protected]=@>{\}*(@@.}do;~]p

Wie es funktioniert

Der Befehl

golfscript merge.gs <<< '[2 3] [1 4]'

wird wie folgt verarbeitet:

~            # Interpret the input string.
             #
             # STACK: [2 3] [1 4]
{            #
    .@=0.@=0 # Duplicate the two topmost arrays of the stack and extract their first 
             # elements. This reverses the original order of the first copy.
             #
             # STACK: [1 4] [2 3] 2 1
             #
    >        # Check if the respective first elements of the arrays are ordered.
             #
             # STACK: [1 4] [2 3] 1
             #
    {\}*     # If they are not, swap the arrays. This brings the array with the smallest
             # element to the top of the stack.
             #
             # STACK: [2 3] [1 4]
             #
    (@@      # Shift the first element of the array on top of the stack and rotate it
             # behind the arrays.
             #
             # STACK: 1 [2 3] [4]
             #
    .        # Duplicate the topmost array.
             #
             # STACK: 1 [2 3] [4] [4]
             #
}do          # Repeat this process if the array is non-empty.
             #
             # STACK: 1 [2 3] [4] -> 1 2 [4] [3] -> 1 2 3 [4] []
             #
;~           # Delete the empty array from the stack and dump the non-empty array.
             #
             # STACK: 1 2 3 4
             #
]p           # Combine all elements on the stack into a single array, the to a string and
             # print.

Die Ausgabe ist:

[1 2 3 4]

J - 42 33

Geänderte Version von hier + der Kommentar von @algorithmshark

k=:(m}.),~0{]
m=:k~`k@.(>&{.) ::,

kStellt den Kopf des rechten Arrays vor die zusammengeführten Endpunkte beider Arrays. k~ist das gleiche, aber mit umgedrehten Arrays. (>&{.)vergleicht die Köpfe. Der Code wird einen Fehler auslösen, wenn eines der Arrays leer ist. In diesem Fall geben wir nur ihre Verkettung zurück ,.

JavaScript (ES6), 69 bis 79 Byte

f=(a,b,c=[])=>(x=a[0]<b[0]?a:b).length?f(a,b,c.concat(x.shift())):c.concat(a,b)

Wie es funktioniert

f = (a, b, c = []) =>          // `f' is a function that takes arguments `a', `b' and `c' -
                               // `c' defaults to `[]' - which returns the following
                               // expression:
                               //
 (x = a[0] < b[0] ? a : b)     // Store the array among `a' and `b' with the smaller first 
                               // element in `x'.
                               //
 .length ?                     // If it's non-empty,
                               //
  f(a, b, c.concat(x.shift())) // append the first element of array `x' to array `c' and run
                               // `f' again;
                               //
  : c.concat(a,b)              // otherwise, append the arrays `a' and `b' to `c'.
                               //
)

Python (63) (69) (71)

def m(a,b):
 if a[0]>b[0]:a,b=b,a
 return[a.pop(0)]+(m(a,b)if a else b)

Ich habe dies geschrieben, bevor ich die Kommentare von OP zu den Laufzeiten anderer Antworten gesehen habe. Dies ist also eine andere Lösung, die O (n) im Algorithmus, aber keine Implementierung ist.

Haskell, 35 Bytes

a#b@(c:d)|a<[c]=b#a|0<1=c:a#d
a#_=a

Haskell, 30 Bytes (nicht konkurrierend)

Diese nicht konkurrierende Version garantiert nur dann eine lineare Laufzeit, wenn aund bmit disjunkten Elementen. Andernfalls wird es weiterhin ordnungsgemäß ausgeführt, es wird jedoch möglicherweise eine quadratische Zeit verwendet.

a#b|a<b=b#a|c:d<-b=c:a#d
a#_=a

PHP 91 98 91 Bytes

edit # 1: Leer $berfordert eine zusätzliche Bedingung in den geschweiften Klammern (+7).
edit # 2: Minor Golfings
edit # 3: Zweite Version hinzugefügt

ziemlich einfach. Der schönste Teil ist der Dreiklang in der array_shift
(was fehlschlägt, wenn Sie es ohne die Locken versuchen)

function m($a,$b){for($c=[];$a|$b;)$c[]=array_shift(${$a&(!$b|$a[0]<$b[0])?a:b});return$c;}

oder

function m($a,$b){for($c=[];$a|$b;)$c[]=array_shift(${$a?!$b|$a[0]<$b[0]?a:b:b});return$c;}

ungolfed

function m($a,$b)
{
    $c=[];
    while($a||$b)
    {
        $c[] = array_shift(${
            $a&&(!$b||$a[0]<$b[0])
                ?a
                :b
        });
#       echo '<br>', outA($a), ' / ', outA($b) , ' -> ', outA($c);
    }
    return $c;
}

Prüfung

$cases = array (
    [1],[0,2,3,4], [0,1,2,3,4],
    [1,5,10,17,19],[2,5,9,11,13,20], [1, 2, 5, 5, 9, 10, 11, 13, 17, 19, 20],
    [1,2,3],[], [1,2,3],
    [],[4,5,6], [4,5,6],
);
function outA($a) { return '['. implode(',',$a). ']'; }
echo '<table border=1><tr><th>A</th><th>B</th><th>expected</th><th>actual result</th></tr>';
while ($cases)
{
    $a = array_shift($cases);
    $b = array_shift($cases);
#   echo '<hr>', outA($a), ' / ', outA($b) , ' -> ', outA($c);
    $expect = array_shift($cases);
    $result=m($a,$b);
    echo '<tr><td>',outA($a),'</td><td>',outA($b),'</td><td>', outA($expect), '</td><td>', outA($result),'</td></tr>';
}
echo '</table>';

Los, 124 Zeichen

func m(a,b[]int)(r[]int){for len(a)>0{if len(b)==0||a[0]>b[0]{a,b=b,a}else{r=append(r,a[0]);a=a[1:]}};return append(r,b...)}

JavaScript - 133

function m(a,b){c=[];for(i=j=0;i<a.length&j<b.length;)c.push(a[i]<b[j]?a[i++]:b[j++]);return c.concat(a.slice(i)).concat(b.slice(j))}

Gleiche Vorgehensweise wie bei OPs.

Perl, 87 Zeichen / Perl 5,14, 78 + 1 = 79 Zeichen

Diese Implementierung überlastet die Referenzen der Eingabearrays. Davon abgesehen ist es ziemlich einfach: Während beide Arrays etwas haben, verschieben Sie die untere der beiden. Geben Sie dann das zusammengeführte Bit zurück, das mit den verbleibenden Bits verbunden ist (es bleibt nur eines von @ $ x oder @ $ y übrig). Straight-Up Perl5, 87 Zeichen:

sub M{($x,$y,@o)=@_;push@o,$$x[0]>$$y[0]?shift@$y:shift@$x while@$x&&@$y;@o,@$x,@$y}

Unter Verwendung von Perl 5.14.0 und seiner neuen Arrayref-Verschiebung: 78 Zeichen + 1 Zeichen Strafe = 79 Zeichen:

sub M{($x,$y,@o)=@_;push@o,shift($$x[0]>$$y[0]?$y:$x)while@$x&&@$y;@o,@$x,@$y}

Java: 144

Das ist ziemlich einfach. Eine Funktion, die zwei Arrays verwendet und eines zurückgibt, die zusammengeführte Version, golfen und ohne Compilation-Wrapper:

int[]m(int[]a,int[]b){int A=a.length,B=b.length,i,j;int[]c=new int[A+B];for(i=j=0;i+j<A+B;c[i+j]=j==B||i<A&&a[i]<b[j]?a[i++]:b[j++]);return c;}

Ungolfed (mit kompilierbarem und lauffähigem Wrapper):

class M{
    public static void main(String[]args){
        int[]a=new int[args[0].split(",").length];
        int i=0;
        for(String arg:args[0].split(","))
            a[i++]=Integer.valueOf(arg);
        int[]b=new int[args[1].split(",").length];
        int j=0;
        for(String arg:args[1].split(","))
            b[j++]=Integer.valueOf(arg);
        int[]c=(new M()).m(a,b);
        for(int d:c)
            System.out.printf(" %d",d);
        System.out.println();
    }
    int[]m(int[]a,int[]b){
        int A=a.length,B=b.length,i,j;
        int[]c=new int[A+B];
        for(i=j=0;i+j<A+B;c[i+j]=j==B||i<A&&a[i]<b[j]?a[i++]:b[j++]);
        return c;
    }
}

Beispielausführungen:

$ javac M.java
$ java M 10,11,12 0,1,2,20,30
 0 1 2 10 11 12 20 30
$ java M 10,11,12,25,26 0,1,2,20,30
 0 1 2 10 11 12 20 25 26 30

Alle Tipps zu verkürzen wäre dankbar.

Scala, 97 Bytes

Rekursive Lösung mit O (n). Um den Code zu verkürzen, wird manchmal eine Operation durchgeführt, indem die 2 austauschbaren Parameter umgeschaltet werden, dh f (a, b) ruft f (b, a) auf.

type L=List[Int];def f(a:L,b:L):L=if(a==Nil)b else if(a(0)<=b(0))a(0)::f(a.drop(1),b) else f(b,a)

Ungolfed:

type L=List[Int]

def f(a:L, b:L) : L =
  if (a == Nil)
    b 
  else 
    if (a(0) <= b(0))
      a(0) :: f(a.drop(1), b) 
    else
      f(b,a)

APL (32)

{⍺⍵∊⍨⊂⍬:⍺,⍵⋄g[⍋g←⊃¨⍺⍵],⊃∇/1↓¨⍺⍵}

Erläuterung:

{⍺⍵∊⍨⊂⍬                               if one or both of the arrays are empty
        :⍺,⍵                           then return the concatenation of the arrays
             ⋄g[⍋g←⊃¨⍺⍵]              otherwise return the sorted first elements of both arrays
                          ,⊃∇/        followed by the result of running the function with
                               1↓¨⍺⍵}  both arrays minus their first element

LISP, 117 Bytes

Der Algorithmus endet in n + 1Iterationen, wobei ndie Länge der kürzesten Liste in der Eingabe ist.

(defun o(a b)(let((c(car a))(d(car b)))(if(null a)b(if(null b)a(if(< c d)(cons c(o(cdr a)b))(cons d(o a(cdr b))))))))

PYG (50)

def m(*a):
 while An(a):yield Mn(ItCo(a,a)).pop(0)

PYG (wieder 64, wenn keine Generatoren erlaubt sind.):

def m(*a):
 r=[]
 while An(a):r+=[(Mn(ItCo(a,a)).pop(0)]
 return r

Eine Anpassung von meiner Python Antwort .

Python - 69 Bytes

def m(A,B):
    C=[]
    while A and B:C+=[[A,B][A>B].pop(0)]
    return C+A+B

Wenn die Reihenfolge von Eingabe und Ausgabe absteigend wäre, könnte dies auf 61 Byte verkürzt werden :

def m(A,B):
    C=[]
    while A+B:C+=[[A,B][A<B].pop(0)]
    return C

Und weiter bis zu 45 Bytes, wenn Generatoren erlaubt sind:

def m(A,B):
    while A+B:yield[A,B][A<B].pop(0)

Perl 6: 53 Zeichen

sub M(\a,\b){{shift a[0]>b[0]??b!!a}...{a^b},a[],b[]}

Verschieben Sie den Wert von aoder bmit dem kleineren Wert, bis aXOR b( a^b) wahr ist. Geben Sie dann alles zurück, was noch übrig ist, und reduzieren Sie []die Arrays in der Liste ( a[],b[]).

Unter der Annahme, dass die Verschiebung vom Anfang eines Arrays an O (n) ist, sind zwei Vergleiche und eine Verschiebung pro Element der schlimmste Fall, sodass der Algorithmus O (n) ist.

JavaScript (ES5) 90 86 90 Bytes

function f(a,b){for(o=[];(x=a[0]<b[0]?a:b).length;)o.push(x.shift());return o.concat(a,b)}

edit: (90 -> 86) Verschob den Ternären in die for-Schleifenbedingung. Idee von Dennis gestohlen.

edit: (86 -> 90) Die Umwandlung von Array in String wurde entfernt, da das O (n) gebrochen wird -Anforderung verletzt.

Mathematica, 137, 135

m[a_,b_]:=(l=a;Do[Do[If[b[[f]]<=l[[s]],(l=Insert[l,b[[f]],s];Break[]),If[s==Length@l,l=l~Append~b[[f]]]],{s,Length@l}],{f,Length@b}];l)

Eingang:

m[{2,2,4,6,7,11},{1,2,3,3,3,3,7}]

Ausgabe:

{1, 2, 2, 2, 3, 3, 3, 3, 4, 6, 7, 7, 11}

Ungolfed:

mergeList[a_, b_] := (
    list = a;
    Do[
        Do[(
            If[
                b[[f]] <= list[[s]],
                (list = Insert[list, b[[f]], s]; Break[]),
                If[
                    s == Length@list,
                    list = list~Append~b[[f]]
                ]
        ]),
        {s, Length@list}
    ],
    {f, Length@b}
    ];
    list
)

Könnte es wahrscheinlich besser machen.

R 80

Gleiche Lösung wie in Scala und anderen Sprachen. Ich bin mir nicht so sicher, ob x [-1] O (1) ist.

f=function(a,b)if(length(a)){if(a[1]<=b[1])c(a[1],f(a[-1],b))else f(b,a)}else b

Mathematica, 104 Bytes

Reap[{m,n}=Length/@{##};i=k=1;Do[If[k>n||TrueQ[#[[i]]<#2[[k]]],Sow@#[[i++]],Sow@#2[[k++]]],n+m]][[2,1]]&

Anonymous-Funktion, speichert die Länge der beiden Eingabelisten in den Variablen mund ndann ist jede Iteration der DoSchleife Sowein Element einer der Listen, die den Zähler für diese Liste erhöhen ( ifür die erste,k für die zweite) um eins wird. Wenn einer der Zähler die Länge der Liste überschreitet, wird die IfAnweisung immer Sowdas Element aus der anderen Liste sein. Nach der n+mOperation sind alle Elemente erledigt.Reapoder vielmehr [[2,1]]ist ein Teil seiner Ausgabe eine Liste von Elementen in der Reihenfolge, in der sie warenSow n waren.

Ich bin mir der Interna nicht sicher (greift auf einen Teil einer Liste zu) O(1) Operation oder nicht), aber die Timings auf meinem Computer sahen in Bezug auf die Länge der eingegebenen Liste recht linear aus.