Déplacement minimum modeste

40

Inspiré par une question sur Stack Overflow. Le titre ici est entièrement de ma faute.


Le défi

Étant donné une liste d'entiers positifs contenant au moins deux entrées, remplacez chaque nombre par le minimum de toutes les entrées qui l'excluent.

Cas de test

[4 3 2 5]    ->  [2 2 3 2]
[4 2 2 5]    ->  [2 2 2 2]
[6 3 5 5 8]  ->  [3 5 3 3 3]
[7 1]        ->  [1 7]
[9 9]        ->  [9 9]
[9 8 9]      ->  [8 9 8]

Règles

L'algorithme devrait théoriquement fonctionner pour toute taille d'entrée (supérieure à un) et toutes valeurs (nombres entiers positifs). Il est accepté si le programme est limité par le temps, la mémoire ou les types de données et ne fonctionne donc que pour les nombres jusqu'à une valeur donnée ou pour la taille d'entrée jusqu'à une valeur donnée.

Les programmes ou fonctions sont autorisés, dans n'importe quel langage de programmation . Les échappatoires standard sont interdites.

La saisie peut être prise par n'importe quel moyen raisonnable ; et avec n'importe quel format. Idem pour la sortie. Les formats d'entrée et de sortie peuvent être différents.

Le code le plus court en octets gagne.

Luis Mendo
la source
Que devrait [4 3 2 2 5]sortir?
Kritixi Lithos
@KritixiLithos le deuxième cas de test n'a-t-il pas couvert cela?
Leaky Nun
@KritixiLithos Pour l'entrée, [4 3 2 2 5]la sortie serait [2 2 2 2 2](c'est similaire au deuxième cas de test)
Luis Mendo
Oh, j'ai raté le deuxième cas de test. Mais maintenant je comprends comment ça marche
Kritixi Lithos
@LuisMendo Vous avez remplacé "entier" par "taille et valeur d'entrée". Cela signifie-t-il que nous devons comptabiliser tous les nombres réels?
Nonne qui fuit

Réponses:

19

Gelée , 9 6 5 octets

JḟÐ € 
ṙJṙ € €
ṙJṖ «/ argument: tableau 1D (z)

 J [1,2,3, ..., len (z)]
ṙ faire pivoter z de chacun des montants ci-dessus (le tableau actuel est 2D)
  Ṗ supprimer le dernier tableau
   «/ Réduire de [implicitement vectorisé] minimum

Essayez-le en ligne!

Vérifiez tous à la fois!(légèrement modifié)

Je suis à peu près sûr que Dennis pourra jouer au golf.

Comment ça marche

L'algorithme est plutôt compliqué. Observons ce que cela fait[4,2,2,5] .

Tout d'abord, nous utilisons Jpour obtenir[1,2,3,4] . Notez que Jelly utilise 1-indexing.

Ensuite, on voit . Il faut deux arguments: un tableau et un entier. Il fait pivoter le tableau vers la gauche d'une quantité spécifiée par l'entier. Ici, on verrait [4,2,2,5]à sa gauche et [1,2,3,4]à sa droite (on trouvera plus de détails sur la façon dont cela fonctionne dans le tutoriel). ). En Jelly, les commandes sont implicitement vectorisées. Par conséquent, cette commande sera exécutée sur chaque élément individuel à droite, c'est pourquoi nous créerions un tableau 2D:

Par conséquent, [4,2,2,5]ṙ[1,2,3,4]devient [[4,2,2,5]ṙ1,[4,2,2,5]ṙ2,[4,2,2,5]ṙ3,[4,2,2,5]ṙ4]ce qui devient:

[[2,2,5,4],
 [2,5,4,2],
 [5,4,2,2],
 [4,2,2,5]]

Notez que les éléments d'origine se trouvent sur la dernière ligne, car dans cette ligne, nous avons effectué une rotation vers la gauche d'un montant égal à la longueur du tableau. C'est pourquoi nous utilisons ensuite pour supprimer cette ligne, de sorte que les colonnes constituent les collections de les éléments du tableau qui ne sont pas à l'index actuel:

[[2,2,5,4],
 [2,5,4,2],
 [5,4,2,2]]

