Mettre en place le "Tri paresseux"

44

Je suis censé trier une liste de chiffres, mais je suis super paresseux. Il est très difficile de trouver comment échanger tous les nombres jusqu'à ce qu'ils soient tous dans un ordre croissant. J'ai donc créé mon propre algorithme qui garantira que la nouvelle liste sera triée¹. Voici comment cela fonctionne:

Pour une liste de taille N , nous aurons besoin de N-1 itérations. A chaque itération,

  • Vérifiez si le nième nombre est plus petit que le n + lième nombre. Si tel est le cas, ces deux nombres sont déjà triés et nous pouvons ignorer cette itération.

  • S'ils ne le sont pas, vous devez continuellement décrémenter les N premiers nombres jusqu'à ce que ces deux nombres soient en ordre.

Prenons un exemple concret. Disons que l'entrée était

10 5 7 6 1

Lors de la première itération, nous comparerons 10 et 5. 10 étant supérieur à 5, nous le décrémentons jusqu'à ce qu'il soit plus petit:

4 5 7 6 1

Nous comparons maintenant 5 et 7. 5 est inférieur à 7, nous n'avons donc rien à faire avec cette itération. Nous allons donc au suivant et comparons 7 et 6. 7 est supérieur à 6, nous décrémentons donc les trois premiers nombres jusqu'à ce qu'il soit inférieur à 6, et nous obtenons ceci:

2 3 5 6 1

Maintenant nous comparons 6 et 1. Encore une fois, 6 est supérieur à 1, nous décrémentons donc les quatre premiers nombres jusqu'à ce qu'il soit inférieur à 1, et nous obtenons ceci:

-4 -3 -1 0 1

Et nous avons fini! Maintenant, notre liste est en parfait ordre de tri. Et, pour améliorer encore les choses, il nous suffisait de parcourir la liste N-1 fois. Cet algorithme trie donc les listes en un temps O (N-1) , ce qui, j'en suis presque sûr, est l'algorithme le plus rapide qui soit.²

Votre défi pour aujourd'hui est de mettre en œuvre ce tri paresseux. Votre programme ou fonction recevra un tableau d’entiers dans le format standard de votre choix. Vous devez effectuer ce tri paresseux et renvoyer la nouvelle liste "triés" . Le tableau ne sera jamais vide ou ne contiendra pas des entiers.

Voici quelques exemples:

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

Comme toujours, c'est du , alors écrivez le programme le plus court possible!


¹ Cela ne veut pas dire à quoi ça ressemble, mais c'est techniquement vrai

² Je plaisante complètement, s'il vous plaît ne me déteste pas

DJMcMayhem
la source
6
Je pense que vous n'êtes pas paresseux si vous le faites de cette façon
Jörg Hülsermann
4
@ JörgHülsermann et certains entiers sont trop lourds ... pas vraiment d'humeur à porter un tel poids, mieux vaut enlever tout ce qu'il y a de mieux
Erik the Outgolfer -
21
<sarcasm>En réalité, cet algorithme de tri est toujours O(N^2)complexe, car vous devez parcourir tous les éléments de la liste auxquels vous avez déjà accédé pour les décrémenter. Je recommande de parcourir la liste à l' envers et de ne décrémenter qu'un nombre par étape si nécessaire. Cela vous donnera une vraie O(N)complexité! </sarcasm>
Valeur d'encre
1
@ValueInk O(n^2)en termes d'accès mémoire, mais n'est-ce pas O(n)pour les comparaisons?
Cole Johnson
7
@ColeJohnson techniquement oui, mais la complexité temporelle doit prendre en compte toutes les étapes de l'algorithme. Il vous reste à parcourir tous les index précédents à chaque itération, donc il sort toujours O(N^2).
Valeur d'encre

Réponses:

12

Jelly ,  14 12 11  9 octets

-2 octets grâce aux ETHproductions (utilisez la dyade minimale, «)

I’«0Ṛ+\Ṛ+

Un lien monadique prenant et renvoyant des listes d'entiers.

Essayez-le en ligne! ou voir la suite de tests .

Je ne pense vraiment pas que c'est assez Lazy ™!

Comment?

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]
Jonathan Allan
la source
12

Haskell , 40 octets

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

Essayez-le en ligne!

Xnor
la source
11
Un langage paresseux semble approprié pour ce défi
tomsmeding
8

JavaScript (ES6), 61 octets

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

Cas de test

Arnauld
la source
7

Gelée , 12 octets

I»1U
0ị;Ç_\U

Essayez-le en ligne!

Comment ça marche

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.

L'idée de base en jeu est la suivante: si vous inversez les tableaux d'entrée et de sortie, la sortie est simplement l'entrée avec chaque delta de 0 ou plus remplacé par -1. Par exemple:

