Erstellen Sie eine Funktion oder ein Programm mit zwei Eingaben:

• Eine Liste von Ganzzahlen, die sortiert werden sollen (weniger als 20 Elemente)
• Eine positive Ganzzahl, die Nangibt, wie viele Vergleiche Sie durchführen sollten

Die Funktion soll anhalten und die resultierende Liste von ganzen Zahlen nach NVergleichen ausgeben . Wenn die Liste vor dem NVergleichen vollständig sortiert ist, sollte die sortierte Liste ausgegeben werden.

Der Bubble-Sortier- Algorithmus ist allgemein bekannt, und ich denke, die meisten Leute kennen ihn. Der folgende Pseudocode und die Animation (beide aus dem verlinkten Wikipedia-Artikel) sollten die notwendigen Details enthalten:

procedure bubbleSort( A : list of sortable items )
   n = length(A)
   repeat 
     swapped = false
     for i = 1 to n-1 inclusive do
       /* if this pair is out of order */
       if A[i-1] > A[i] then    
         /* swap them and remember something changed */
         swap( A[i-1], A[i] )
         swapped = true
       end if
     end for
   until not swapped
end procedure

Die Animation unten zeigt den Fortschritt:

Ein Beispiel (direkt aus dem verknüpften Wikipedia-Artikel entnommen) zeigt die Schritte beim Sortieren der Liste ( 5 1 4 2 8 ):

Erster Pass

1: ( 5 1 4 2 8 ) ->  ( 1 5 4 2 8 ) // Here, algorithm compares the first two elements, 
                                   // and swaps since 5 > 1.
2: ( 1 5 4 2 8 ) ->  ( 1 4 5 2 8 ) // Swap since 5 > 4
3: ( 1 4 5 2 8 ) ->  ( 1 4 2 5 8 ) // Swap since 5 > 2
4: ( 1 4 2 5 8 ) ->  ( 1 4 2 5 8 ) // Now, since these elements are already in order 
                                   // (8 > 5), algorithm does not swap them.

Zweiter Durchgang

5: ( 1 4 2 5 8 ) ->  ( 1 4 2 5 8 )
6: ( 1 4 2 5 8 ) ->  ( 1 2 4 5 8 ) // Swap since 4 > 2
7: ( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )
8: ( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )

Das Array ist jetzt bereits sortiert, der Algorithmus weiß jedoch nicht, ob es vollständig ist. Der Algorithmus benötigt einen ganzen Durchgang ohne Austausch, um zu wissen, dass er sortiert ist.

Dritter Durchgang

9: ( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )
10:( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )
11:( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )
12:( 1 2 4 5 8 ) ->  ( 1 2 4 5 8 )

Testfälle:

Format: Number of comparisons (N): List after N comparisons

Input list:
5  1  4  2  8
Test cases: 
1: 1  5  4  2  8
2: 1  4  5  2  8
3: 1  4  2  5  8
4: 1  4  2  5  8
5: 1  4  2  5  8
6: 1  2  4  5  8
10: 1  2  4  5  8
14: 1  2  4  5  8

Input list:
0: 15  18  -6  18   9  -7  -1   7  19  19  -5  20  19   5  15  -5   3  18  14  19
Test cases:
1: 15  18  -6  18   9  -7  -1   7  19  19  -5  20  19   5  15  -5   3  18  14  19
21: -6  15  18   9  -7  -1   7  18  19  -5  19  19   5  15  -5   3  18  14  19  20
41: -6   9  -7  15  -1   7  18  18  -5  19  19   5  15  -5   3  18  14  19  19  20
60: -6  -7  -1   9   7  15  18  -5  18  19   5  15  -5   3  18  14  19  19  19  20
61: -6  -7  -1   7   9  15  18  -5  18  19   5  15  -5   3  18  14  19  19  19  20
81: -7  -6  -1   7   9  15  -5  18  18   5  15  -5   3  18  14  19  19  19  19  20
119: -7  -6  -1  -5   7   9  15   5  15  -5   3  18  14  18  18  19  19  19  19  20
120: -7  -6  -1  -5   7   9  15   5  15  -5   3  18  14  18  18  19  19  19  19  20
121: -7  -6  -1  -5   7   9   5  15  15  -5   3  18  14  18  18  19  19  19  19  20
122: -7  -6  -1  -5   7   9   5  15  15  -5   3  18  14  18  18  19  19  19  19  20
123: -7  -6  -1  -5   7   9   5  15  -5  15   3  18  14  18  18  19  19  19  19  20
201: -7  -6  -5  -1  -5   3   5   7   9  14  15  15  18  18  18  19  19  19  19  20
221: -7  -6  -5  -5  -1   3   5   7   9  14  15  15  18  18  18  19  19  19  19  20

