Ich brauche ein Programm, in dem der Benutzer ein Array von Doubles eingibt und das Programm das Array sortiert ausgibt

280

Hinweis: Diese Frage wurde stark bearbeitet, seit ich sie zum ersten Mal hier gepostet habe. Die Regeln wurden hierher verschoben . Lesen Sie sie, bevor Sie eine Antwort veröffentlichen, um den Zweck zu verstehen. Dies war die erste Frage, die in der Kategorie .

Stellen Sie sich einen faulen Benutzer bei Stack Overflow vor, der diese Frage stellt:

Ich brauche ein Programm, in dem der Benutzer ein Array von Doubles eingibt und das Programm das Array sortiert ausgibt. Könnten Sie bitte den Code angeben?

Wie können Sie einen Code erstellen, der diesen Benutzer trollt? Erstellen Sie einen Code, der für einen unerfahrenen Programmierer nützlich erscheint, in der Praxis jedoch völlig unbrauchbar ist.

Der Gewinner ist die am besten bewertete Antwort, es sei denn, die Antwort ist aus irgendeinem Grund nicht geeignet (Informationen zu den Teilnahmebedingungen finden Sie in der Beschreibung des im Tag-Wiki ). Wenn die zuvor am häufigsten gewählte Antwort in Zukunft in Bezug auf die Anzahl der Stimmen nach dem Akzeptieren geschlagen wird, wird die neue beste Antwort akzeptiert und die vorherige Antwort wird nicht akzeptiert. Im Falle eines Unentschieden wähle ich den Gewinner nach Belieben aus den Unentschieden aus oder warte einfach ein bisschen länger.

Antworten ohne Code sind nicht zulässig. Sie mögen Spaß machen und ein paar Gegenstimmen bekommen, aber sie werden nicht akzeptiert.

Regeln finden Sie unter Tag-Beschreibung .

Hinweis: Dies ist eine Frage. Bitte nehmen Sie die Frage und / oder die Antworten nicht ernst. Mehr Infos hier .

Victor Stafusa
quelle
48
Stack Oversort
ThiefMaster
6
@bluesm Wenn jemand bereits beschlossen hat, einen anderen zu bitten, sein Problem zu lösen, anstatt seine eigene Lernzeit zu verschwenden, hilft es nicht, einen Link zu veröffentlichen, über den er selbst lernen kann.
IQAndreas
3
Wow, diese Frage wird in weniger als 24 Stunden 100 Upvotes und 10.000 Views erhalten!
Joe Z.
18
Meine Güte, Victor, deine About-Box ist so traurig ... wir haben alle unsere Höhen und Tiefen, aber du solltest dich nicht verprügeln, Mann. Sie sind jetzt überall ein Held für Code-Golfer!
SimonT
4
Ich bin überrascht , niemand hat eine Lösung auf Basis angeboten Art Schlaf noch
Frank Farmer

Antworten:

178

Manchmal hilft die Gemeinde hier nicht gerne bei den Hausaufgaben. Deshalb bekommen Sie so viele Scherzantworten. Aber ich helfe gerne. Hier ist eine vollständige Lösung in 'C' (da ich davon ausgehe, dass Sie "Programmieren" lernen möchten, nicht "Skripten" mit Java oder Ruby). Ich habe viele Tipps beigefügt, von denen ich mir wünschte, ich hätte sie gewusst, als ich zum ersten Mal lernte

#include <stdio.h>

//Always use meaningful names for types
typedef unsigned char boolean;
#define True 't'
#define FALSE (!True)

//this is a really neat trick for swapping values efficiently
void swap(long* a,long *b) { *a=*a^*b;*b=*b^*a;*a=*a^*b; }

//Here's a readability improvement
#define until(condition) while(!(condition))

int main(int n, char*args[]){
  double *d;
  int i;
  char input[5];  //should be long enough for most doubles.
  boolean sorted = FALSE;

  //In C, you need to specify the array size beforehand, so ask
  printf("Please enter the length of the array\n");
  gets(input);
  //scan the input string and convert to a value
  sscanf(input,"%s",&input[0]);
  n=(long)atol(input);

  //allocate space, make sure you get the order of arguments right.
  d = calloc(sizeof(double),n); 

  //Get and sort the array
  until (sorted) {

     for (i=0;i<n;i++) {
        //It's important to always ask nicely
        printf("Please enter the %d%s array item\n",i,i==1?"st":"th");
        scanf("%lf",d+i);
     }
     //do a compare and exchange sort:
     sorted = !sorted;  //not sorted
     //check all the items
     printf("%d %d\n",i,n);
     for (i=1;i<n;i++) {
        //compare
        if (d[i]<d[i-1]) {
          //exchange 
          swap(d+i,d+i-1);
          sorted = FALSE;
        }
     }
     //show results
     printf("The array is%ssorted\n",sorted?" ":" not "); }
  //use the --> "downto operator" for counting downto 0. 
  for (;n-->0;) printf("%lf\n",*d++);
  }
Ahelly
quelle
32
Fast alle Ratschläge sind falsch und es wird einfach so lange nach der Eingabeliste gefragt, bis Sie sie bereits sortiert eingeben.
AShelly
47
+1, für 1st, 2th, 3th, 4th...und für den Downto-Operator - sehr fortschrittliche C-Programmiertechniken.
Kaya
5
Sollte verwendet werden sscanf(input, "%5s", &input[0]), da es sonst zu Überlauffehlern beim Parsen der Eingabe kommen kann. Die Eingabe sollte deklariert werden char input[sizeof(int)+1], um die Abwärtskompatibilität mit 64-Bit-Systemen zu gewährleisten.
sh1
12
i==1?"st":"th"hahaha ...
Guy Sirton
15
Java hat Speicherbereinigung. Daher ist Java für "Scripting", keine echte Programmierung. Das ist die grundlegende CS101. (so sagt der Troll.)
AShelly
181

Hier ist es in Java. Es ist ein völliger Betrug, inakzeptabel und unfixierbar, da es eine MySQL-Datenbank erstellt, die Nummer dort einfügt, eine Auswahl mit einer ORDER BY-Klausel vornimmt und die von MySQL angegebenen Nummern ausgibt. Tatsächlich ist es MySQL, das die Sortierung durchführt, nicht das Programm.

package sorter;

import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.util.ArrayList;
import java.util.List;
import javax.swing.JOptionPane;

public class SortingAlgorithm {

    private static final String CREATE_DB = "CREATE DATABASE sorting";
    private static final String DROP_DB = "DROP DATABASE sorting";
    private static final String CREATE_TABLE = "CREATE TABLE sorting.sorting ( num double not null )";

    public static void main(String[] args) throws Exception {
        Class.forName("com.mysql.jdbc.Driver");
        List<Double> doubles = new ArrayList<>(50);
        String typed;
        do {
            typed = JOptionPane.showInputDialog(null, "Type a double:");
            if (typed != null) doubles.add(Double.parseDouble(typed));
        } while (typed != null);

        List<Double> sorted = new ArrayList<>(50);

        try (Connection con = DriverManager.getConnection("jdbc:mysql://localhost:3306", "root", "root")) {
            try (PreparedStatement ps = con.prepareStatement(CREATE_DB)) {
                ps.executeUpdate();
            }
            try (PreparedStatement ps = con.prepareStatement(CREATE_TABLE)) {
                ps.executeUpdate();
            }

            for (Double d : doubles) {
                try (PreparedStatement ps = con.prepareStatement("INSERT INTO sorting.sorting (num) VALUES (" + d + ")")) {
                    ps.executeUpdate();
                }
            }

            try (
                    PreparedStatement ps = con.prepareStatement("SELECT * FROM sorting.sorting ORDER BY num");
                    ResultSet rs = ps.executeQuery())
            {
                while (rs.next()) {
                    sorted.add(rs.getDouble("num"));
                }
            }
            try (PreparedStatement ps = con.prepareStatement(DROP_DB)) {
                ps.executeUpdate();
            }
        }

        JOptionPane.showMessageDialog(null, "The array sorted is: " + sorted);
    }
}
Victor Stafusa
quelle
103
Das ist eigentlich ein bisschen zu nah dran an der Heimat, als dass viele Java-Codierer eine akzeptable Übereinstimmung der Lösung mit der Spezifikation in Betracht ziehen würden !!
Dr. Rebmu
10
Denken Sie auch an den Fall, dass Sie eine sehr große Anzahl von Objekten sortieren müssen. Das Sortieren "außerhalb des Programms" in einer Datenbank ist eine praktikable Lösung.
Viktor Seifert
40
Nicht genug Abstraktion hier. Sie benötigen mindestens 10 Schnittstellen, 20 Implementierungen, Enums, Unit-Tests, Coverage-Tests, Maven, Integrationstests, Mocks ...
Naftuli Kay
6
@NaftuliTzviKay Wir sollten eine MySQLSortEnterpriseEdition erstellen, um Ihre Idee umzusetzen. Wird Victor der GPL-Lizenz für den Code zustimmen, damit wir loslegen können?
Joe Z.
14
@JoeZ. Ja, meiner Antwort fehlen Kommentare zum Lizenzmodell, und ich sollte den Benutzer zu Beginn des Programms dazu bringen, eine EULA zu akzeptieren. Da ich es jedoch dem Lazy OP übergebe, ist es für den nichtkommerziellen Gebrauch kostenlos, einschließlich der Erstellung der lang erwarteten Premium-MySQLSortEnterpriseEdidtion.
Victor Stafusa
142

