Ich soll eine Liste von Zahlen sortieren, aber ich bin super faul. Es ist wirklich schwer herauszufinden, wie man alle Zahlen vertauscht, bis sie alle in aufsteigender Reihenfolge vorliegen. Deshalb habe ich einen eigenen Algorithmus entwickelt, der sicherstellt, dass die neue Liste sortiert ist¹. So funktioniert das:

Für eine Liste der Größe N benötigen wir N-1 Iterationen. Bei jeder Iteration

• Überprüfen Sie, ob die N-te Zahl kleiner als die N + 1-te Zahl ist. Wenn dies der Fall ist, sind diese beiden Zahlen bereits sortiert, und wir können diese Iteration überspringen.

• Wenn dies nicht der Fall ist, müssen Sie die ersten N Zahlen kontinuierlich dekrementieren, bis diese beiden Zahlen in Ordnung sind.

Nehmen wir ein konkretes Beispiel. Angenommen, die Eingabe war

10 5 7 6 1

Bei der ersten Iteration vergleichen wir 10 und 5. 10 ist größer als 5, also dekrementieren wir es, bis es kleiner ist:

4 5 7 6 1

Jetzt vergleichen wir 5 und 7. 5 ist kleiner als 7, sodass wir bei dieser Iteration nichts tun müssen. Also gehen wir zum nächsten und vergleichen 7 und 6. 7 ist größer als 6, also dekrementieren wir die ersten drei Zahlen, bis sie kleiner als 6 sind, und wir erhalten Folgendes:

2 3 5 6 1

Jetzt vergleichen wir 6 und 1. Auch hier ist 6 größer als 1, also dekrementieren wir die ersten vier Zahlen, bis sie kleiner als 1 sind, und wir erhalten Folgendes:

-4 -3 -1 0 1

Und wir sind fertig! Jetzt ist unsere Liste perfekt sortiert. Und um die Sache noch besser zu machen, mussten wir die Liste nur N-1- mal durchlaufen , sodass dieser Algorithmus Listen in O (N-1) -Zeit sortiert. Ich bin mir ziemlich sicher, dass dies der schnellste Algorithmus ist, den es gibt.²

Ihre Herausforderung für heute ist es, diese Lazy Sort zu implementieren. Ihr Programm oder Ihre Funktion erhält ein Array von Ganzzahlen in einem beliebigen Standardformat, und Sie müssen diese verzögerte Sortierung durchführen und die neue "sortierte" Liste zurückgeben. Das Array wird niemals leer sein oder Nicht-Ganzzahlen enthalten.

Hier sind einige Beispiele:

Input: 10 5 7 6 1
Output: -4 -3 -1 0 1

Input: 3 2 1
Output: -1 0 1

Input: 1 2 3
Output: 1 2 3

Input: 19
Output: 19

Input: 1 1 1 1 1 1 1 1 1 
Output: -7 -6 -5 -4 -3 -2 -1 0 1 

Input: 5 7 11 6 16 2 9 16 6 16
Output: -27 -25 -21 -20 -10 -9 -2 5 6 16

Input: -8 17 9 7
Output: -20 5 6 7

Wie immer ist dies Code-Golf , schreiben Sie also das kürzeste Programm, das Sie können!

¹ Dies bedeutet nicht, wie es sich anhört, aber es ist technisch wahr

² Ich mache nur Spaß, bitte hasse mich nicht

Jelly ,  14 12 11  9 Bytes

-2 Bytes dank ETHproductions (benutze die minimale Dyade, «)

I’«0Ṛ+\Ṛ+

Ein monadischer Link, der Listen mit ganzen Zahlen aufnimmt und zurückgibt.

Probieren Sie es online! oder sehen Sie sich die Testsuite an .

Ich glaube wirklich nicht, dass dies Lazy ™ genug ist!

Wie?

I’«0Ṛ+\Ṛ+ - Link: list of integers, a              e.g. [ 8, 3, 3, 4, 6, 2]
I         - increments between consecutive items of a   [-5, 0, 1, 2,-4 ]
 ’        - decrement (vectorises)                      [-6,-1, 0, 1,-5 ]
   0      - literal 0
  «       - minimum of decremented increments and zero  [-6,-1, 0, 0,-5 ]
    Ṛ     - reverse                                     [-5, 0, 0,-1,-6 ]
      \   - cumulative reduce with:
     +    -   addition                                  [-5,-5,-5,-6,-12]
       Ṛ  - reverse                                     [-12,-6,-5,-5,-5]
        + - addition (with a)                           [-4,-3,-2,-1, 1, 2]

Haskell , 40 Bytes

f(a:r)|h:t<-f r=h-max(r!!0-a)1:h:t
f x=x

Probieren Sie es online!

JavaScript (ES6), 61 Byte

a=>a.map((b,i)=>a=(b-=a[i+1])>0?a.map(c=>i--<0?c:c-b-1):a)&&a