• Ja, integrierte Algorithmen für die Blasensortierung sind zulässig.
• Nein, Sie können nicht nur positive Ganzzahlen oder eindeutige Ganzzahlen annehmen.
• Die Sortierung muss in der oben beschriebenen Reihenfolge erfolgen. Sie können nicht am Ende der Liste beginnen

Gelee , 25 Bytes

ḣ©ṫ-Ṣ®ṖṖ¤;;ṫḊ¥
JḊṁ¹³W¤;ç/

Basierend auf meiner Antwort in J.

Probieren Sie es online!

Überprüfen Sie die Anzahl der Vergleiche.

Erläuterung

Der Hilfslink ändert die Liste am Index, [i-1, i]indem er sie sortiert, wodurch dasselbe Ergebnis wie beim Vergleich der Blasensortierung erzielt wird.

ḣ©ṫ-Ṣ®ṖṖ¤;;ṫḊ¥  Helper link - Input: list A, index i
ḣ               Take the first i values
 ©              Save a copy of it
  ṫ-            Take the last two values
    Ṣ           Sort them
         ;      Append them to
     ®            Get the copy
      ṖṖ¤         Pop the last two values (Ṗ is pop)
          ;     Prepend it to
           ṫ      Take the last i values
            Ḋ¥    Dequeue - remove the head

JḊṁ¹³W¤;ç/  Input: list A and # of comparisons n
J           Enumerate the indices of A
 Ḋ          Dequeue - remove the head
  ṁ         Reshape it cyclically to length n
   ¹        Identity function (Just to avoid parsing rules)
       ;    Append it to
    ³         The list A
     W¤       Wrap it as an array
        ç/  Reduce from left to right using the helper link and return

JavaScript (ES6), 102 82 80 86 80 Byte

Fehlerbehebung und 1 Byte gespeichert dank @ edc65

(a,m)=>eval("for(i=0;m;a[j=i-1]>(b=a[i])?a[a[i]=a[j],j]=b:0)1/a[++i]?m--:i=0;a")

Rekursion kann nicht sein, ist definitiv nicht wahrscheinlich der beste Ansatz, aber ich bleibe vorerst bei einer Schleife.

Versuch es:

f=(a,m)=>eval("for(i=0;m;a[j=i-1]>(b=a[i])?a[a[i]=a[j],j]=b:0)1/a[++i]?m--:i=0;a")

Enter your numbers:<br>
<input id=A rows=10 value="5 1 4 2 8"><br>
Enter the number of steps:<br>
<input type="number" min=0 id=B rows=10 value="1"><br>
<button onclick="C.innerHTML=f((A.value.match(/-?\d+/g)||[]).map(Number),B.value)">Run</button><br>
<pre id=C></pre>

Haskell, 83 82 81 Bytes

y%x@(a:b:c)=(y++x):(y++[min a b])%(max a b:c)
y%x=[]%(y++x)
[x]!_=[x] 
x!n=[]%x!!n

Anwendungsbeispiel: [5,1,4,2,8] ! 5-> [1,4,2,5,8].