Es gibt keinen Kill wie Overkill

Zuallererst, lieber GiMmEtHaCoDeZ, versuchen wir, Ihre Aufgabe aufzuschlüsseln:

  1. Lesen Sie die Zahlen
  2. Sortieren Sie sie
  3. Ausgabe der sortierten Nummern.

Da "Teilen und Erobern" eine sehr wichtige Strategie bei der Arbeit mit Softwareproblemen ist, können Sie diese nacheinander angehen

1. Lesen

Ein weiteres wichtiges Thema in der Software ist die Vielseitigkeit. Da nicht festgelegt ist, wie der Benutzer die Zahlen eingibt, kann dies über die Konsole, über eine Datei, über einen Webdienst usw. geschehen. Daher ist es wichtig, dass unsere Lösung verschiedene Eingabetypen unterstützt. Der einfachste Weg, dies zu erreichen, besteht darin, den wichtigen Teil einer Schnittstelle zu extrahieren

public interface IDoubleArrayReader
{
  IEnumerable<double> GetDoubles();

  DoubleArrayReaderType Type {get;}
}

Wo DoubleArrayReaderTypeist eine Aufzählung gegeben mit

public enum DoubleArrayReaderType
{
  Console,
  File,
  Database,
  Internet,
  Cloud,
  MockService
}

Es ist auch wichtig, die Software von Grund auf testbar zu machen, damit eine Implementierung der Schnittstelle möglich ist

public class MockServiceDoubleArrayReader : IDoubleArrayReader
{
    IEnumerable<double> IDoubleArrayReader.GetDoubles()
    {
      Random r = new Random();  
      for(int i =0; i<=10; i++)
      {
        yield return r.NextDouble();
      }
    }

    DoubleArrayReaderType IDoubleArrayReader.Type 
    {
      get
      {
        return DoubleArrayReaderType.MockService;
      }
    }
}

Als nächstes ist die logische Frage, wie wir das entsprechende IDoubleArrayReaderin den Code laden können . Das ist einfach, solange wir eine einfache Fabrik benutzen:

public static class DoubleArrayInputOutputFactory
{
  private static Dictionary<DoubleArrayReaderType, IDoubleArrayReader> readers;

  static DoubleArrayInputOutputFactory()
  {
      readers = new Dictionary<DoubleArrayReaderType, IDoubleArrayReader>();
      foreach (Type type in Assembly.GetExecutingAssembly().GetTypes())
      {
        try
        {
          var instance = Activator.CreateInstance(type);
          if (instance is IDoubleArrayReader)
          {
            readers.Add((instance as IDoubleArrayReader).Type, 
                        (instance as IDoubleArrayReader));
          }
        }
        catch
        {
          continue;
        }
      }
  }

  public static IDoubleArrayReader CreateDoubleArrayReader(DoubleArrayReaderType type)
  {
    return readers[type];
  }
}

Beachten Sie, dass wir Reflection verwenden, um alle aktiven Reader zu laden, sodass zukünftige Erweiterungen automatisch verfügbar sind. Im Hauptteil unseres Codes tun wir Folgendes:

IDoubleArrayReader reader = DoubleArrayInputOutputFactory
                           .CreateDoubleArrayReader(DoubleArrayReaderType.MockService);
var doubles = reader.GetDoubles();

2. Bearbeitung (Sortierung)

Nun müssen wir die erhaltenen Zahlen verarbeiten, dh sortieren. Beachten Sie, dass die Schritte völlig unabhängig voneinander sind, sodass es für das Sortiersubsystem unerheblich ist, wie die Zahlen eingegeben wurden. Darüber hinaus kann sich das Sortierverhalten ändern, z. B. müssen wir möglicherweise einen effizienteren Sortieralgorithmus eingeben. Daher extrahieren wir natürlich das angeforderte Verarbeitungsverhalten in einer Schnittstelle:

public interface IDoubleArrayProcessor
{
  IEnumerable<double> ProcessDoubles(IEnumerable<double> input);

  DoubleArrayProcessorType Type {get;}
}

public enum DoubleArrayProcessorType
{
  Sorter,
  Doubler,
  Tripler,
  Quadrupler,
  Squarer
}

Und das Sortierverhalten implementiert nur die Schnittstelle:

public class SorterDoubleArrayProcessor : IDoubleArrayProcessor
{
    IEnumerable<double> IDoubleArrayProcessor.ProcessDoubles(IEnumerable<double> input)
    {
      var output = input.ToArray();
      Array.Sort(output);
      return output;
    }

    DoubleArrayProcessorType IDoubleArrayProcessor.Type 
    {
      get
      {
        return DoubleArrayProcessorType.Sorter;
      }
    }
}

Natürlich benötigen wir eine Factory, um die Verarbeitungsinstanzen zu laden und zu verwalten.

public static class DoubleArrayProcessorFactory
{
  private static Dictionary<DoubleArrayProcessorType, IDoubleArrayProcessor> processors;

  static DoubleArrayProcessorFactory()
  {
      processors = new Dictionary<DoubleArrayProcessorType, IDoubleArrayProcessor>();
      foreach (Type type in Assembly.GetExecutingAssembly().GetTypes())
      {
        try
        {
          var instance = Activator.CreateInstance(type);
          if (instance is IDoubleArrayProcessor)
          {
            processors.Add((instance as IDoubleArrayProcessor).Type, (instance as IDoubleArrayProcessor));
          }
        }
        catch
        {
          continue;
        }
      }
  }

  public static IDoubleArrayProcessor CreateDoubleArrayProcessor(DoubleArrayProcessorType type)
  {
    return processors[type];
  }

}

3. Schreiben Sie die Ausgabe

Hier gibt es nicht viel zu sagen, da dies ein Prozess ist, der die Eingabe widerspiegelt. Tatsächlich könnten wir die Lese- und Schreibfabriken in einer einzigen kombinieren DoubleArrayInputOutputFactory:

public interface IDoubleArrayWriter
{
  void WriteDoublesArray(IEnumerable<double> doubles);

  DoubleArrayWriterType Type {get;}
}

public enum DoubleArrayWriterType
{
  Console,
  File,
  Internet,
  Cloud,
  MockService,
  Database
}

public class ConsoleDoubleArrayWriter : IDoubleArrayWriter
{
    void IDoubleArrayWriter.WriteDoublesArray(IEnumerable<double> doubles)
    {
      foreach(double @double in doubles)
      {
        Console.WriteLine(@double);
      }
    }

    DoubleArrayWriterType IDoubleArrayWriter.Type 
    {
      get
      {
        return DoubleArrayWriterType.Console;
      }
    }
}


public static class DoubleArrayInputOutputFactory
{
  private static Dictionary<DoubleArrayReaderType, IDoubleArrayReader> readers;
  private static Dictionary<DoubleArrayWriterType, IDoubleArrayWriter> writers;

  static DoubleArrayInputOutputFactory()
  {
      readers = new Dictionary<DoubleArrayReaderType, IDoubleArrayReader>();
      writers = new Dictionary<DoubleArrayWriterType, IDoubleArrayWriter>();
      foreach (Type type in Assembly.GetExecutingAssembly().GetTypes())
      {
        try
        {
          var instance = Activator.CreateInstance(type);
          if (instance is IDoubleArrayReader)
          {
            readers.Add((instance as IDoubleArrayReader).Type, (instance as IDoubleArrayReader));
          }
        }
        catch
        {
          continue;
        }
      }

      foreach (Type type in Assembly.GetExecutingAssembly().GetTypes())
      {
        try
        {
          var instance = Activator.CreateInstance(type);
          if (instance is IDoubleArrayWriter)
          {
            writers.Add((instance as IDoubleArrayWriter).Type, (instance as IDoubleArrayWriter));
          }
        }
        catch
        {
          continue;
        }
      }

  }

  public static IDoubleArrayReader CreateDoubleArrayReader(DoubleArrayReaderType type)
  {
    return readers[type];
  }

  public static IDoubleArrayWriter CreateDoubleArrayWriter(DoubleArrayWriterType type)
  {
    return writers[type];
  }

}

Alles zusammen

Schließlich wird unser Hauptprogramm nur all diese beeindruckenden Eigenschaften nutzen, die wir bereits erstellt haben. Der Code wird also einfach sein:

var doubles = reader.GetDoubles();
doubles = processor.ProcessDoubles(doubles);
writer.WriteDoublesArray(doubles);

wo, zum Beispiel könnten wir definieren reader, writerund processormit

IDoubleArrayReader reader = DoubleArrayInputOutputFactory.CreateDoubleArrayReader(DoubleArrayReaderType.MockService);
IDoubleArrayProcessor processor = DoubleArrayProcessorFactory.CreateDoubleArrayProcessor(DoubleArrayProcessorType.Sorter);
IDoubleArrayWriter writer = DoubleArrayInputOutputFactory.CreateDoubleArrayWriter(DoubleArrayWriterType.Console);
SWeko
quelle
49
Lol, ListSort Enterprise Edition © :-P +1
Türklinke
14
+1 für verrücktes Overcoding. Ich schlage vor, dass Sie Ihre Antwort in 3 oder mehr "Modul" -Antworten
aufteilen
15
Und das Schöne daran ist, dass es tatsächlich eine Bibliothekssorte verwendet :) Es entspricht voll und ganz der Spezifikation und ist völlig nutzlos
SWeko
9
Das war schön.
Andrew
7
Die Verwendung von DI verwirrt nur das OP, da dies nur ein kurzes Beispiel ist.
SWeko
132