Testfälle

let f =

a=>a.map((b,i)=>a=(b-=a[i+1])>0?a.map(c=>i--<0?c:c-b-1):a)&&a

console.log(JSON.stringify(f([10, 5, 7, 6, 1]))) // -4 -3 -1 0 1
console.log(JSON.stringify(f([3, 2, 1]))) // -1 0 1
console.log(JSON.stringify(f([1, 2, 3]))) // 1 2 3
console.log(JSON.stringify(f([19]))) // 19
console.log(JSON.stringify(f([1, 1, 1, 1, 1, 1, 1, 1, 1]))) // -7 -6 -5 -4 -3 -2 -1 0 1
console.log(JSON.stringify(f([5, 7, 11, 6, 16, 2, 9, 16, 6, 16]))) // 27 -25 -21 -20 -10 -9 -2 5 6 16
console.log(JSON.stringify(f([-8, 17, 9, 7]))) // -20 5 6 7

Gelee , 12 Bytes

I»1U
0ị;Ç_\U

Probieren Sie es online!

Wie es funktioniert

I»1U  Helper link. Argument: l (list of integers)
I     Compute the increments (difference between items) of l.
 »1   For each item n, take the maximum of n and 1.
   U  Reverse.

0ị;Ç_\U  Main link. Argument: l (list of integers)
   Ç     Call the helper link with argument l.
  ;      Concatenate this with