In Funktion % yverfolgt die Elemente, die bisher während des aktuellen Durchlaufs besucht wurden, xsind diejenigen, die noch zu untersuchen sind. aund bsind die nächsten zwei, dh die Kandidaten, die getauscht werden sollen. Wenn wir das Ende der Liste erreicht, beginnen wir von Anfang an : y%x = []%(y++x). Alle Schritte werden in einer Liste gespeichert, in der die Hauptfunktion das ndritte Element auswählt.

Bearbeiten: Vorgängerversionen funktionierten nicht für Einzelelementlisten, zum Glück ist die neue Version noch kürzer.

Python 3, 77 74 Bytes

-3 Bytes dank @Maltysen (Init jin der Deklaration)

lambda l,n,j=0:exec('j*=j<len(l)-1;l[j:j+2]=sorted(l[j:j+2]);j+=1;'*n)or l

Testfälle bei ideone

Verwendet sortedfür jeden Vergleichs- und Tauschvorgang, führt jedoch eine Blasensortierung durch.

Setzt j=0(linker Index), führt dann nVergleiche und Tauschvorgänge benachbarter Listenelemente durch und wird jauf zurückgesetzt, 0wenn dieses Fenster außerhalb der Grenzen liegt.

Der j*=j<len(l)-1Wille multipliziert sich an diesem Punkt jmit False(dh 0), während er sich jedes Mal jmit True(dh 1) multipliziert .

(Es funktioniert auch noch für eine leere Liste.)

PowerShell v2 +, 135 - 129 Byte

param($a,$n)for($s=1;$s){($s=0)..($a.count-2)|%{if($a[$_]-gt$a[$_+1]){$a[$_],$a[$_+1]=$a[$_+1],$a[$_];$s=1}if(!--$n){$a;exit}}}$a

So. Viele. Dollar.

( Saved sechs Bytes zu erkennen , dass diese Herausforderung beinhaltet nicht das „kostenlos“ Optimierung des letzte Element Überspringen (n) bei jedem Durchlauf , da das ist sortiert garantiert und stattdessen läuft durch einen vollständigen Durchlauf jedes Mal. Das bewegte die $a.countin die forSchleife und beseitigte die $zVariable. )

Straight-up-Bubble-Sortierung mit einem flotten Fleck, die den Tausch in einem Schritt ausführt -
$a[$_],$a[$_+1]=$a[$_+1],$a[$_]

Die Ausgangslogik wird über gehandhabt if(!--$n){$a;exit}

Testfälle

(Das Array wird hier durch Leerzeichen getrennt angezeigt, da das Standard- Ausgabefeldtrennzeichen für die String-Kennzeichnung eines Arrays ein Leerzeichen ist. Die String-Kennzeichnung erfolgt, weil wir mit den Beschriftungen verketten "$_ -> ".)

PS C:\Tools\Scripts\golfing> 1,2,3,4,5,6,10,14|%{"$_ -> "+(.\bubble-sorting-in-progress.ps1 @(5,1,4,2,8) $_)}
1 -> 1 5 4 2 8
2 -> 1 4 5 2 8
3 -> 1 4 2 5 8
4 -> 1 4 2 5 8
5 -> 1 4 2 5 8
6 -> 1 2 4 5 8
10 -> 1 2 4 5 8
14 -> 1 2 4 5 8