L'opération suivante «/, est également assez compliquée. Tout d'abord, «renvoie le minimum des deux nombres qu'il voit à sa gauche et à sa droite. Par exemple, 5«3retourne 3. Maintenant, si les deux arguments sont des tableaux, alors cela vectoriserait comme je l’ai dit plus haut. Qu'est-ce que cela signifie que [1,5,2,3]«[4,1,5,2]cela deviendrait [1«4,5«1,2«5,3«2]ce qui est [1,1,2,2]. Now, /is reduce, ce qui signifie que nous effectuons l'opération sur chaque ligne jusqu'à la fin. Par exemple, [1,2,3,4]+/deviendrait ((1+2)+3)+4, qui est la somme du tableau [1,2,3,4].

Donc, si nous appliquons «/au tableau 2D que nous venons d'obtenir, nous obtiendrions:

([2,2,5,4]«[2,5,4,2])«[5,4,2,2]

qui, du fait de la vectorisation, équivaudrait à:

[2«2«5,2«5«4,5«4«2,4«2«2]

qui calcule le minimum de chaque tableau sans l'élément à l'index.

Fuite Nun
la source
1
Oh, ton montage ... tu y es arrivé le premier.
Jonathan Allan
1
@ JonathanAllan Je suis désolé.
Leaky Nun
40

Python 2 , 41 octets

lambda l:[sorted(l)[x==min(l)]for x in l]

Essayez-le en ligne!

Pour chaque élément, xnous vérifions si x==min(l). Si ce n'est pas le cas, il est Falsetraité comme 0s'il était utilisé comme un index de liste en sorted(l)donnant le plus petit élément. Dans le cas contraire, il est Trueaka 1, donnant le deuxième plus petit élément, puisque cet élément lui - même est le plus petit et doit être ignorée.

Xnor
la source
2
J'ai du mal à croire que cela fonctionne.
Leaky Nun
2
Bonne approche!
Luis Mendo
Pourriez-vous ajouter une explication? Ce ne serait pas très compliqué, mais le truc de "chaque nombre sera le minimum, sauf celui qui est le minimum, qui sera le deuxième plus petit" et le fait de Falsese convertir 0et de Truese convertir 1sont vraiment refroidir et devrait être vanté d'avoir ^ W ^ Wexplained
Fonds Lawsuit Monica
18

Gelée , 5 octets

=Ṃ‘ịṢ

Essayez-le en ligne!

Comment?

=Ṃ‘ịṢ - Main link: list a     e.g.  [4,3,2,5]
 Ṃ    - minimum of a                2
=     - equals? (vectorises)        [0,0,1,0]
  ‘   - increment                   [1,1,2,1]
    Ṣ - sort a                      [2,3,4,5]
   ị  - index into                  [2,2,3,2]
Jonathan Allan
la source
4
@ LeakyNun Ce n'est pas un port, c'est juste la même méthode, je cherche toujours moins aussi ... J'ai voté aussi cette réponse :)
Jonathan Allan
5
@ LeakyNun Je suis nouveau ici, mais es-tu toujours aussi hostile? Ce n'est pas comme s'il y avait des tonnes de façons uniques d'aborder cela. Même s'il l'a fait, il a toujours la réponse la plus courte.
Grayson Kent
3
@GraysonKent Je m'excuse pour mon hostilité perçue.
Leaky Nun
1
@GraysonKent Bienvenue à PPCG!
Luis Mendo
1
@LeakyNun Cela se produit souvent dans des défis plus simples, vous ne pouvez pas vraiment dire que chaque réponse est un port sur tous les autres
ASCII uniquement
12

Haskell , 42 41 39 octets

MODIFIER:

  • -1 octet grâce à nimi!
  • -2 octets. Un merci à xnor! Et un par moi-même.

fprend une liste d'entiers (ou n'importe quel Ordtype) et retourne une liste.

f(x:y)=minimum y:(fst<$>zip(f$y++[x])y)

Essayez-le en ligne!

frécursive en faisant tourner la liste. xest le premier élément de la liste et yle reste. Comme la récursion est infinie, la liste des résultats doit être coupée: fst<$>zip...yc'est une façon plus courte de dire take(length y)....

Ørjan Johansen
la source
1
Vous pouvez enregistrer un octet en nommant toute la liste d'entrée par l' intermédiaire @et retourner les listes pour être compressé: f l@(x:y)=fst<$>zip(minimum...)l.
nimi
1
f(h:t)=minimum t:(fst<$>zip(f(t++[h]))t)
xnor
9

Octave, 26 octets

@(x)sort(x)((x==min(x))+1)

Une approche similaire à celle utilisée dans cette réponse , qui se trouve être la même chose que ceci .