Noch wörtlichere Interpretation:

echo " aaehrrty"

das heißt, "das Array" sortiert.

RBerteig
quelle
5
Ich bin hierher gekommen, um das zu posten.
Quuxplusone
5
Als Datei speichern sort.shund anrufen alssh sort.sh "an array of doubles"
Kyss Tao
Ich denke, Sie haben das "der Benutzer gibt ein Array von Doppelten ein" verpasst.
Dukeling
1
@Dukeling das ist der Sinn dessen, was Kyss Tao kommentiert. "an array of doubles"kann als Befehlszeilenargument an das Skript übergeben werden.
AJMansfield
108

Perl

Von all den Dingen, die ich für CodeGolf.SE gemacht habe, hat dies wahrscheinlich die meiste Zeit in Anspruch genommen, zumindest ein paar Stunden.

$_[0]=eval<>;
for(0..$#{$_[0]}**2){
 @_[$#_+1]=[\(@{$_[$#_]}),$#{$_[$#_]}+1];
 for(1..$#{$_[$#_]}-$#_){
  if(eval('${'x$#_.'@{$_[$#_]}[$_-1]'.'}'x$#_)>eval('${'x$#_.'@{$_[$#_]}[$_]'.'}'x$#_)){
   ${$_[$#_]}[$#{$_[$#_]}]=$_;
  }
 }
 (${$_[$#_]}[${$_[$#_]}[$#{$_[$#_]}]-1],${$_[$#_]}[${$_[$#_]}[$#{$_[$#_]}]])=(${$_[$#_]}[${$_[$#_]}[$#{$_[$#_]}]],${$_[$#_]}[${$_[$#_]}[$#{$_[$#_]}]-1]);
}
for(0..~~@{$_[0]}){
 $\.=eval('${'x$#_.'${$_[$#_]}[$_-1]'.'}'x$#_).','
}
$\=~s/,*$//;$\=~s/^,*//;$\="[$\]";
print;

Eingabe ist von der Form [2,4,5,7,7,3]und Ausgabe ist von der Form [2,3,4,5,7,7].

Ich habe jetzt keine Zeit zu erklären ... komme später wieder.

Jedenfalls gibt es in Perl so etwas wie ein anonymes Array. Es ist ein Array, aber es hat keinen Namen. Was wir jedoch wissen, ist eine Referenz (Speicherstelle), die darauf verweist. Eine Reihe von Zahlen in eckigen Klammern erstellt ein anonymes Array und gibt einen Verweis darauf zurück.

Diese Antwort basiert auf einer Reihe anonymer Arrays, in denen Verweise gespeichert sind @_. Die Eingabe wird in ein anonymes Array umgewandelt. Anschließend erstellen wir andere anonyme Arrays, von denen jedes Element auf ein Element im vorherigen Array verweist. Anstatt die Elemente im Array zu sortieren, sortieren wir die Zeiger auf die Elemente in diesem Array. Außerdem erstellen wir ein neues Array für jeden Schritt (und mehr) in der Sortieroperation.

PhiNotPi
quelle
3
böse! böse! böse!
DGM
56
Etwa so gut zu entziffern wie jedes andere Perl-Skript für mich :)
Corey Goldberg
6
@swelljoe Ist $_an dieser Stelle eigentlich eine leere Zeichenfolge. Ich habe meine gewünschte Ausgabe in gespeichert $\ , dem Trennzeichen für Ausgabedatensätze.
PhiNotPi
4
@Andy einfach. "Wie funktioniert es?"
John Dvorak
1
und alle vom Benutzer erstellten Variablen haben hübsche Namen, die allen denkbaren Konventionen folgen
Hagen von Eitzen,
80

Python

Gibt dem Benutzer ein sortiertes Array, indem alle nicht sortierten Elemente aus dem Eingabearray entfernt werden.

import sys

sorted = []
for number in map(float, sys.stdin.read().split()):
    if not sorted or number >= sorted[-1]:
         sorted.append(number)
print sorted 

Der Algorithmus geht die Liste nur durch und fügt jedes Element hinzu, wenn die Liste dadurch nicht unsortiert wird. Die Ausgabe ist also eine sortierte Liste, nur keine, die alle Elemente der ursprünglichen Liste enthält. Wenn der op nur prüft, ob die Liste in sortierter Reihenfolge ist, bemerkt er möglicherweise nicht, dass in der Ausgabe Werte fehlen.

Winston Ewert
quelle
1
Bitte sehen Sie sich andere Antworten an, bevor Sie Ihre eigenen veröffentlichen. Sie sollten den Namen Ihrer Sprache hinzufügen. Um diese Frage zu beantworten, müssen Sie auch kurz erklären, was Sie tun, um das OP zu überwachen.
Wasi
5
Hehe, das hat mich tatsächlich zum Lachen gebracht. Auf jeden Fall stimme ich zu, dass eine etwas bessere Erklärung hilfreich wäre.
oconnor0
2
Handelt es sich bei dem Doppelruf um sys.stdin.read()einen Tippfehler oder um einen Teil der echten Trolling-Antwort? Sicherlich würde es das OP frustrieren, das Array als Eingabe zu geben und weiterhin auf das Ergebnis zu warten ...
Bakuriu
Wow, das ist schon böse.
Sylverdrag
13
Ein O(n)Sortieralgorithmus. Nett.
2.
65

Bash, 54 Zeichen

Viele Antworten in langsamen, ineffizienten Sprachen wie C und Python ... lassen Sie uns die Sache etwas beschleunigen, indem wir eine Lösung für alle Skriptsprachen anbieten: Bash.

Ich weiß, was Sie denken - Bash kann nicht einmal mit Fließkomma-Arithmetik umgehen, also wie wird es sortiert, richtig? Nun, siehe, meine Implementierung des mächtigen SleepSort-Algorithmus:

#!/bin/bash

for i in $@; do echo -n $(sleep $i)$i' '& done
echo "Leveraging the power of your $(grep -c ^processor /proc/cpuinfo) cores to \
sort optimally by spawning $(jobs -l | wc -l) concurrent sorting threads..."
wait
echo -e "\nThe array sorted."

Das Programm erhält Eingaben als Kommandozeilenargumente. Probelauf:

> ./sleepsort.sh 7 1 4 3 2.752 6.9 0.01 0.02
Leveraging the power of your 4 cores to optimally by spawning 8 concurrent sorting threads...
0.01 0.02 1 2.752 3 4 6.9 7
The array sorted.

Dies hat auch den Vorteil, dass es vielleicht der kürzeste aller hier vorgestellten Arbeitsalgorithmen ist. Das ist richtig - eine mächtige Bash-Zeile , die nur Bash-Builtins verwendet und keine externen Binärdateien aufruft (das heißt, wenn Sie die rein optionale ausführliche Ausgabe nicht mitzählen). Im Gegensatz zu den Bogosorten ist die Laufzeit deterministisch.

Tipp: Eine effektive Optimierung besteht darin, die eingegebenen Zahlen vor dem Sortieren durch einen Faktor zu teilen. Die Umsetzung bleibt dem Leser überlassen.

Bearbeiten:

Verkürzte 54-Zeichen-Golfversion mit weniger hübschem Druck:

#!/bin/sh
for i in $@;do echo $(sleep $i)$i&done;wait
Randalieren
quelle
11
Trolling 1: Der Algorithmus funktioniert, ist aber möglicherweise sehr langsam - er erzeugt einen Thread für jede Nummer und schläft für diese Anzahl von Sekunden, bevor er die Nummer ausgibt (was also in Ordnung ist). Trolling 2: Außerdem wird der größte Teil des Codes für das Schreiben eines netten Kommentars über die Anzahl der Threads aufgewendet. Außerdem werden die CPU-Informationen des Systems unnötigerweise und unentgeltlich gelesen und analysiert, um eine zusätzliche ausführliche Ausgabe zu ermöglichen. Trolling 3: Am Ende wird "das Array sortiert" ausgegeben, was anscheinend erledigt ist. Trolling 4: Der Benutzer kann die "Sortierung" nicht abbrechen, indem er Strg-C drückt.
Aufstand
4
5. Es funktioniert nur unter GNU / Linux , aufgrund der Verwendung von /proc/cpuinfo.
kps11346
5
Äußerst kreative Lösung, übrigens :)
Dmitry
8
Das ist großartig. Ich kann nicht einmal ausdrücken, wie großartig das ist. Ich denke darüber nach, das aktiv zu nutzen, weil WARUM NICHT.
4
Ich habe tatsächlich irgendwo eine Variante davon in der Produktion im Einsatz. Aber in dieser Situation ist die Laufzeit des Prozesses wichtig, das ist meine Entschuldigung ...
Aufruhr
64

JavaScript hat eine eingebaute sort()Funktion, die Sie folgendermaßen verwenden können:

var numbers = [6, 2.7, 8];
numbers.sort();
// => [2.7, 6, 8]

... oh, ganz vergessen zu erwähnen, es sortiert in lexikographischer Reihenfolge, dh 10 < 9und 9 < -100. Wahrscheinlich ist es das, was Sie sowieso erwarten.

Alexey Lebedev
quelle
8
Das ist sogar noch besser, weil es eine eingebaute Funktion ist.
Wayne Werner
62

(jPL) jQuery-Programmiersprache

Sie müssen dafür jQuery verwenden. Eine einfache Lösung für dieses Problem ist die folgende:

function jSort() {
    var a = 0.0; // position 1
    var b = 0.0; // position 2
    var c = 0.0; // position 3

    var arr = [];
    var nArr = [];

    // don't forget to validate our array!
    if (window.prompt("You must only type double values. Type 1 if you accept the terms.") != 1) {
        alert("You can't do that.");
        return;
    }

    for (var i = 0; i < 3; i++) {
        if (i == 0) {
            var a = window.prompt("Type a double value");
            arr.push(a);
        }
        if (i == 1) {
            var b = window.prompt("Type a double value");
            arr.push(b);
        }
        if (i == 2) {
            var c = window.prompt("Type a double value");
            arr.push(c);
        }
    }

    // Now the tricky part
    var b1 = false;
    var b2 = false;
    var b3 = false;
    for (var i = 0 ; i < 3; i++) {
        // check if the variable value is the same value of the same variable which now is inside the array
        if (i == 0) {
            if (a == arr[i]) {
                b1 = true;
            }
        }

        if (i == 1) {
            if (b == arr[i]) {
                b2 = true;
            }
        }

        if (i == 2) {
            if (c == arr[i]) {
                b3 = true;
            }
        }
    }

    if (b1 == true && b2 == true && b3 == true) {
        if (arr[0] > arr[1]) {
            if (arr[0] > arr[2]) {
                nArr.push(arr[0]);
            } else {
                nArr.push(arr[2]);
            }
        }

        if (arr[1] > arr[0]) {
            if (arr[1] > arr[2]) {
                nArr.push(arr[1]);
            }
            else {
                nArr.push(arr[2]);
            }
        }

        if (arr[2] > arr[0]) {
            if (arr[2] > arr[1]) {
                nArr.push(arr[2]);
            } else {
                nArr.push(arr[1]);
            }
        }

        console.log(arr.sort(function (a, b) { return a - b }));
        alert(arr.sort(function (a, b) { return a - b }));
    }
}

jSort();
Felipe Miosso
quelle
55
Besonders gefällt mir , wie dies nicht wirklich jQuery verwenden.
KRyan
8
-1 Ihre Array-Benennung muss die ungarische Notation enthalten, insbesondere jQuery-Objekte, die mit $, Arrays mit aund Ergebnisse von window.promptas gekennzeichnet sind p.
Qantas 94 Heavy
2
Der "knifflige Teil" ist elegant. OP, bemühen Sie sich, eines Tages eine solche Codestruktur zu haben.
Chris Barker
2
Das F'n Doble "Validierung" LOOOOOOOOOOOOL omg omg Tag gemacht! bearbeitet für weniger
Großbuchstaben
54

C

Diese Lösung kombiniert die Prägnanz und den Zugriff auf Betriebssystemebene von C mit den leistungsstarken, wiederverwendbaren Softwarekomponenten in GNU / Linux:

#include <stdlib.h>

main(int argc, char **argv)
{
    system("echo Enter numbers one per line, ending with ctrl-D; sort -g");
}
Mark Plotnick
quelle
4
Oder ein „Drehbuch“: #!/usr/bin/sort.
Mechanische Schnecke
54

Rubin

print "Input an array of doubles: "
gets
puts "the array sorted."

Ziemlich selbsterklärend.

Oder erfordern, dass die Eingabe tatsächlich "ein Array von Doubles" ist:

print "Input an array of doubles: "
g = gets until /an array of doubles\n/
puts "the array sorted."

Nicht gets.chompfür zusätzliches Übel verwenden. Auch mit Regex nach dem Schleppen bis, was ich nicht einmal wusste, dass Sie tun können (danke Jan Dvorak), um OP noch mehr zu verwirren!

Türknauf
quelle
4
Um die Idee zu erweitern, würde ich wiederholt um Eingabe bitten, bis der Benutzer die Zeichenfolge eingibt an array of doubles.
Wrzlprmft
@Wrz Ok, fertig :-)
Türklinke
2
Das ist besonders großartig, weil der arme OP herausfinden muss, wie er einen Zeilenvorschub loswerden kann (weil Sie ihn getsanstelle von verwenden gets.chomp).
Wchargin
@WChargin Yep, ich hatte das in der ersten Revision (siehe Revisionsverlauf), entfernte es aber, um noch böser zu werden>: D EDIT: Oh warte, egal, das war meine andere Antwort. Ich bearbeite das hier :-)
Türklinke
1
+1 Ich habe hier ein Konto erstellt, um nur zu sagen, genau so würde ich es beantworten! Liebe es!
DGM
44

Python3.3

Sicher, hier ist das einfachste Python-Programm, das ein Array sortieren kann, das als Listenliteral auf stdin angegeben ist:

collections = __import__(dir(object.__subclasses__()[7])[1][4:-3] + chr(116))

URL = ('https://www.google.com/search?client=ubuntu&channel=fs&q=dante+alighieri'
      '%27s+divina+commedia&ie=utf-8&oe=utf-8#channel=fs&q=__++divina+commedia+'
      'dante+alighieri+inferno+__').translate(
          dict.fromkeys(map(ord, '+-.:,;bcdefghjklopqrstuvwxyz/&=#?%')))[30:]
SECRET_KEY = URL[2:10][::-1][3:-1]
DATA = '{}{}{}'.format(URL[:2], SECRET_KEY[:2] + SECRET_KEY[:-3:-1], URL[-2:])



if getattr(DATA, dir(list)[7])(__name__):
    pieces = 'literally - evil'.split(' - ')
    r = getattr(collections, 
                '_'.join([pieces[0][:-2],
                          pieces[1].translate({ord('j')-1: 'a'})])
                )((getattr(globals()['__{}__'.format('buildings'.translate(
                        {100:'t', 103:None}))], 'in' r"put"))
                  ())
    tuple((lambda lst:
           (yield from map(list,
                           map(lambda k: (yield from k), 
                               ((lambda i: (yield from map(lambda t:
                                             (lst.append(lst[i]) or
                                              lst.__setitem__(i, lst[t]) or
                                              lst.__setitem__(t, lst.pop())),
                                              (j for j in range(i)
                                                if (lambda: lst[i] < lst[j])())
                                              ))
                                )(è) for è in range(
                                                getattr(lst,
                                                        dir(lst)[19])()))))
          )
        )(r))
    print(r)

Leider funktioniert es nur in python3.3 +, da es den yield fromAusdruck verwendet. Der Code sollte selbsterklärend sein, sodass Sie keine Probleme haben sollten, wenn Sie ihn Ihrem Professor übergeben.


Das Trolling besteht darin, eine perfekt funktionierende Lösung bereitzustellen, die genau das tut, was das OP beabsichtigt hat, aber auf eine Art und Weise, die:

  • unmöglich zu verstehen (für Anfänger)
  • Es ist unmöglich, sich an den Lehrer zu wenden, weil:
    • das OP kann es nicht verstehen
    • selbst wenn er könnte, hätte der Lehrer keine Zeit zum Entschlüsseln, um es zu verstehen
  • beängstigend für einen naiven Neuling, der denken könnte, dass ihm das Programmieren zu schwer fällt

Zusammenfassend lässt sich sagen, dass diese Antwort die Frustration des Schülers über die Verspottung seiner Anfragen mit unter bestimmten Gesichtspunkten zutreffenden Antworten erheblich erhöhen würde.


(Lesen Sie nicht, wenn Sie eine Herausforderung in Betracht ziehen, den obigen Code zu verstehen.)

Ich muss hinzufügen, dass das Trolling auch durch die Tatsache erhöht wird, dass der implementierte Sortieralgorithmus tatsächlich ist

Blasensortierung! ... was sicherlich so umgesetzt werden könnte, dass auch das OP es verstehen könnte. Es ist kein obskurer Algorithmus an sich, nur eine gute Code-Verschleierung von etwas, das das OP sonst perfekt verstehen könnte.

Bakuriu
quelle
3
Ich denke, das könnte mehr Erklärung gebrauchen. Was machst du jetzt mit dem Inferno ?
KRyan
1
Wow, Sie können nicht-ASCII-Variablennamen in Python tun? wusste nicht ...
kratenko
1
@kratenko Von python3 +. In python2 geht der Interpreter von ASCII als Codierung aus und hätte einen Fehler ausgelöst. In python3 geht der Interpreter von UTF-8 als Codierung aus und akzeptiert alle Zeichen, die nach Unicode-Eigenschaften "Buchstaben" sind, für Bezeichner.
Bakuriu
3
@KRyan: Er wendet offensichtlich die Sortiermethode an, mit der die Hölle die Leute in die neun Kreise bringt.
Joe Z.
10
Oh meine Güte ... +1 für è.
Sean Allred
41

C - Langsamer, schwer zu verwendender, inakzeptabler Codierungsstil

Der Sortieralgorithmus selbst ist als langsame Sortierung bekannt und weist eine Best-Case-Komplexität (Einfachheit) von etwa n ^ (log n / 2) auf . Der Algorithmus wurde von Andrei Broder und Jorge Stolfi in ihrem großartigen Aufsatz "Pessimal Algorithms and Simplexity Analysis" veröffentlicht, den ich für gute Lacher und Denkanstöße sehr empfehle.

void sort(double* arr, int n, int i, int j)
{
        if(i < j) {
                int m = (i+j)/2;
                sort(arr, n, i  , m);
                sort(arr, n, m+1, n);
                if(arr[m] > arr[j]) {
                        double t = arr[j];
                        arr[j] = arr[m];
                        arr[m] = t;
                }
                sort(arr, n, i, j-1);
        }
}

Die Sortierung selbst ist jedoch unbrauchbar. Daher benötigen wir eine Möglichkeit für den Benutzer, die Daten einzugeben, die sortiert werden sollen. Das Parsen von Doubles ist schmerzhaft. Warum also nicht byteweise eingeben?

const unsigned MAX_ELEMS = 100;
int main()
{
        int i=0, j=0, len;
        char a[MAX_ELEMS*8];
        double* arr = (double*) a;
        short isNull=1;

        while(1) {
                a[i++] = getchar();
                if(i%8 == 0) {
                        if(isNull)
                                break;
                        isNull = 1;
                }
                else if(a[i-1] != 0)
                        isNull = 0;
        }

        len=i/8 - 1;

        sort(arr, len-1, 0, len-1);

        for(i = 0; i < len; i++)
        {
                printf("%f ", arr[i]);
        }
}

Um zu beweisen, dass es funktioniert:

 $ gcc -g trollsort.c -o trollsort
trollsort.c: In function ‘main’:
trollsort.c:43:3: warning: incompatible implicit declaration of built-in function ‘printf’
 $ echo -en "\0\0\0\0\0\xe4\x94\x40\0\0\0\0\0\0\xf0\x3f\0\0\0\0\0\0\x45\x40\0\0\0\0\0\0\0\0" | ./trollsort
1.000000 42.000000 1337.000000

Am Ende haben wir:

  • Der langsamste deterministische Sortieralgorithmus, den ich kenne
  • Stille, hartcodierte Begrenzung der Listenlänge
  • Absolut schreckliche Eingabe, ich könnte die Ausgabe auch ähnlich machen, aber ich denke, dass es auf diese Weise lustiger ist.
    • Bedenken Sie: Sie müssen wissen, welche Endianess Ihr Computer das Programm verwenden soll.
    • Sie können auch keine 0 eingeben (-0 ist ok)
  • Zeigerarithmetik und so gut wie keine Bedeutung für Typen, da Zeiger auf jede Weise umgewandelt werden
Shiona
quelle
Dies hat undefiniertes Verhalten für alle Eingaben, die größer als 7 Byte sind. Keine akzeptable Antwort.
Michael Spencer
1
Ich liebe das Papier "Pessimal Algorithms". Vielen Dank.
Ryan
"Der langsamste deterministische Sortieralgorithmus, den ich kenne" - der nachweislich langsamste deterministische Sortieralgorithmus. Das ist der springende Punkt der Zeitung, AFAIR.
Konrad Rudolph
@MichaelSpencer Pflege zu erarbeiten? Ich habe ein Beispiel mit einer Eingabegröße von 24 Byte angegeben und die Ausgabe entspricht den Erwartungen (ich glaube, hier fehlt mir ein Witz).
Shiona
2
@Sasho, aber eine Schein-Sortierung hat im besten Fall eine Laufzeit von \ Omega (n) (n-1 Vergleiche, 0 Operationen). Das geht viel schneller, oder? schlimmer als \ Omega (n ^ (log n / 2)).
Shiona
39

Rubin, böser Bogosort! (Bonus: Bogosort durch Benutzereingabe)

print "Input array of doubles, separated by commas: "
arr = gets.split(",")
arr.shuffle! until arr.each_cons(2).all? {|x| x[0] < x[1]}
puts arr * ","

Die "bösen" Wendungen:

  • Läuft natürlich wirklich sehr, sehr, sehr, sehr, sehr langsam
  • Verwendet den Zeichenkettenvergleich, also ist 10 kleiner als 2. Kann einfach mit .map &:to_fan die zweite Zeile angehängt behoben werden , aber OP weiß das möglicherweise nicht
  • chompWenn die letzte Nummer nicht verwendet wird , wird am Ende eine mysteriöse Zeile eingefügt
  • stripWird diese Option nicht verwendet , werden Zahlen mit einem mysteriösen Leerzeichen um Kommas herum eingegeben (z. B. das Leerzeichen in 1.5, 2).

Oder wie wäre es mit einer Fehlsortierung durch Benutzereingaben ?! >: D

print "Input array of doubles, separated by commas: "
arr = gets.split(",")
arr.shuffle! until arr.each_cons(2).all? {|x|
    print "Is #{x[0]} less than #{x[1]}? (y/n) "
    gets =~ /y/
}
puts arr * ","
Türknauf
quelle
Warum nicht Bogobogosort ? (
Läuft
@Wchargin Ich kann es in Betracht ziehen :-) Vielleicht interessiert dich meine letzte Bearbeitung! (Entschuldigung, dass ich langsam bin, ich bin gerade auf meinem Handy, da ich nicht auf einen Computer zugreifen kann :-P)
Türklinke
37

COBOL

Sicher! "Sogar ein Affe kann das!"

Hier ist ein einfaches COBOL-Programm , das die Eingabe für Sie sortiert. Lesen Sie die Kommentare, um genau zu sehen, wie trivial und erweiterbar es ist. Die wirklichen Vorteile davon sind, dass es sich um einen bewährten Mechanismus handelt, der nicht auf neuen und relativ ungetesteten Sprachen wie Java und irgendetwas Web-basiertem oder von Microsoft basiert. Es lässt sich sehr effektiv kompilieren und Verfahren wie dieses werden von den erfolgreichsten Finanzunternehmen der Fortune500 und anderen Branchenführern eingesetzt. Dieser Code wurde von vielen Experten überprüft und gilt als ausgezeichneter Sortiermechanismus.

000100 IDENTIFICATION DIVISION.
000200* Cobol sort. Consistent with COBOL 390
000300* does not use sections; does not use go to
000400* uses sort procedures
000500* does a sort with some minimal input validation
000600* since everything is done in an orderly way,
000700* you can easily add code of your own to this program
000800 PROGRAM-ID. 'SORTEX1'.
000900 ENVIRONMENT DIVISION.
001000 CONFIGURATION SECTION.
001100 INPUT-OUTPUT SECTION.
001200 FILE-CONTROL.
001300*    INPUT FILE UNSORTED
001400     SELECT UNSORTED-FILE ASSIGN UNSORTED.
001500*    The work file for the sort utility
001600*    you need the select and an sd but do not need jcl for it
001700     SELECT SORT-WORK      ASSIGN      SORTWORK.
001800*    output file normally a disk/tape file
001900*    for this program, send it to the printer
002000     SELECT SORTED-FILE ASSIGN SORTED.
002100*
002200 DATA DIVISION.
002300 FILE SECTION.
002400*
002500 FD  UNSORTED-FILE
002600     RECORDING MODE IS F
002900     RECORD CONTAINS  80 CHARACTERS.
003000
003100 01  UNSORTED-RECORD.
003200     05  WS-UR-ACCT-NO        PIC X(5).
003300     05  FILLER               PIC X(5).
003400     05  WS-UR-AMOUNT         PIC 9(5).
003500     05  WS-UR-CUST-NAME      PIC X(10).
003600     05  FILLER               PIC X(5).
003700     05  WS-UR-TRANS-CODE     PIC X(1).
003800     05  FILLER               PIC X(49).
003900
004000  SD  SORT-WORK
004400      RECORD CONTAINS  80 CHARACTERS.
004500*
004600 01  SORT-WORK-RECORD.
004700*    You need a definition and picture for
004800*    the field that is sorted on (sort key)
004900     05  SW-ACCT-NO    PIC X(05).
005000*    YOU NEED A FILLER TO COMPLETE THE DEFINITION
005100     05  FILLER        PIC X(75).
005200*
005300 FD  SORTED-FILE
005400     RECORDING MODE IS F
005700     RECORD CONTAINS  80 CHARACTERS.
005800*
005900 01  SORTED-RECORD.
006000     05  WS-SR-ACCT-NO        PIC X(05).
006100     05  FILLER               PIC X(05).
006200     05  WS-SR-AMOUNT         PIC 9(05).
006300     05  WS-SR-CUST-NAME      PIC X(10).
006400     05  FILLER               PIC X(55).
006500
006600 WORKING-STORAGE SECTION.
006700 01  SWITCHES.
006800     05  UNSORTED-FILE-AT-END      PIC X   VALUE 'N'.
006900     05  SORT-WORK-AT-END          PIC X   VALUE 'N'.
007000     05  valid-sw                  PIC X   VALUE 'N'.
007100
007200 01  COUNTERS.
007300      05 RELEASED-COUNTER PIC S9(7)
007400                PACKED-DECIMAL VALUE +0.
007500      05 REJECT-COUNTER   PIC S9(7)
007600                PACKED-DECIMAL VALUE +0.
007700
007800 PROCEDURE DIVISION.
007900     PERFORM INITIALIZATION
008000*    Compare this logic to that of the simple program
008100*    notice how the sort verb replaces the
008200*    perform main until end of file etc
008300     SORT SORT-work ASCENDING KEY SW-ACCT-NO
008400         INPUT PROCEDURE SORT-INPUT
008500         OUTPUT PROCEDURE SORT-OUTPUT
008600     PERFORM      TERMINATION
008700     GOBACK.
008800
008900 INITIALIZATION.
009000*    Do what you normally do in initialization
009100*    open the regular input file (not the sort work file)
009200*    and other files needed
009300*    (you could open them in the sort input procedure, too)
009400     OPEN INPUT UNSORTED-FILE
009500          output SORTED-FILE
009600*    READ THE FIRST RECORD ON THE REGULAR INPUT FILE
009700     PERFORM READ-IT.
009800*    Whatever else you do in initialization
009900*    headers, initialize counters, etc
010000
010100 TERMINATION.
010200*    Do what you normally do in termination
010300*    print out total lines
010400*    close the files you opened
010500*    display totals
010600     CLOSE UNSORTED-FILE
010700           SORTED-FILE.
010800
010900 READ-IT.
011000     READ UNSORTED-FILE
011100     AT END MOVE 'Y' TO UNSORTED-FILE-AT-END
011200     END-READ.
011300
011400 SORT-INPUT.
011500*    This is the 'sort input procedure'
011600*    when control passes thru the last statement in it
011700*    the input phase of the sort is finished
011800*    and actual sorting takes place
011900     PERFORM SORT-INPUT-PROCESS-ALL
012000        UNTIL UNSORTED-FILE-AT-END = 'Y'.
012100
012200  SORT-INPUT-PROCESS-ALL.
012300*  This is the point when you have each unsorted input record
012400*  in your hands
012500*  many programs do some validation or selection here
012600*  to determine which records are actually given to the sort util
012700*  we will do some simple validation here
012800     MOVE 'Y' TO VALID-SW
012900     PERFORM SORT-INPUT-VALIDATE
013000     IF VALID-SW = 'Y'
013100     THEN
013200**       Give the unsorted input record to the sort utility
013300         RELEASE SORT-work-RECord FROM unsorted-RECORD
013400         ADD 1 TO RELEASED-COUNTER
013500     ELSE
013600**       Here, you have decided not to give the unsorted input
013700**       record to the sort utility
013800         ADD 1 TO REJECT-COUNTER
013900     END-IF
014000     PERFORM READ-IT.
014100
014200 SORT-INPUT-VALIDATE.
014300*    Check the regular input record for validity.
014400*    if it is not suitable for sorting, set the valid sw
014500*    other validation criteria would apply for other files
014600     IF WS-UR-ACCT-NO IS equal to spaces
014700        THEN MOVE 'N' TO VALID-SW
014800     END-IF.
014900
015000 SORT-OUTPUT.
015100*    This is the 'sort output procedure'
015200*    when control passes thru the last statement in it
015300*    the output phase of the sort is finished
015400*    you have seen (returned) the last sorted record
015500*    and the sort utility is finished
015600     PERFORM RETURN-IT
015700     PERFORM SORT-OUTPUT-PROCESS-ALL
015800         UNTIL SORT-WORK-AT-END = 'Y'.
015900
016000 RETURN-IT.
016100*    Gets each sorted record from the sort utility
016200*    return is logically like a read
016300      RETURN SORT-work
016400         AT END MOVE 'Y' TO SORT-work-AT-END
016500      END-RETURN.
016600
016700 SORT-OUTPUT-PROCESS-ALL.
016800      PERFORM SORT-OUTPUT-PROCESSING
016900      PERFORM RETURN-IT.
017100 SORT-OUTPUT-PROCESSING.
017200* Here you do the things you do in a
017300* regular program's main processing routine
017400* add totals, compute things
017500* write detail records, print lines, etc
017600* you could put control break check here
017700* this program just and writes the record out to "sorted file"
017900     MOVE SORT-WORK-RECORD TO SORTED-RECORD
018100     WRITE SORTED-RECORD.
rolfl
quelle
6
Nur Sie würden COBOL für eine Antwort auf diese Frage verwenden. +1
syb0rg
5
Ah, der frische Duft von Lochkarten
Sklivvz
3
@EbenezerSklivvze - LOL. Ich nahm einmal eine Lochkarte heraus, die ich als Lesezeichen verwendete, als mein Professor am Assembly College der Klasse von alten Lochkarten erzählte. Er hatte genügend Fußboden (es war 1994 :). Denken Sie nicht, dass viele meiner Zeitgenossen jemals ein ganzes Deck gesehen haben ...
DVK
30

OP hat nie gesagt, wie man sie sortiert ... oder was seine Definition von Doppeln ist. Datentyp annehmen, doubleaber als Duplikat interpretieren . Verwenden Sie hier JavaScript.

var arr = [4, 6, 7, 4, 5, 9, 11, 7],
    flag = 1,
    result = [];

while( arr.length ) {
  for( var i = 0, index = 0; i < arr.length; ++i ) {
    if( arr[i] * flag < arr[index] * flag ) {
      console.log(arr[i], arr[index]);
      index = i;
    }
  }
  arr.splice(index, 1);
  flag = -flag;
}

Ergebnis: abwechselnde Reihenfolge [4, 11, 4, 9, 5, 7, 6, 7]

Kiruse
quelle
4
Msgstr "Datentypen doppelt annehmen, aber als Duplikate interpretieren". Nur ein wahres Genie würde so denken. Einfach brilliant!
Felipe Miosso
@ FelipeMiosso Um ehrlich zu sein, ich bin nicht sicher, ob Sie nur sarkastisch sind ...
Kiruse
1
Haha ... ich war sarkastisch. Ich weiß, dass es Leute gibt, die wirklich so denken. Wie auch immer ... Ihre Antwort war episch! Ich lachte viel.
Felipe Miosso
@FelipeMiosso Ich bin froh, dass ich mithelfen konnte, ein Lachen auszulösen. ;)
Kiruse
console.log alles!
Emil Vikström
28

PHP

Hier ist eine vollständige Implementierung mit Fehlerbehandlung. Es ist das schnellste für alle array of doubles.

<?php
  function arraySorter($arr) {
      foreach ($arr as $el) {
          if ($el != 'double') {
              throw new Exception('Unexpected Error: Invalid array!');
          }
      }
      return $arr;
  }

  $arrayOfDoubles = Array('double', 'double', 'double', 'double', 'double');
  var_dump(arraySorter($arrayOfDoubles));
?>
totymedli
quelle
25
do
{
}
while(next_permutation(begin(ar), end(ar)));

Bei der nächsten Permutation in C ++ wird true zurückgegeben, wenn das Array sortiert ist, andernfalls false (nachdem es permutiert hat). Sie sollten also das Array sortieren und es dann in einer Übung wie oben verwenden (damit ein vollständiger Kreis zurück zum sortierten Array entsteht).

user974006
quelle
+1 Ich habe darüber nachgedacht, next_permutationfür meine Antwort zu verwenden, aber das ist viel sauberer, als ich es mir vorgestellt habe.
jliv902
25

[Lösung durch pünktliche Fehlleitung]

Bitte lesen Sie die entsprechende Norm, IEC 60559: 1989 Spezifikation für binäre Gleitkomma-Arithmetik für Mikroprozessorsysteme , die Sie hier erwerben können . In der Fußnote zu §5.10 Details des totalOrder-Prädikats wird Folgendes angegeben:

totalOrder schreibt nicht allen Kodierungen in einem Format eine Gesamtreihenfolge vor. Insbesondere wird nicht zwischen verschiedenen Codierungen derselben Gleitkommadarstellung unterschieden, wenn eine oder beide Codierungen nicht kanonisch sind.

Wir sehen also, dass es unmöglich ist, Code zu schreiben, um Doppelte zu sortieren. Es ist eine Trickfrage. Ha, ha, sehr schlau! Bitte sagen Sie Ihrem Professor, dass ich seinen Kurs sehr genieße.

[edit: nichts setzt voraus, dass ich nicht annehme, dass das Problem eine Gesamtbestellung erfordert]

kps11346
quelle
3
Das Problem war jedoch, die Doppel zu sortieren. Niemand verlangte, dass die Werte in (Gesamt-) Reihenfolge sind. Beispielsweise könnten Sie das Array in zwei positive und negative Zahlen sortieren. Sie wurden von der Frage doppelt angesprochen.
Shiona
23

Ein böses JavaScript:

OP, ich möchte Ihnen nicht alles geben, also überlasse ich Ihnen, wie Sie selbst Eingaben vom Benutzer erhalten (Hinweis: Verwenden prompt).

Sobald Sie das haben, ist hier eine Funktion, in die Sie Ihr Array übergeben können, um es zu sortieren. Sie müssen nur das Array, den niedrigsten Wert im Array und ein Inkrement angeben:

var sortDoubles = function (unsortedArray, minimumVal, increment) {
    var sortedArray = [];

    while (unsortedArray.length != sortedArray.length) {
        var index = unsortedArray.indexOf(minimumVal);
        if (index != -1) {
            sortedArray.push(unsortedArray[index]);
        }

        minimumVal += increment;
    }

    return sortedArray;
};

Hier ist eine kleine Übung, um es anhand der Benutzereingaben [1.5, -3.5, 12, 10, -19.5] in Aktion zu sehen.


Hinweis: Abgesehen davon, dass das vorliegende Problem eine schlechte Leistung, Komplexität und Erweiterbarkeit aufweist, ist dies besonders frustrierend, wenn das OP keine Kenntnisse über Gleitkomma-Mathematik besitzt. Wenn beispielsweise die Benutzereingabe lautet [8.1, 5, -.8, 2.3, 5.6, 17.9]und das OP die einfachen Werte (dh minimumVal=-.8und increment=.1) auswählt , wird das Programm für immer ausgeführt. In diesem Zusammenhang bin ich derzeit der stolze Besitzer von 2 nicht funktionierenden Browser-Registerkarten aufgrund dieses Problems :)

Anmerkung II: Ich fand es ekelhaft, den obigen Code zu schreiben.

Anmerkung III: MWA HAHAHAHA!

Briguy37
quelle
Gute Idee. Sie müssen cool gewesen sein, als Sie noch ein Programmier-Neuling waren.
Pierre Arlaud
22

Hier ist eine tatsächliche Antwort , die ich für Java mag:

Fügen Sie die Zeile vor println hinzu und Ihr Array wird sortiert

Arrays.sort( array );

Keine Erklärung, verwirrt das OP , funktioniert aber und wird von erfahreneren Programmierern positiv bewertet.


Eine andere ähnliche Antwort :

Werfen Sie einen Blick auf Arrays.sort ()

Fordern Sie das OP indirekt auf, seine eigenen Nachforschungen anzustellen, und geben Sie ihm eine vage richtige Antwort. Ohne weitere Nachforschungen ist das OP immer noch verwirrt . Mir gefällt auch, dass der Link auf ältere Dokumentationen verweist.

syb0rg
quelle
10
Dies ist nützlich und daher einer Abwahl wert.
Emory
11
"Indirekt den OP auffordern, seine eigenen Nachforschungen anzustellen und ihm dabei eine vage richtige Antwort zu geben", beschreibt ziemlich genau meinen Stil der StackOverflow-Beantwortung: /
Corey Goldberg,
7
"Werfen Sie einen Blick auf Arrays.sort ()" ... "Könnte ich ein Beispiel für die Verwendung in meinem Programm erhalten?" ... brillant.
SimonT
5
+1 vor allem, weil unser bescheidener OP wahrscheinlich eine Sortierung für eine Klasse selbst schreiben muss, was Array.sort () für ihn / sie völlig unbrauchbar macht.
Kevin
2
Strg + F -> "Kann ich ein Beispiel für die Verwendung in meinem Programm erhalten?" = 3 Ergebnisse.
Qix
21

Genetischer Algorithmus / Monte-Carlo-Methode für das Sortierproblem in JAVA

Das Sortierproblem ist der Informatik seit langem bekannt und es wurden viele gute Lösungen gefunden. In den letzten Jahren wurden große Fortschritte im Bereich Biocomputing erzielt, und die Untersuchung, wie die Biologie Probleme löst, hat sich als große Hilfe bei der Lösung schwerer Probleme erwiesen. Dieser Sortieralgorithmus verwendet die besten dieser Ideen, um das Sortierproblem zu lösen. Die Idee ist ziemlich einfach. Sie beginnen mit einem ungeordneten Array und finden heraus, wie sortiert dieses bereits ist. Sie geben ihm eine Bewertung seiner "Sortierbarkeit" und verteilen dann eine zufällige Komponente auf das Array - genau wie in der Biologie, wo es nicht klar ist, wie die Kinder aussehen werden, selbst wenn Sie alles über die Eltern wissen! Dies ist der genetische Algorithmus-Teil. Sie erschaffen sozusagen die Nachkommen dieses Arrays. Dann sehen Sie, ob die Nachkommen besser sortiert sind als die Eltern (auch bekannt als Überleben der Stärkeren!). Wenn dies der Fall ist, fahren Sie mit diesem neuen Array als Ausgangspunkt fort, um die nächste Permutation usw. zu erstellen, bis das Array vollständig sortiert ist. Das Coole an diesem Ansatz ist, dass es kürzer dauert, wenn das Array bereits von Anfang an ein bisschen sortiert ist!

package testing;

import java.awt.List;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Random;

import org.joda.time.DateTime;
import org.joda.time.Interval;


public class MonteCarloSort {
    private static final Random RANDOM  = new Random();


    public static void main(String[] args) {


        List doubleList = new java.awt.List();

        //  prompt the user to enter numbers
        System.out.print("Enter a number or hit return to start sorting them!");


        //  open up standard input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String input = null;

        //  read the numbers from the command-line; need to use try/catch !!!
        do{

            try {
                input = br.readLine();
            } catch (IOException ioe) {
                System.out.println("IO error trying to read a number!");
                System.exit(1);
            }


                try {
                    double d = Double.parseDouble(input);
                    doubleList.add(input);
                } catch (NumberFormatException e) {
                    if (!input.equals("")) System.out.println("Only numbers are allowed.");
                }

        } while (!input.equals(""));



        printCurrentListAndStuff(doubleList);

        while (isAscSorted(doubleList) < doubleList.getItemCount()){
            List newlist = createPermutation(doubleList);

            //genetic algorithm approach!
            if (isAscSorted(doubleList) <= isAscSorted(newlist)){
                //the new list is better, so we use it as starting point for the next iteration!
                doubleList = newlist;
                printCurrentListAndStuff(doubleList);

            }

        }

        System.out.println("done!");
    }

    private static void printCurrentListAndStuff(List doubleList){
        System.out.print("array sortedness is now " + isAscSorted(doubleList) + "(max = "+doubleList.getItemCount()+"): ");
        printList(doubleList);
        System.out.print("\n"); 
    }

    private static void printList(List doubleList){
        for (int i = 0; i < doubleList.getItemCount(); i++){
            String doubleVal = doubleList.getItem(i);
            System.out.print((i>0?", ":"") +doubleVal);
        }   
    }

    private static List createPermutation(List doubleList){
        int sortedness = isAscSorted(doubleList);
        if (sortedness == doubleList.getItemCount()) return doubleList;

        //we take the first non fitting item and exchange it by random
        int swapWith = RANDOM.nextInt(doubleList.getItemCount());

        //it makes no sense to swap with itself, so we exclude this
        while (swapWith == sortedness){
            swapWith = RANDOM.nextInt(doubleList.getItemCount());
        }

        List newList = new List();
        for (int i = 0; i < doubleList.getItemCount(); i++){
            if ( i == sortedness){
                newList.add(doubleList.getItem(swapWith));  
            }
            else if ( i == swapWith){
                newList.add(doubleList.getItem(sortedness));    
            }
            else{
                newList.add(doubleList.getItem(i));
            }

        }
        return newList;

    }

    /**
     * A clever method to get the "degree of sortedness" form a given array. the
     * bigger the number the more sorted it is. The given list is fully sorted if
     * the return value is the length of the list!
     * 
     * @param doubleList
     * @return a number
     */
    private static int isAscSorted(List doubleList){
        double current = Double.NEGATIVE_INFINITY;
        for (int i = 0; i < doubleList.getItemCount(); i++){
            String doubleVal = doubleList.getItem(i);
            if (Double.parseDouble(doubleVal) >= current){
                current = Double.parseDouble(doubleVal);
            }
            else{
                return i;
            }
        }
        return doubleList.getItemCount();
    }

}

Extras

  • Missbrauch von java.awt.List
  • inkonsistente und falsche Variablennamen
  • völlig beschissen bla bla über biocomputing
  • erfinderische und inkonsistente Sprache in der Erklärung
  • monte carlo ist eindeutig das falsche werkzeug für geradlinige deterministische probleme
  • nicht benötigte Importe
  • wahrscheinlich mehr Goodies ...
luksch
quelle
Nennt man diesen GA oder Monte Carlo eine andere Stufe des Trolls? Ich glaube, das ist ein randomisierter Algorithmus zum Bergsteigen.
Shiona
Es war beabsichtigt, dieses Programm mit Schlagwortnamen zu verknüpfen, aber ich habe auch nie von einem "randomisierten Hill-Climbing-Algorithmus" gehört ... und im weiteren Sinne denke ich, dass GA und Monte Carlo nicht allzu weit entfernt sind, um eindeutig falsch zu liegen ...
luksch
19

Python

a = map(float, raw_input().split())
print sorted(a, key=lambda x: int(x * 10**3) % 10 + int(x * 10**5) % 10)

Sortiert die Array (Liste) durch die Summe der 3 rd und 5 th Dezimalstellen.

grc
quelle
5
Leider ist dies trivial behoben, indem alles nachher entfernt lambda x:und durch ersetzt wird x. Trotzdem würde ein Anfänger-Programmierer das nie erfahren, also ein dickes Lob!
Joe Z.
18

C ++

Das funktioniert ... irgendwann.

Hier ist mein Sortieralgorithmus:

template <typename Iterator>
void sort (Iterator first, Iterator last)
{
    while (std::is_sorted (first, last) == false) {
        std::shuffle (first, last, std::random_device()) ;
    }
}

Hier ist das vollständige Programm:

#include <algorithm>
#include <iostream>
#include <random>
#include <string>
#include <sstream>
#include <vector>

namespace professional 
{
    template <typename Iterator>
    void sort (Iterator first, Iterator last) ;

} // end of namespace professional

std::vector <double> get_doubles () ;

int main (void)
{
    std::vector <double> vecVals = get_doubles () ;
    professional::sort (std::begin (vecVals), std::end (vecVals)) ;

    for (const double d : vecVals) {
        std::cout << d << " " ;
    }

    std::cout << std::endl ;

    return 0 ;
}

template <typename Iterator>
void professional::sort (Iterator first, Iterator last)
{
    while (std::is_sorted (first, last) == false) {
        std::shuffle (first, last, std::random_device()) ;
    }
}

std::vector <double> get_doubles ()
{
    std::cout << "Please enter some space delimited doubles." << std::endl ;

    std::vector <double> vecVals ;

    std::string strLine ;
    std::getline (std::cin, strLine) ;

    std::stringstream ss (strLine) ;

    while (1) {
        double d = 0 ;
        ss >> d ;

        if (ss.bad () == false && ss.fail () == false) {
            vecVals.push_back (d) ;
        }

        else {
            break ;
        }
    }

    return vecVals ;
}
jliv902
quelle
6
Deine Art "Algorithmus" hat mich in Tränen aufgelöst.
Nate
Hah, das ist kein Algorithmus, weil es nicht
erlaubt
@joxnas, tatsächlich auf Systemen, auf denen nicht deterministische Zufallsgeräte nicht verfügbar sind, kann der Zufallsgenerator tatsächlich periodisch sein. Dann würde es einfach davon abhängen, ob die Menge der möglichen Permutationen, die der Zufallsgenerator zulässt, die Menge der möglichen Permutationen $ S_n $ für alle möglichen Eingangsarraylängen $ n $ subsummiert.
Fehler
Ohje, ich habe vergessen, dass LaTeX nur von TeX.SE und Math.SE unterstützt wird. Stellen Sie sich diese Symbole in hochnäsigem Italix vor.
Fehler
18

Hier, genieße deine Augen:

<?php
if (isset($_POST["doubleArray"]) === true) {
    $doubleValues = explode(":", $_POST["doubleArray"]);
    if (is_numeric($_POST["smallestDouble"]))
    {
        $sorted = $_POST["sorted"] . ":" . $doubleValues[$_POST["smallestDouble"]];
        unset($doubleValues[$_POST["smallestDouble"]]);
        $doubleValues = array_values($doubleValues);        
    }

    if (count($doubleValues) > 0) {
        $i = 0;
        foreach ($doubleValues as $value) {
            echo $i . " : " . $value . "<br />";
            $i++;
        }
        echo "Type the index of the smallest double value in the list: ";
    } else {
        echo "Sorted values" . $sorted;
    }
}else {
       echo "Enter double values separated by a colon (:)";

}
?>

<form name="form1" method="post" action="<?php echo $_SERVER['PHP_SELF']; ?>" >
<?php
if (!isset($doubleValues)) {
    echo '<input type="text" name="doubleArray" /><br>';
} else {
    echo '<input type="hidden" name="doubleArray" value="' .
    implode(":", $doubleValues) .
    '" ><input type="text" name="smallestDouble" /><br>'.
    '<input type="hidden" name="sorted" value="' . $sorted . '" >';
}
?>
    <input type="submit" value="Submit">
</form>

Dieser Code zeigt das Array an und fordert den Benutzer auf, das kleinste Double des Arrays einzugeben. Anschließend wird die Nummer zur Liste der sortierten Nummern hinzugefügt, das Double aus dem Array entfernt und die verbleibenden Array-Nummern angezeigt.

* Fehlinterpretation: Schwachstelle, aber das OP erwartet nicht genau, dass das Programm den Benutzer auffordert, beim Sortieren zu helfen.

* Schummeln: Der Benutzer ist derjenige, der die eigentliche Sortierung vornimmt.

* Leistung: Für jede Nummer des Arrays ist ein Server-Roundtrip erforderlich, und der Benutzer muss die kleinste Nummer manuell ermitteln. Die Leistung kann nicht viel schlechter werden.

* Inakzeptabel: Ich denke, ich habe das abgedeckt. Und viel Glück bei der Wiederverwendung. Im schlimmsten Fall könnte der Benutzer 90% des Codes loswerden und wiederholt durchlaufen, um die kleinsten Werte zu finden und sie jedes Mal zu entfernen, was ihm einen der am wenigsten effizienten Sortieralgorithmen geben würde.

* Kreativ und böse: du sagst es mir.

Sylverdrag
quelle
2
Du sagst "Schlemmen Sie Ihre Augen" und gibst mir PHP Oo
Aidiakapi
3
"Evil" war Teil der Anforderungen, nicht wahr?
Sylverdrag
17

Javascript Intelligent Design Sort

function sort(array){
    console.log("Someone more intelligent than you has already sorted this optimally. Your puny brain cannot comprehend it");
    return array;//I do believe that this is the fastest sorting algorithm there is!
}
scrblnrd3
quelle
6
Kredit, bei dem Kredit fällig ist: dangermouse.net/esoteric/intelligentdesignsort.html
wchargin
1
Verstehen Sie nicht, warum Sie intelligentes Design in einem Programmierwettbewerb verprügeln?
khebbie
12
@ khebbie Warum nicht?
Konrad Rudolph
Problem ist, wenn der Benutzer derjenige ist, der die Zahlen eingibt, dann wären sie intelligenter als sie selbst. ;)
d -_- b
16

Python - req. # 1

Dieser Code sortiert die Doppelseiten in lexikographischer Reihenfolge, anstatt die numerische Reihenfolge zu erhöhen, indem er einen Präfixbaum von Ziffern erstellt und diese dann rekursiv durchläuft.

class trie_node:
    def __init__(self):    
        self.chn = {}
        self.instances = 0
        for char in "0123456789.-+e":
            self.chn[char] = None
    def insert_number(self, number):
        if(number == ""):
            self.instances += 1
        else:
            self.chn[number[0]] = trie_node()
            self.chn[number[0]].insert_number(number[1:])

def get_sorted_array(node, number):
    array_to_return = [number] * node.instances
    for char in "0123456789.-+e":
        if node.chn[char] != None:
            array_to_return += get_sorted_array(node.chn[char], number + char)
    return array_to_return

def pcg_sort(arr):
    root = trie_node()

    for element in arr:
        root.insert_number(str(element))

    sarr = get_sorted_array(root, "")
    fsarr = []
    for element in sarr:
        fsarr.append(float(element))

    return fsarr

input_array = []

while True:
    number = raw_input("Enter a double (/ to end): ")
    if(number == "/"):
        print pcg_sort(input_array)
        break
    else:
        try:
            number = float(number)
            input_array.append(number)
        except ValueError:
            pass

Es funktioniert n log npünktlich und ist in der Tat eine clevere Möglichkeit, eine sortierte Liste zu führen, aber leider ist es für das OP völlig falsch.

Joe Z.
quelle
4
Es ist auch insofern besonders umständlich, als wenn alle Zahlen die gleiche Anzahl von Stellen vor dem Dezimalpunkt haben, es tatsächlich korrekt funktioniert, so dass das OP möglicherweise nicht einmal bemerkt, dass die Sortierung etwas falsch macht, wenn er es nur mit einer Eingabe von testet , sagen 2, 1, 3, 8, 5.
Joe Z.
14

Sortiert das Array von Doubles. In Java:

public String sort(double[] input){
String s = "";
for(Double d:input){
    s+=Long.toBinaryString(Double.doubleToRawLongBits(d));
}
char[] chars=s.toCharArray();
Arrays.sort(chars);
s="";
for(char c:chars){
    s+=c;
}
return s;}

Zum Beispiel:

[0.0, 1.5, 123]

geht aus der unsortierten binären Darstellung von

011111111111000000000000000000000000000000000000000000000000000100000001011110110000000000000000000000000000000000000000000000

zu den elegant sortierten

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111

planetguy32
quelle
11

Ich brauche ein Programm, in dem der Benutzer ein Array von Doubles eingibt und das Programm das Array sortiert ausgibt. Könnten Sie bitte den Code angeben?

Edit per @kealist, ich denke, es ist besser, wenn kommentiert, um die Kluft plausibel erscheinen zu lassen. In Rebol ...

doubled-list: load ask "Input list of doubles: "

;-- The list is of doubles, so we have to undouble them before sorting
;-- Use MAP-EACH to create a new list with each element divided by two
undoubled-list: map-each num doubled-list [num / 2] 

;-- Note: We could also have sorted before we undoubled the numbers
print sort undoubled-list

Man spielt die Idee ab, dass sie nicht wirklich wissen, was ein Double ist, und könnte glauben, dass eine Liste von Double nur eine Reihe von Zahlen ist, die mit zwei multipliziert werden.

Dr. Rebmu
quelle
6
Möglicherweise müssen sie halbiert werden, da die Eingabe bereits verdoppelt ist!
Kealist
@kealist Ich dachte, dass dies jedoch auf der Idee spielt, dass "verdoppelt" wird. Ich denke, dass es ein bisschen besser ist, die [2 * num] zu haben.
Dr. Rebmu
10

Absichtliches Missverständnis der Frage:

Verwenden eines rekursiven Ansatzes:

def recsort(array):
    "Recursive sort"
    if array:
        for j, i in enumerate(array):
            for l1 in recsort(array[:j]):
                for l2 in recsort(array[j+1:]):
                    yield i + l1 + l2
                    yield i + l2 + l1
    else:
        yield ''

for p in recsort(raw_input("Array:")):
    print p

Das sortierte Array wird garantiert irgendwann ausgegeben, für jeden Datentyp im Array, sogar für jede Sortierreihenfolge und sogar für jede Art von Trennzeichen für die Eingabe, was diesen Ansatz äußerst flexibel macht. Der Hauptnachteil ist, dass es für große Arrays etwas langsam ist, aber Sie können das mit Multithreading leicht lösen.

Valentin CLEMENT
quelle