0ị       the 0th last item of the (1-indexed) l. (Can't use Ṫ because it modifies l)
    _\   Cumulatively reduce the result by subtraction.
      U  Reverse.

Die Grundidee lautet: Wenn Sie die Eingabe- und Ausgabearrays vertauschen, ist die Ausgabe einfach die Eingabe, wobei jedes Delta von 0 oder höher durch -1 ersetzt wird. Zum Beispiel:

[10,  5,  7,  6,  1]   input
[ 1,  6,  7,  5, 10]   reverse
[   5,  1, -2,  5  ]   deltas
[  -1, -1, -2, -1  ]   min(deltas, -1)
[ 1, -1, -2, -1, -1]   reverse and concat the last item of the original
[ 1,  0, -2, -3, -4]   re-apply deltas
[-4, -3, -2,  0,  1]   reverse

k, 20 Bytes

{x-|+\0,1_0|1+-':|x}

Probieren Sie es online aus.

Erläuterung:

{                  } /function, x is input
                 |x  /reverse x
              -':    /difference between every element
            1+       /add one to each difference
          0|         /make minimum difference be 0
      0,1_           /swap first difference with a 0
    +\               /cumulative sum
   |                 /reverse again
 x-                  /subtract from x

Haskell, 56 Bytes

a#(x:y:z)=map(+min(y-x-1)0)(a++[x])#(y:z)
a#x=a++x
([]#)

Probieren Sie es online!

Behalten Sie den ersten Teil der Liste als Parameter bei a. Fügen Sie bei jedem Schritt das nächste Element xzum Ende von hinzu aund erhöhen Sie alle Elemente von a um das Minimum von (y-x-1)und 0.

Python , 54 Bytes

f=lambda a,*r:r and[f(*r)[0]-max(r[0]-a,1)]+f(*r)or[a]

Probieren Sie es online!

Nimmt eingegebenen splatted wie f(1,2,3). Gibt eine Liste aus. Verwendet exponentielle Zeit.

76 Bytes

a=>{for(int d=0,i=a.Length-1;i>0;a[--i]-=d)d=a[i-1]-d<a[i]?d:a[i-1]-a[i]+1;}

Dadurch wird die Liste geändert. Es geht die Liste rückwärts durch und behält eine laufende Summe des Deltas bei, das für jede Zahl gilt.

JavaScript (ES6), 59 Byte

f=([n,...a],p=a[0]-n)=>a+a?[(a=f(a))[0]-(p>1?p:1),...a]:[n]

Brain-Flak , 153 Bytes

{(({})<>[({})])(({}({}))[({}[{}])])<>(([{}]({})))([({}<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}{{}({}<>{}())((<>))}{}{}}{}<>{}([]){{}({}<>)<>([])}<>

Probieren Sie es online!

Dies gilt auch +1für die -rFlagge.

#While True
{

    #Push the last value left in the array minus the counter onto the alternate stack
    (({})<>[({})])

    #Put the counter back on top of the alternate stack
    (({}({}))[({}[{}])])

    #Toggle
    <>

    #Find the difference between the last two inputs left on the array
    (([{}]({})))

    #Greater than or equal to 0?
    ([({}<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}

    #If So:
    {

      #Pop the truthy/falsy value
      {}

      #Increment the counter by the difference between elements +1
      ({}<>{}())

      #Push two falsys
      ((<>))

    #Endwhile
    }

    #Pop the two falsys
    {}{}

#Endwhile
}

#Pop the falsy

{}

#Toggle back
<>

#Pop the counter

#Reverse the stack
{}
([]){{}({}<>)<>([])}<>

R, 56 Bytes

function(s){s-c(rev(cumsum(rev(pmax(0,-diff(s)+1)))),0)}

JavaScript (ES6), 68 Byte

a=>a.map((v,i)=>(d=v-o[i+1]+1)>1?o=o.map((v,j)=>j>i?v:v-d):0,o=a)&&o

Ein- und Ausgabe ist ein Array von ganzen Zahlen.

Testschnipsel

f=
a=>a.map((v,i)=>(d=v-o[i+1]+1)>1?o=o.map((v,j)=>j>i?v:v-d):0,o=a)&&o

<input id=I oninput="O.value=f(this.value.split` `.map(x=>+x)).join` `">
<input id=O disabled>

JavaScript (ES6), 50 Byte

f=a=>(b=[...a]).some((_,i)=>a[i]-->=a[i+1])?f(a):b

Erläuterung:

Dies ist eine rekursive Lösung, bei der zuerst das Array geklont und dann alle Werte verringert werden, bis ein Element größer oder gleich dem nächsten Element im Array ist.

Die Funktion ruft sich selbst auf, solange Elemente nicht in Ordnung sind. Wenn die Elemente endgültig sortiert sind, wird der Klon zurückgegeben. (Das Array selbst kann nicht zurückgegeben werden, da die some()Methode alle seine Elemente dekrementiert und sie alle um -1 deaktiviert hätte.)

Testfälle:

f=a=>(b=[...a]).some((_,i)=>a[i]-->=a[i+1])?f(a):b

console.log(f([10,5,7,6,1])+'');
console.log(f([1,1,1,1,1,1,1,1,1])+'');
console.log(f([5,7,11,6,16,2,9,16,6,16])+'');
console.log(f([19])+'');
console.log(f([-8,17,9,7])+'');
console.log(f([1,2,3,4,5,6,7])+'');

SWI-Prolog, 194 Bytes

:-use_module(library(clpfd)).
f([],[],_,_).
f([A|B],[M|N],P,D):-A#=M-D-E,A#<P,abs(M,S),T#=S+1,E in 0..T,label([E]),f(B,N,A,D+E).
l([],[]).
l(A,B):-reverse(Z,B),f([X|Y],Z,X+1,0),reverse(A,[X|Y]).

Vielleicht können Sie es hier online ausprobieren: http://swish.swi-prolog.org/p/LazySort.pl

Sie fragen, l(L, [10,5,7,6,1]).welche sagt "lösen für L, wobei L die träge sortierte Version dieser Liste ist".

Die zwei Funktionen sind:

• lazysortiert (A, B) - gibt an, dass A die lazysortierte Version von B ist, wenn beide leere Listen sind oder wenn A durch Umkehren von B, Aufrufen einer Hilfsfunktion zum Durchlaufen der Liste und Subtrahieren mit einem Akkumulator erhalten werden kann Schieben Sie jeden Wert niedriger als den vorherigen und kehren Sie das Ergebnis wieder in die richtige Richtung um.
• fDer Helfer vergleicht zwei Listen, den Wert der vorherigen Nummer in der Liste und einen fortlaufenden Differenzakkumulator, und berechnet, dass der neue Wert der aktuellen Listenposition der ursprüngliche Wert abzüglich des Differenzakkumulators ist, optional abzüglich eines neuen Werts, der erforderlich ist, um dies zu erzwingen Wert unter der vorherigen Nummer in der Liste und fmuss mit dem nun erhöhten Differenzakkumulator rekursiv nach dem Ende der Liste aufgelöst werden.

Screenshot der Testfälle auf Swish:

JavaScript (ES6), 61 Byte

a=>a.reduceRight((r,e)=>[e-(d=(c=e-r[0]+1)>d?c:d),...r],d=[])

Nicht die kürzeste Lösung, aber ich konnte die Gelegenheit nicht nutzen reduceRight.

C # (.NET Core) , 89 88 86 79 Bytes

• Nur 1 Byte mit einem etwas anderen Ansatz gespeichert.
• Weitere 2 Bytes mit einer Vereinfachung des fors gespeichert .
• 7 Bytes gespart dank der erstaunlichen Golffähigkeiten von VisualMelon.

a=>{for(int i=0,j,k;++i<a.Length;)for(k=a[i-1]-a[j=i]+1;--j>=0;)a[j]-=k>0?k:0;}

Probieren Sie es online!

Zuerst fordurchläuft es das Array, dann berechnet es die Dekrementierung und schließlich fordekrementiert das zweite die Elemente, falls erforderlich, bis zur ivierten Position.

Ist es gültig, nur das ursprüngliche Array zu ändern, anstatt ein neues zurückzugeben (gewöhnt sich immer noch an die Regeln)?