PS C:\Tools\Scripts\golfing> 1,21,41,60,61,81,119,120,121,122,123,201,221|%{"$_ -> "+(.\bubble-sorting-in-progress.ps1 @(15,18,-6,18,9,-7,-1,7,19,19,-5,20,19,5,15,-5,3,18,14,19) $_)}
1 -> 15 18 -6 18 9 -7 -1 7 19 19 -5 20 19 5 15 -5 3 18 14 19
21 -> -6 15 18 9 -7 -1 7 18 19 -5 19 19 5 15 -5 3 18 14 19 20
41 -> -6 9 -7 15 -1 7 18 18 -5 19 19 5 15 -5 3 18 14 19 19 20
60 -> -6 -7 -1 9 7 15 18 -5 18 19 5 15 -5 3 18 14 19 19 19 20
61 -> -6 -7 -1 7 9 15 18 -5 18 19 5 15 -5 3 18 14 19 19 19 20
81 -> -7 -6 -1 7 9 15 -5 18 18 5 15 -5 3 18 14 19 19 19 19 20
119 -> -7 -6 -1 -5 7 9 15 5 15 -5 3 18 14 18 18 19 19 19 19 20
120 -> -7 -6 -1 -5 7 9 15 5 15 -5 3 18 14 18 18 19 19 19 19 20
121 -> -7 -6 -1 -5 7 9 5 15 15 -5 3 18 14 18 18 19 19 19 19 20
122 -> -7 -6 -1 -5 7 9 5 15 15 -5 3 18 14 18 18 19 19 19 19 20
123 -> -7 -6 -1 -5 7 9 5 15 -5 15 3 18 14 18 18 19 19 19 19 20
201 -> -7 -6 -5 -1 -5 3 5 7 9 14 15 15 18 18 18 19 19 19 19 20
221 -> -7 -6 -5 -5 -1 3 5 7 9 14 15 15 18 18 18 19 19 19 19 20

R, 132 131 112 136 Bytes

Das Programm empfängt die Eingabe wie folgt: Zuerst Nder Vektor selbst. Wenn Sie zum Beispiel wollen v = [5 1 4 2 8]und n = 1, den Eingang, der geht in scanist 1 5 1 4 2 8. Um dieses Programm auszuführen, führen Sie die erste Zeile aus , geben die Zahlen nacheinander in die Konsole ein und führen dann den Rest aus (dies ist eine REPL-Antwort).

Dann macht der folgende Code den Trick:

v=scan()
s=m=0
while(!s){s=T;for(i in 3:length(v)){m=m+1
if(m>v[1]){s=T;break}
if(v[i-1]>v[i]){v[c(i-1,i)]=v[c(i,i-1)];s=F}}}
cat(v[-1])

Prüfung:

Input: a vector with N first and the elements to be sorted next
1 5 1 4 2 8
5 5 1 4 2 8
14 5 1 4 2 8
60 15 18 -6 18  9 -7 -1  7 19 19 -5 20 19  5 15 -5  3 18 14 19

Output: 
1 5 4 2 8
1 4 2 5 8
1 2 4 5 8
-6 -7 -1  9  7 15 18 -5 18 19  5 15 -5  3 18 14 19 19 19 20

Update: 1 Byte aufgrund von Vlo golfen .

Pyth, 34 32 Bytes

AQVH=*<ZtlGZ=GsXJcG,Zh=hZ1ShtJ;G

Eine Übersetzung von Jonathan Allans Python-Antwort.

Probieren Sie es hier aus!

JavaScript (ES6), 82 80 79 Byte

f=(a,m,n=0,_,b=a[n+1])=>1/b?m?f(a,m-1,n+1,a[n]>b?a[a[n+1]=a[n],n]=b:0):a:f(a,m)

Basiert auf der ursprünglichen Antwort von @ ETHproduction. Bearbeiten: 2 Bytes dank @ JonathanAllan gespeichert. 1 Byte dank @ edc65 gespeichert.

J , 62 60 Bytes