[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
ETHproductions
la source
5

k, 20 octets

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

Essayez-le en ligne.

Explication:

{                  } /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
zgrep
la source
4

Haskell, 56 octets

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

Essayez-le en ligne!

Conservez la première partie de la liste en paramètre a. A chaque étape, ajoutez l'élément suivant xà la fin de aet augmentez tous les éléments de a au minimum de (y-x-1)et 0.

nimi
la source
4

Python , 54 octets

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

Essayez-le en ligne!

Prend une entrée éclaboussée comme f(1,2,3). Affiche une liste. Utilise le temps exponentiel.

Xnor
la source
3

C #, 76 octets

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

Cela modifie la liste en place. Il parcourt la liste en arrière et conserve un total cumulé du delta à appliquer à chaque numéro.

Hand-E-Food
la source
2

JavaScript (ES6), 59 octets

f=([n,...a],p=a[0]-n)=>a+a?[(a=f(a))[0]-(p>1?p:1),...a]:[n]
ETHproductions
la source
Sensationnel. J'étais sur le point d'écrire une solution JS, mais j'ai ensuite vu cela. Je ne pensais pas utiliser l'opérateur de propagation comme ça dans les paramètres
andrewarchi
Vous pouvez laisser les f=réponses JS économiser deux octets
andrewarchi
@andrewarchi Merci, mais cette fonction particulière a besoin de s'appeler elle-même ( f(a)), elle a donc toujours besoin du nom.
ETHproductions
J'ai oublié que c'était récursif
andrewarchi
2

Brain-Flak , 153 octets

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

Essayez-le en ligne!

Cela inclut +1pour le -rdrapeau.

#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
{}
([]){{}({}<>)<>([])}<>
DJMcMayhem
la source
2

R, 56 octets

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

aPaulT
la source
1
Bien utilisé diff, j’essayais de comprendre comment le faire fonctionner ... Soit dit en passant, vous pouvez vous débarrasser des accolades autour du corps de la fonction pour -2 octets, mais mieux encore, vous pouvez utiliser la s=scan()place d’une fonction définition pour économiser quelques octets de plus. Ce serait bien si vous incluiez un lien vers Essayez-le en ligne afin que d'autres personnes puissent vérifier que ce code fonctionne pour tous les cas de test.
Giuseppe
Pas de soucis! nous commençons tous quelque part :)
Giuseppe
1

JavaScript (ES6), 68 octets

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

L'entrée et la sortie est un tableau d'entiers.

Test Snippet

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>

Justin Mariner
la source
1

JavaScript (ES6), 50 octets

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

Explication:

Il s'agit d'une solution récursive, qui clone d'abord le tableau, puis diminue toutes les valeurs jusqu'à ce qu'un élément soit supérieur ou égal à l'élément suivant du tableau.

La fonction s’appelle elle-même tant que tous les éléments sont en panne. Lorsque les éléments sont enfin triés, le clone est renvoyé. (Nous ne pouvons pas renvoyer le tableau lui-même, car la some()méthode aurait décrémenté tous ses éléments, ce qui les aurait tous rendus par -1.)

Cas de test:

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])+'');

Rick Hitchcock
la source
1

SWI-Prolog, 194 octets

:-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]).

Peut-être en mesure de l'essayer en ligne ici: http://swish.swi-prolog.org/p/LazySort.pl

Vous demandez l(L, [10,5,7,6,1]).qui dit "résoudre pour L, où L est la version triée paresseuse de cette liste".

Les deux fonctions sont:

  • lazysorted (A, B) - indique que A est la version de B lazysorted, s'il s'agit de deux listes vides, ou si A peut être obtenu en inversant B, en appelant une fonction d'assistance pour parcourir la liste et effectuer une soustraction avec un accumulateur. en poussant chaque valeur plus basse que la précédente et en inversant le résultat de cette manière.
  • fhelper fait correspondre deux listes, la valeur du numéro précédent dans la liste et un accumulateur de différence en continu, et résout pour la nouvelle valeur de la position actuelle de la liste étant la valeur d'origine moins l'accumulateur de différence, éventuellement une nouvelle valeur nécessaire pour forcer valeur inférieure au numéro précédent dans la liste, et fdoit résoudre pour la queue de la liste de manière récursive avec l’accumulateur de différence désormais augmenté.

Capture d'écran des cas de test sur Swish:

image montrant les tests en cours sur Swish

TessellatingHeckler
la source
0

JavaScript (ES6), 61 octets

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

Pas la solution la plus courte, mais je ne pouvais pas laisser passer l'occasion d'utiliser reduceRight.

Neil
la source
0

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

  • Sauvegardé seulement 1 octet avec une approche légèrement différente.
  • Sauvegardé 2 autres octets avec une simplification de la fors.
  • Sauvegardé 7 octets grâce aux incroyables compétences de VisualMelon en matière de golf.
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;}

Essayez-le en ligne!

Il forparcourt d'abord le tableau, puis calcule le décrément et enfin le second fordécrémente les éléments, si nécessaire, jusqu'à la iposition th.

Est-il valide de simplement modifier le tableau d'origine au lieu d'en retourner un nouveau (en s'habituant toujours aux règles)?

Charlie
la source
Oui, la modification de la matrice d'origine convient parfaitement. :)
DJMcMayhem
4
@DJMcMayhem merci, je me suis senti trop paresseux pour en créer un nouveau. :)
Charlie