Je ne suis pas vraiment fan de simplement porter d'autres réponses, c'est pourquoi j'aimerais souligner que j'avais une idée similaire avant de voir les autres.

Explication:

Jonathan Allan a déjà fourni une bonne explication pour le code Jelly, il couvre donc le bit Octave et explique pourquoi cela fonctionne (et ne fonctionnerait pas dans MATLAB).

@(x)                       % An unnamed anonymous function taking a vector x as input
    sort(x)                % Gives a sorted version of x
            (x==min(x))    % Checks if each element is equal to the minimum value
           ((x==min(x))+1) % Adds 1 to the boolean vector, to use as indices
@(x)sort(x)((x==min(x))+1) % Complete function

Cela ne fonctionne pas dans MATLAB, car les assignations en ligne et l'indexation directe ne fonctionnent pas. sort(x)(1)donne une erreur dans MATLAB, pas le premier élément du vecteur trié.

Stewie Griffin
la source
8

Haskell, 41 octets

a#(b:c)=minimum(a++c):(b:a)#c
a#b=b 
([]#)

Exemple d'utilisation: ([]#) [4,3,2,5]->[2,2,3,2] . Essayez-le en ligne!

Commencez avec un accumulateur vide aet parcourez la liste des entrées. L'élément suivant dans la liste de sortie est le minimum de l'accumulateur aet tout sauf le premier élément de la liste d'entrée (-> c) suivi d'un appel récursif avec le premier élément bajouté à l'accumulateur et c. Arrêtez-vous lorsque vous atteignez la fin de la liste de saisie.

nimi
la source
7

JavaScript (ES6), 50 46 octets

a=>a.map((_,i)=>Math.min(...a.filter(_=>i--)))

Edit: 4 octets enregistrés grâce à @Arnauld.

Neil
la source
a=>a.map(x=>Math.min(...a.filter(y=>x!=y)))pour 43 octets.
Shaggy
@ Shaggy Je ne pense pas que cela fonctionne pour une entrée telle que3,3,3,3
Arnauld
D'oh! Non, cela ne fonctionnera pas s'il y a 2 occurrences ou plus de la valeur minimale.
Shaggy
1
Cependant, vous pouvez faire a=>a.map((_,i)=>Math.min(...a.filter(_=>i--)))pour 46.
Arnauld
@Arnauld Très intelligent, merci!
Neil
7

Brachylog , 13 12 octets

l+₁:?⊇ᶠ⁽⌋ᵐb↔

Essayez-le en ligne!

Sauvegardé d'un octet grâce à @ ais523.

Explication

l+₁:?            The list [length(Input) + 1, Input]
     ⊇ᶠ⁽         Find the length(Input) + 1 first subsets of the Input
        ⌋ᵐ       Get the min of each subset 
           b↔    Remove the first element and reverse

Nous exploitons le fait que l' uniformise les sous-ensembles du plus grand au plus petit. Par exemple pour[1,2,3] les sous - ensembles que nous recevons sont dans cet ordre: [1,2,3], [1,2], [1,3], [2,3], [1], [2], [3], [].

Nous pouvons voir que les sous [1,2], [1,3], [2,3]- ensembles sont ceux dont nous voulons le minimum, mais sont dans l'ordre inverse de la liste d'entrée (d'où le ). Nous pouvons sélectionner ces sous-ensembles uniquement en recherchant les premiers length(Input) + 1sous-ensembles, qui les contiendront tous + la liste complète en premier. Nous supprimons toute cette liste avec b.

Fataliser
la source
1
Vous pouvez enregistrer un octet en scindant votre "sous-ensemble findall + minimum" en "sous-ensemble findall" et en "mappage minimum". (Je dois ajouter ceci au fil de discussion de Brachylog, maintenant vous me l'avez rappelé.)
1
@ ais523 Merci, j'oublie toujours ce truc…
Fatalize
6

En fait , 13 octets

;;S╝m╗⌠╜=╛E⌡M

Utilise la même technique que xnor a également découverte .

Essayez-le en ligne!

Explication:

;;S╝m╗⌠╜=╛E⌡M
;;             make two extra copies of input list
  S╝           sort one and save it in register 1
    m╗         save the minimum of the other in register 0
      ⌠╜=╛E⌡M  for each value in list:
       ╜=╛E      return the minimum element of the input list if the value is not equal to the minimum, else return the second-smallest element
Mego
la source
1
Vous ne nous avez toujours pas autorisé à examiner la pile globale à l'intérieur de la pile temporaire?
Leaky Nun
1
@ LeakyNun Pas encore. Dans l'état actuel du code de l'interprète, ce serait très difficile. Après avoir terminé la refactorisation sur laquelle je travaille, je vais ajouter cette fonctionnalité.
Mego
1
Quand as-tu commencé la grande refactorisation?
Leaky Nun
6

R, 46 31 octets

l=scan();sort(l)[(min(l)==l)+1]

implémente la solution de Stewie Griffin dans R, hélas, mon idée originale est 50% plus longue! lit toujours la liste à partir de stdin, mais renvoie maintenant un vecteur numérique beaucoup plus lisible.

Essayez-le en ligne!

ancienne implémentation:

l=scan();Map(function(x)min(l[-x]),match(l,l))

lit dans la liste de stdin. Un index négatif l[-x]exclut l'élément de la liste et match(l,l)renvoie l'index de la première occurrence de chaque élément de la liste. Retourne une liste.

Giuseppe
la source
5

Python 2, 51 octets

Je sais qu'il existe déjà une meilleure solution Python, mais je souhaite toujours publier la mienne.

lambda L:[min(L[:i]+L[i+1:])for i in range(len(L))]

Essayez-le en ligne

mbomb007
la source
5

Mathematica 34 octets

Min[#~Drop~{i}]~Table~{i,Tr[1^#]}&
Kelly Lowder
la source
5

PowerShell , 68 59 octets

($a=$args)|%{$b+=@((($c=$a|sort)[0],$c[1])[$_-eq$c[0]])};$b

Essayez-le en ligne!

Je suis assez confiant que cela peut être raccourci, je vais continuer à le regarder

Sinusoïde
la source
4

C, 85 octets

i,j,m;f(d,o,n)int*d,*o;{for(i=n;i--;)for(m=d[!i],j=n;j;o[i]=m=--j^i&&d[j]<m?d[j]:m);}

Le premier argument est le tableau d'entiers en entrée. Le deuxième argument est le tableau entier en sortie. Le troisième argument est le nombre d'éléments pour les deux tableaux.

Voir le travail en ligne .

2501
la source
3

Perl 6 ,  26 24  19 octets

26

{.map: (.Bag∖*).min.key}

Notez que c'est U + 2216 pas \U + 5C

L'essayer

{.map: (.Bag⊖*).min.key}

L'essayer

24

{(.min X%$_)X||.sort[1]}

L'essayer

19

{.sort[.min X==$_]}

L'essayer


26

{           # bare block lambda with implicit parameter 「$_」

  .map:     # for each of the values in the input (implicit method call on 「$_」)
  (
    .Bag    # turn the block's input into a Bag
           # set-difference           「∖」 U+2216 aka 「(-)」
    # ⊖     # symmetric-set-difference 「⊖」 U+2296 aka 「(^)」
    *       # turn expression into a WhateverCode lambda (this is the parameter)
  ).min.key # get the minimum pair from the Bag, and return its key
}

J'ai utilisé les opérateurs unicode "fantaisistes" plutôt que les équivalents ascii, car ils auraient eu besoin d'un espace devant eux pour ne pas être analysés dans le cadre de l' .Bagappel de méthode.

24

{
  (.min X% $_) # the minimum cross modulus-ed with the input
  X||          # cross or-ed 
  .sort[1]     # with the second minimum
}

19

{
  .sort\        # sort the values
  [             # index into that
    .min X== $_ # the minimum cross compared with the input
  ]
}

(Les golfs de 24 et 19 octets ont été inspirés par une implémentation de Jelly )

Brad Gilbert b2gills
la source
3

Clojure, 36 81 62 71 octets

Le plus récent (ne devrait pas vraiment les soumettre rapidement):

#(for[c[(zipmap(range)%)]i(sort(keys c))](apply min(vals(dissoc c i))))

Essayez-le en ligne .

En outre, celui-ci ayant un bogue (62 octets), zipmap produit une carte non ordonnée afin que cela ne produise pas la séquence correcte sur des entrées plus volumineuses.

#(for[c[(zipmap(range)%)][i v]c](apply min(vals(dissoc c i))))

vn'est pas réellement utilisé pour quoi que ce soit mais c'est plus court que i (keys c).

Précédent à 81 octets:

Essayez-le en ligne .

#(let[r(range(count %))](for[i r](apply min(for[j r :when(not= i j)](nth % j)))))

Essayez-le en ligne .

Oh putain l'original (36 octets) ne fonctionne pas lorsque le nombre minimum est répété, les [4 2 2 5]résultats en [2 4 4 2]tant que les deux 2s sont supprimés :(

#(for[i %](apply min(remove #{i}%)))

#{i}est l'ensemble qui contient seulement i, il retourne la vérité iet la fausseté pour les autres, ce qui signifie que le minimum est calculé à partir de tous les autres nombres de la liste d'entrée.

Essayez-le en ligne .

NikoNyrh
la source
3

Pyth, 8 7 octets

mh.-SQ]

-1 octet grâce à @isaacg

Essayez le!

KarlKastor
la source
Vous pouvez supprimer la dfin - elle est implicitement remplie.
isaacg
@isaacg merci, je ne savais pas cela
KarlKastor
2

PHP, 72 octets

<?$k=$g=$_GET;sort($k);foreach($g as&$v)$v=$k[$v==$k[0]?:0];print_r($g);

Version en ligne

Jörg Hülsermann
la source
2

PHP, 47 octets

while(++$i<$argc)echo@min([z,$i=>z]+$argv),' ';
utilisateur63956
la source
2

Scala, 37 octets

l.indices map(i=>l diff Seq(l(i))min)

l est une collection de Int.

Cas de test:

scala> val l = List(4,3,2,5)
l: List[Int] = List(4, 3, 2, 5)

scala> l.indices map(i=>l diff Seq(l(i))min)
res0: scala.collection.immutable.IndexedSeq[Int] = Vector(2, 2, 3, 2)

scala> val l = List(4,2,2,5)
l: List[Int] = List(4, 2, 2, 5)

scala> l.indices map(i=>l diff Seq(l(i))min)
res1: scala.collection.immutable.IndexedSeq[Int] = Vector(2, 2, 2, 2)

scala> val l = List(6,3,5,5,8)
l: List[Int] = List(6, 3, 5, 5, 8)

scala> l.indices map(i=>l diff Seq(l(i))min)
res2: scala.collection.immutable.IndexedSeq[Int] = Vector(3, 5, 3, 3, 3)

scala> val l = List(7,1)
l: List[Int] = List(7, 1)

scala> l.indices map(i=>l diff Seq(l(i))min)
res3: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 7)

scala> val l = List(9,9)
l: List[Int] = List(9, 9)

scala> l.indices map(i=>l diff Seq(l(i))min)
res4: scala.collection.immutable.IndexedSeq[Int] = Vector(9, 9)

scala> val l = List(9,8,9)
l: List[Int] = List(9, 8, 9)

scala> l.indices map(i=>l diff Seq(l(i))min)
res5: scala.collection.immutable.IndexedSeq[Int] = Vector(8, 9, 8)

Cela peut probablement encore être joué au golf, je ne pouvais pas trouver un moyen plus court pour supprimer un élément d'une liste que l diff Seq(l(i))

therealfarfetchd
la source
2

C #, 36 octets

i.Select((x,a)=>i.Where((y,b)=>b!=a).Min())

Prend les éléments (i) et recherche la valeur minimale dans les éléments sans l'élément en cours.

C’est un peu triste de constater que d’autres tentatives ne fonctionnent pas, car nous travaillons avec des types primitifs et nous n’avons donc pas de listes avec des références permettant de comparer les éléments.

MetaColon
la source
2

PowerShell , 49 38 octets

-11 octets grâce à mazzy

($a=$args)|%{($c=$a|sort)[$_-eq$c[0]]}

Essayez-le en ligne!

Amélioration de la belle réponse de Sinusoid . Enregistre 10 octets en utilisant une sortie explicite au lieu de construire un tableau. Indexe dans le tableau trié vers le point 0 (c'est-à-dire la plus petite valeur) ou le point 1 si la condition est vraie.

Veskah
la source
1
It's smart. Save more :) Try it online!
mazzy
1
@mazzy Well done. It's obvious now that I see it but I never would've put that together.
Veskah
1
Nice work! Yours is more lovely :)
Sinusoid
1

Perl 5, 43 bytes

sub{@x=sort{$a<=>$b}@_;map$x[$_==$x[0]],@_}

Equivalent to the Python solution. Perl's sort unfortunately has the wrong default for numbers (requiring an explicit comparator), and min isn't built-in, but it almost makes up for it by sub being shorter than lambda, map$_, being shorter than x for x in, and the implicitness of return and args lists.

hobbs
la source
1

Ruby, 30 bytes

For each element, sort the array, remove the current element and grab the first element of the remaining array.

->a{a.map{|e|(a.sort-[e])[0]}}

It's an anonymous function that can be used like this:

f = ->a{a.map{|e|(a.sort-[e])[0]}}
p f[[6, 3, 5, 5, 8]] # => [3, 5, 3, 3, 3]
daniero
la source
1

CJam, 15 bytes

{:S{S:e<=S$=}%}

Essentially a translation of xnor's algorithm into CJam.

This is an unnamed block that takes an array from the stack and leaves the result on the stack.

Explanation:

{
  :S     e# Save in S
  {      e# For X in S:
    S:e< e#   Push Min(S)
    =    e#   X == Min(S)
    S$=  e#   Sorted(S)[top of stack]
  }%     e# End
}
Esolanging Fruit
la source
1
@LuisMendo Whoops - I forgot to actually sort the array. It should work now.
Esolanging Fruit
1

05AB1E, 5 bytes

{sWQè

Port of @xnor's Python 2 answer.

Try it online or verify all test cases.

Explanation:

{        # Sort the (implicit) input-list
         #  i.e. [4,1,3,6] → [1,3,4,6]
 s       # Swap, so the (implicit) input-list is at the top of the stack again
  W      # Get the minimum without popping from the list
         #  i.e. [4,1,3,6] → 1
   Q     # Check for each element if they are equal to this value (1/0 as truthy/falsey)
         #  i.e. [4,1,3,6] and 1 → [0,1,0,0]
    è    # Use these 0s and 1s to index in the sorted list
         #  i.e. [1,3,4,6] and [0,1,0,0] → [1,3,1,1]
Kevin Cruijssen
la source
1

Java 8, 119 bytes

a->{int t[]=a.clone(),m=a[0],i=a.length;for(int x:a)m=x<m?x:m;for(java.util.Arrays.sort(t);i-->0;)a[i]=t[a[i]==m?1:0];}

Port of @xnor's Python 2 answer.

Modifies the input-array instead of returning a new one to save bytes.

Try it online.

Explanation:

a->{                  // Method with integer-array parameter and no return-type
  int t[]=a.clone(),  //  Make a copy of the input-array
      m=a[0],         //  Minimum `m`, starting at the first value of the input-array
      i=a.length;     //  Index-integer, starting at the length of the input-array
  for(int x:a)        //  Loop over the input-array
    m=x<m?            //   If the current item is smaller than the current `m`
       x              //    Replace `m` with this value
      :               //   Else:
       m;             //    Leave `m` the same
  for(java.util.Arrays.sort(t);
                      //  Sort the copy we've made of the input-array
      i-->0;)         //  Loop `i` in the range (length, 0]
    a[i]=             //   Modify the item at index `i` of the input-array to:
      t[              //    The item in the sorted array at index:
        a[i]==m?      //     If the current item and the minimum are equal:
         1            //      Use index 1 in the sorted array
        :             //     Else:
         0];}         //      Use index 0 in the sorted array
Kevin Cruijssen
la source
1

APL (Dyalog Extended), 7 bytes

Port of xnor's Python 2 answer. Requires ⎕IO←0:

∧⊇⍨⊢=⌊/

Try it online!

Explanation:

∧⊇⍨⊢=⌊/   Monadic function train
      ⌊/   The minimum element of the input
    ⊢=     Element-wise compare the input to the above
           Results in a boolean vector, let's call it "X"
∧         ⍝ Sort the input
 ⊇⍨      ⍝ Index into sorted input by X
voidhawk
la source
1

Haskell, 76 bytes

This is considerably longer than the earlier Haskell entries, but it's the first that only performs a linear number of comparisons and a linear amount of additional work.

f(x:y)|(z,w)<-x!y=z:w
a![x]=(x,[a])
a!(x:y)|(p,q)<-a#x!y=(x#p,a#p:q)
(#)=min

Try it online!

Explanation

! takes two arguments: a running minimum and a nonempty list. It returns the minimum value in the list and the result of processing the given list using the running minimum.

dfeuer
la source
1

MathGolf, 9 7 bytes

s_╓?m=§

Try it online!

Explanation

Basically a port of Kevin Cruijssen's 05AB1E answer, but I lose 2 bytes thanks to having to do things explicitly.

s         sort(array)
 _        duplicate TOS
  ╓       minimum of two elements, min of list, minimum by filter
   ?      rot3 pops input on top of stack again
    m=    explicit map to check equality
      §   get from sorted array for each
maxb
la source