>@([:({.,(2/:~@{.}.),]}.~2+[)&.>/]|.@;<:@#@]<@|i.@[)^:(]1<#)

Dies ist ein Verb, das zwei Argumente akzeptiert: die Anzahl der Vergleiche in der LHS und die Liste der Ganzzahlen in der RHS. Zuerst wird geprüft, ob die Länge der Liste größer als eins ist. Ist dies nicht der Fall, wird die Liste unverändert zurückgegeben. Andernfalls wird die angegebene Anzahl von Vergleichen ausgeführt, bevor das Ergebnis zurückgegeben wird.

Verwendung

Für den ersten Testfall werden Extras-Befehle verwendet, um mehrere Ein- / Ausgaben zu formatieren. Der zweite Testfall wird als einzelne Ein- / Ausgabe dargestellt.

   f =: >@([:({.,(2/:~@{.}.),]}.~2+[)&.>/]|.@;<:@#@]<@|i.@[)^:(]1<#)
   1 2 3 4 5 6 10 14 ([;f)"0 1 ] 5 1 4 2 8
┌──┬─────────┐
│1 │1 5 4 2 8│
├──┼─────────┤
│2 │1 4 5 2 8│
├──┼─────────┤
│3 │1 4 2 5 8│
├──┼─────────┤
│4 │1 4 2 5 8│
├──┼─────────┤
│5 │1 4 2 5 8│
├──┼─────────┤
│6 │1 2 4 5 8│
├──┼─────────┤
│10│1 2 4 5 8│
├──┼─────────┤
│14│1 2 4 5 8│
└──┴─────────┘
   1 f 15 18 _6 18 9 _7 _1 7 19 19 _5 20 19 5 15 _5 3 18 14 19
15 18 _6 18 9 _7 _1 7 19 19 _5 20 19 5 15 _5 3 18 14 19
   123 f 15 18 _6 18 9 _7 _1 7 19 19 _5 20 19 5 15 _5 3 18 14 19
_7 _6 _1 _5 7 9 5 15 _5 15 3 18 14 18 18 19 19 19 19 20
   221 f 15 18 _6 18 9 _7 _1 7 19 19 _5 20 19 5 15 _5 3 18 14 19
_7 _6 _5 _5 _1 3 5 7 9 14 15 15 18 18 18 19 19 19 19 20

Erläuterung

Es ist schwierig, in J einen knappen Code zu schreiben, der die Veränderbarkeit nutzt. Stattdessen konvertiere ich das Problem in das Reduzieren einer Liste für eine Reihe von Angaben. Ich denke, dieser Code ist chaotisch, also werde ich den Job jeder Phrase anstelle jedes Primitivs durcharbeiten. Der erste Teil erfasst die Länge der Liste und erzeugt einen Bereich. Bearbeiten Sie dann jedes Infix der Größe 2, um einen Durchgang von Vergleichen zu emulieren.

   i. # 5 1 4 2 8
0 1 2 3 4
   2 <\ i. # 5 1 4 2 8
┌───┬───┬───┬───┐
│0 1│1 2│2 3│3 4│
└───┴───┴───┴───┘
   2 <@{.\ i. # 5 1 4 2 8
┌─┬─┬─┬─┐
│0│1│2│3│
└─┴─┴─┴─┘

Dies sind die Startindikatoren für jeden Vergleich. Wenn 7 Vergleiche durchgeführt werden, formen Sie es neu, um die gewünschte Menge zu erhalten. J parst von rechts nach links, so dass es von rechts nach links verkleinert wird, wie rechts falten. Hänge die ursprüngliche Liste an und kehre sie um.

   7 $ 2 <@{.\ i. # 5 1 4 2 8
┌─┬─┬─┬─┬─┬─┬─┐
│0│1│2│3│0│1│2│
└─┴─┴─┴─┴─┴─┴─┘
   |. 5 1 4 2 8 ; 7 $ 2 <@{.\ i. # 5 1 4 2 8
┌─┬─┬─┬─┬─┬─┬─┬─────────┐
│2│1│0│3│2│1│0│5 1 4 2 8│
└─┴─┴─┴─┴─┴─┴─┴─────────┘

Alternativ kann der Bereich [0, 7) erstellt und jeder Wert modulo der Länge der Liste minus 1 entnommen werden, um den gleichen Bereich zu erstellen.

   (<: # 5 1 4 2 8) <@| i. 7
┌─┬─┬─┬─┬─┬─┬─┐
│0│1│2│3│0│1│2│
└─┴─┴─┴─┴─┴─┴─┘

Der letzte Teil ist ein Verb, das eine Liste in der RHS und einen Index in der LHS aufnimmt, der den Startindex des Vergleichs markiert. Wählen Sie die beiden Elemente aus, die an diesem Index beginnen, sortieren Sie sie, fügen Sie sie wieder in die Liste ein und geben Sie sie zurück.

   > ({.,(2/:~@{.}.),]}.~2+[)&.>/ |. 5 1 4 2 8 ; 7 $ 2 <@{.\ i. # 5 1 4 2 8
1 2 4 5 8

Matlab, 93 91 Bytes

function l=f(l,m)
n=numel(l)-1;i=0;while n&m;i=mod(i,n)+1;m=m-1;l(i:i+1)=sort(l(i:i+1));end

Spart 11 Bytes durch Weglassen if l(i)>l(i+1);l(i:i+1)=l([i+1,i])und sortiert stattdessen jedes Mal die beiden Elemente. Funktioniert für Listen mit der Länge 1. Mit dem Octave- m--Operator könnten ein oder zwei Bytes gespeichert werden, aber das ist nicht viel.

Spart durch Setzen zwei weitere Bytes n=numel(l)-1;, weil ich dann einfach while nstatt while n>1und i=mod(i,n)+1statt machen kann i=mod(i,n-1)+1.

Diese Antwort wurde viele Stunden nach dem Erstellen der Herausforderung geschrieben.

Groovy (101 Bytes)

{l,n->(l.size()..0).each{i->(0..i-2).each{if(l[it]>l[it+1] && n>0 && it>-1){l.swap(it,it+1)};n--}};l}

BEARBEITEN: Ich musste keinen eigenen Swap-Verschluss schreiben, groovy hat diesen eingebaut.
Versuchen Sie es hier: https://groovyconsole.appspot.com/script/5104724189642752

Beispiel für einen Ausgabe-Trace:

4:[1, 5, 4, 2, 8]
3:[1, 4, 5, 2, 8]
2:[1, 4, 2, 5, 8]
1:[1, 4, 2, 5, 8]
0:[1, 4, 2, 5, 8] - Locks in the final answer.
-1:[1, 4, 2, 5, 8]
-2 (Return):[1, 4, 2, 5, 8]

Alte Implementierung (122 Bytes)

m={l,n->s={x,y->t=l[x];l[x]=l[y];l[y]=t};((l.size()-2)..2).each{i->(0..i).each{if(l[it]>l[it+1] && n){s(it,it+1)};n--}};l}

Versuchen Sie es hier: https://groovyconsole.appspot.com/script/6316871066320896

PHP, 148 145 Bytes

<?php for($i=2,$a=$argv;$a[1]--;$i=$i==count($a)-2?2:$i+1)if($a[$i]>$a[$i+1])list($a[$i],$a[$i+1])=[$a[$i+1],$a[$i]];echo substr(join(' ',$a),5);

Ich bin nicht sehr zufrieden mit der Schleifenstruktur, aber ich mag den Listenwechsel und er funktioniert, also poste ich ihn trotzdem. php7.1 würde mir erlauben, mindestens 4 Bytes zu speichern.

Mit schönerer Formatierung:

<?php 
for($i=2,$a=$argv;$a[1]--;$i=$i==count($a)-2?2:$i+1)
  if($a[$i]>$a[$i+1])
    list($a[$i],$a[$i+1])=[$a[$i+1],$a[$i]];
echo substr(join(' ',$a),5);

Edit: Jörg Hülsermann hat mich an Join erinnert, anstatt zu implodieren.
Hinweis: Muss sich in einer Datei mit einem einzelnen Dateinamen befinden.

Ruby, 52 50 Bytes

Warten Sie ... kein Rubin?

->l,n{n.times{|a|l[s=a%~-l.size,2]=l[s,2].sort};l}