J'ai besoin d'un programme où l'utilisateur entre un tableau de doubles et le programme affiche le tableau trié

280

Remarque: cette question a été sérieusement modifiée depuis que je l'ai postée pour la première fois ici. Les règles ont été déplacées ici , lisez-les avant de poster toute réponse pour comprendre le but de cette opération. Ce fut la première question créée dans la catégorie .

Imaginez un utilisateur paresseux sur Stack Overflow pose la question suivante:

J'ai besoin d'un programme où l'utilisateur entre un tableau de doubles et le programme sort le tableau trié. Pourriez-vous s'il vous plaît donner le code?

Comment pouvez-vous créer un morceau de code qui va traîner cet utilisateur? Créez un morceau de code qui paraîtra utile pour un programmeur inexpérimenté mais qui est totalement inutile en pratique.

Le gagnant est la réponse la plus votée, sauf si la réponse n’est pas éligible (pour les conditions d’éligibilité, consultez la description de la balise wiki de ). Si la réponse précédemment la plus votée est battue à l'avenir dans le nombre de votes positifs après son acceptation, la nouvelle meilleure réponse est acceptée et la précédente est refusée. En cas d'égalité, je choisirai le vainqueur à volonté parmi ceux à égalité ou j'attendrai un peu plus.

Les réponses sans code ne sont pas éligibles. Ils pourraient être amusants et obtenir des votes positifs, mais ils ne seront pas acceptés.

Les règles peuvent être trouvées à la description de la balise .

Remarque: il s'agit d'une question à la . S'il vous plaît ne prenez pas la question et / ou les réponses au sérieux. Plus d'informations ici .

Victor Stafusa
la source
48
Stack Oversort
ThiefMaster
6
@bluesm Si quelqu'un a déjà décidé de demander à quelqu'un d'autre de résoudre son problème au lieu de «perdre son temps» à apprendre, afficher un lien vers un lieu où ils peuvent apprendre par eux-mêmes ne servira à rien.
IQAndreas
3
Wow, cette question est sur le point d'obtenir 100 votes positifs et 10 000 vues en moins de 24 heures!
Joe Z.
18
Mon Dieu, Victor, ta boîte About est si triste… Nous avons tous nos hauts et nos bas, mais tu ne devrais pas te battre, mec. Vous êtes un héros pour les golfeurs de code partout dans le monde maintenant!
SimonT
4
Je suis surpris que personne n'a proposé une solution basée sur le sommeil sorte encore
Frank Fermier

Réponses:

178

Parfois, la communauté ici n'aime pas aider à faire ses devoirs. C'est pourquoi vous obtenez tant de réponses à la blague. Mais j'aime aider. Voici une solution complète en 'C' (puisque je suppose que vous voulez apprendre la "programmation", pas le "script" avec Java ou Ruby). J'ai inclus de nombreux conseils que j'aurais aimé connaître lors de mon premier apprentissage

#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++);
  }
AShelly
la source
32
presque tous les conseils sont faux, et il continue simplement à demander la liste de saisie jusqu'à ce que vous l'ayez déjà triée.
AShelly
47
+1, pour 1st, 2th, 3th, 4th...et l'opérateur downto - techniques de programmation C très avancées.
Kaya
5
Devrait utiliser sscanf(input, "%5s", &input[0]), sinon il pourrait y avoir des bogues de dépassement lors de l'analyse de l'entrée. Et l'entrée doit être déclarée char input[sizeof(int)+1], pour assurer la compatibilité ascendante avec les systèmes 64 bits.
sh1
12
i==1?"st":"th"hahaha ...
Guy Sirton
15
Java a la collecte des ordures. Par conséquent, Java est pour "script", pas de programmation réelle. C'est CS101 de base. (ainsi dit le troll.)
AShelly Le
181

La voici en java. C'est une tricherie totale, inacceptable et non corrigible car cela crée une base de données MySQL, y insère le numéro, effectue une sélection avec une clause ORDER BY et affiche les numéros donnés par MySQL. En fait, c'est MySQL qui fait le tri, pas le programme.

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
la source
103
C'est en fait un peu trop près de chez vous pour ce que de nombreux codeurs Java considèrent comme une solution acceptable, une solution aux spécifications !!
Dr. Rebmu
10
Pensez également au cas où vous devez trier un très grand nombre d'objets. Les classer "en dehors du programme" dans une base de données est une solution réalisable.
Viktor Seifert
40
Pas assez d'abstraction ici. Vous avez besoin d'au moins 10 interfaces, 20 implémentations, enums, tests unitaires, tests de couverture, Maven, tests d'intégration,
simulacres
6
@NaftuliTzviKay Nous devrions créer un MySQLSortEnterpriseEdition pour implémenter votre idée. Victor acceptera-t-il que le code soit sous licence GPL afin que nous puissions commencer?
Joe Z.
14
@ JoeZ. Oui, ma réponse manque de commentaires sur le modèle de licence et je devrais obliger l'utilisateur à accepter un CLUF au début du programme. Mais comme je le donne à l'OP paresseux, il est gratuit pour une utilisation non commerciale, y compris pour créer la prime tant attendue, MySQLSortEnterpriseEdidtion.
Victor Stafusa
142

C # - Il n'y a pas de mort comparable à l'overkill

Tout d’abord, cher GiMmEtHaCoDeZ, essayons de décomposer votre tâche:

  1. Lire les chiffres
  2. Les trier
  3. Sortez les nombres triés.

Comme "Diviser et conquérir" est une stratégie très importante lorsque vous travaillez avec des problèmes logiciels, abordons-les un à la fois.

1. lecture

Un autre problème important dans le logiciel est la polyvalence. Comme il n’est pas spécifié comment l’utilisateur entrera les chiffres, cela peut se faire via la console, via un fichier, via un service Web, etc. Peut-être même une méthode à laquelle nous ne pouvons pas penser pour le moment. Il est donc important que notre solution puisse prendre en charge différents types de saisie. Le moyen le plus simple d'y parvenir consiste à extraire la partie importante d'une interface, disons

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

  DoubleArrayReaderType Type {get;}
}

DoubleArrayReaderTypeest une énumération donnée avec

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

Il est également important de rendre le logiciel testable à partir de la base, de sorte qu'une implémentation de l'interface sera

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

Ensuite, la question logique est de savoir comment nous saurons charger IDoubleArrayReaderle code approprié . C'est facile tant que nous utilisons une usine simple:

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

Notez que, comme nous utilisons la réflexion pour charger tous les lecteurs actifs, toutes les extensions futures seront automatiquement disponibles. Maintenant, dans le corps principal du code externe, nous ne faisons que:

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

2. Traitement (tri)

Nous devons maintenant traiter, c'est-à-dire trier les nombres que nous avons acquis. Notez que les étapes sont complètement indépendantes les unes des autres, donc, pour le sous-système de tri, la façon dont les nombres ont été entrés n'a pas d'importance. De plus, le comportement de tri est également sujet à modification, par exemple, nous pourrions avoir besoin de mettre en place un algorithme de tri plus efficace. Alors, naturellement, nous allons extraire le comportement de traitement demandé dans une interface:

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

  DoubleArrayProcessorType Type {get;}
}

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

Et le comportement de tri implémentera simplement l'interface:

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

Bien entendu, nous aurons besoin d’une usine pour charger et gérer les instances de traitement.

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. Écrire la sortie

Il n’ya pas grand chose à dire ici, car c’est un processus qui reflète l’entrée. En fait, nous pourrions combiner les usines de lecture et d’écriture en une seule DoubleArrayInputOutputFactory, comme ceci:

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

}

Mettre tous ensemble

Enfin, notre programme principal utilisera simplement toute cette génialité que nous avons déjà construite. Le code sera donc simplement:

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

où, par exemple, nous pourrions définir reader, writeret en processorutilisant

IDoubleArrayReader reader = DoubleArrayInputOutputFactory.CreateDoubleArrayReader(DoubleArrayReaderType.MockService);
IDoubleArrayProcessor processor = DoubleArrayProcessorFactory.CreateDoubleArrayProcessor(DoubleArrayProcessorType.Sorter);
IDoubleArrayWriter writer = DoubleArrayInputOutputFactory.CreateDoubleArrayWriter(DoubleArrayWriterType.Console);
SWeko
la source
49
Lol, ListSort Enterprise Edition © :-P +1
Bouton de porte
14
+1 pour le surcodage fou. Je suggère que vous divisiez votre réponse en 3 réponses 'module' ou plus afin que je puisse les +1 individuellement
greggo
15
Et cerise sur le
gâteau,
9
C'était magnifique.
Andrew
7
L'utilisation de DI ne fera que confondre le PO, car il ne s'agit que d'un exemple rapide.
SWeko
132

Une interprétation encore plus littérale:

echo " aaehrrty"

c'est-à-dire, "le tableau" trié.

RBerteig
la source
5
Je suis venu ici pour poster ceci.
Quuxplusone
5
enregistrer en tant que fichier sort.shet appeler en tant quesh sort.sh "an array of doubles"
Kyss Tao
Je pense que vous avez manqué le "l'utilisateur entre un tableau de doubles".
Dukeling
1
@Dukeling, voilà le commentaire de Kyss Tao. "an array of doubles"peut être passé au script en tant qu'argument de ligne de commande.
AJMansfield
108

Perl

Parmi toutes les choses que j'ai faites pour CodeGolf.SE, cela a probablement pris le plus de temps, au moins quelques heures.

$_[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;

L'entrée est de la forme [2,4,5,7,7,3]et la sortie est de la forme [2,3,4,5,7,7].

Je n'ai pas le temps de t'expliquer maintenant ... reviens plus tard.

Quoi qu'il en soit, il y a quelque chose appelé un tableau anonyme en Perl. C'est un tableau, mais il n'a pas de nom. Ce que nous savons, cependant, est une référence (emplacement mémoire) qui pointe vers elle. Une série de nombres entre crochets crée un tableau anonyme, auquel il renvoie une référence.

Cette réponse est construite à partir d’une série de tableaux anonymes, dont les références sont stockées dans @_. L'entrée est transformée en tableau anonyme. Nous créons ensuite d'autres tableaux anonymes, dont chaque élément est une référence à un élément du tableau précédent. Au lieu de trier les éléments du tableau, nous trions les pointeurs sur les éléments de ce tableau. Nous créons également un nouveau tableau pour chaque étape (et plus) de l'opération de tri.

PhiNotPi
la source
3
mal! mal! mal!
DGM
56
à peu près aussi déchiffrable que n'importe quel autre script Perl pour moi :)
Corey Goldberg Le
6
@swelljoe En fait, $_c'est une chaîne vide à cet endroit. J'ai enregistré la sortie souhaitée dans $\ le séparateur d'enregistrement de sortie.
PhiNotPi
4
@Andy simple. "Comment ça marche?"
John Dvorak
1
et toutes les variables créées par l'utilisateur ont de jolis noms qui respectent toutes les conventions pensables
Hagen von Eitzen
80

Python

Donne à l'utilisateur un tableau trié en supprimant tous les éléments non triés du tableau en entrée.

import sys

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

L'algorithme parcourt la liste en ajoutant uniquement chaque élément s'il ne rend pas la liste non triée. Ainsi, le résultat est une liste triée, mais pas une liste contenant tous les éléments de la liste originale. Si l'op vérifie simplement si la liste est triée, il ne remarquera peut-être pas qu'il manque des valeurs dans la sortie.

Winston Ewert
la source
1
Veuillez voir les autres réponses avant de poster les vôtres. Vous devriez ajouter le nom de votre langue. Pour répondre à cette question, vous devez également expliquer brièvement ce que vous faites pour contrôler le PO.
Wasi
5
Hehe, celui-ci m'a fait rire aux éclats. Quoi qu'il en soit, je conviens qu'une explication un peu meilleure serait utile.
oconnor0
2
Le double appel à sys.stdin.read()une faute de frappe ou fait-il partie de la vraie réponse à la traîne? Il serait certainement frustrant pour le PO de donner le tableau en entrée et de continuer à attendre le résultat ...
Bakuriu
Wow, c'est mal, d'accord.
Sylverdrag
13
Un O(n)algorithme de tri. Agréable.
ejrb
65

Bash, 54 caractères

Beaucoup de réponses utilisant des langages lents et inefficaces comme C et Python ... accélérons un peu les choses en offrant une solution dans la mère de tous les langages de script: Bash.

Je sais ce que vous pensez - Bash ne peut même pas gérer l'arithmétique en virgule flottante, alors comment va-t-il trier, n'est-ce pas? Eh bien, voici ma mise en œuvre du puissant algorithme SleepSort:

#!/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."

Le programme est fourni avec une entrée en tant qu'argument de ligne de commande. Échantillon échantillon:

> ./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.

Cela a également l’avantage d’être peut-être le plus court des algorithmes de travail présentés ici. C'est vrai - une puissante ligne de bash , utilisant uniquement les commandes intégrées bash et n'appelant aucun fichier binaire externe (c'est-à-dire, si vous ne comptez pas la sortie purement facultative et détaillée). Contrairement aux bogosorts, son runtime est déterministe.

Conseil: Une optimisation efficace consiste à diviser les nombres saisis par un facteur avant le tri. L'implémentation est laissée au lecteur.

Modifier:

Version de golf 54 caractères réduite avec moins de jolies impressions:

#!/bin/sh
for i in $@;do echo $(sleep $i)$i&done;wait
Émeute
la source
11
Trolling 1: l'algorithme fonctionne, mais est évidemment potentiellement extrêmement lent - il génère un thread pour chaque nombre, dormant pendant ce nombre de secondes avant de sortir le nombre (qui est donc dans l'ordre). Trolling 2: De plus, la majeure partie du code est consacrée à la rédaction d'un commentaire intéressant sur le nombre de threads générés, ainsi qu'à la lecture et à l'analyse gratuites et gratuites des informations sur l'unité centrale du système, dans le seul but d'obtenir une sortie plus détaillée. Trolling 3: Il sort "le tableau trié" à la fin, ce qui semble être chose faite. Trolling 4: L'utilisateur ne peut pas annuler le "tri" en appuyant sur ctrl-c.
Émeute
4
5. Cela ne fonctionne que sous GNU / Linux , en raison de l'utilisation de /proc/cpuinfo.
kps11346
5
Au fait, c'est une solution extrêmement créative :)
dmitry
8
Ceci est incroyable. Je ne peux même pas dire à quel point c'est génial. J'envisage de l'utiliser activement, car POURQUOI PAS.
4
En fait, j’ai réellement une variante de cette utilisation quelque part dans la production. Mais dans cette situation, la durée du processus est importante, c'est donc mon excuse ...
Riot
64

JavaScript a une sort()fonction intégrée, vous pouvez l'utiliser comme ceci:

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

... oh, j'ai complètement oublié de mentionner, cela trie par ordre lexicographique, c'est à dire 10 < 9et 9 < -100. C'est probablement ce que vous attendez de toute façon.

Alexey Lebedev
la source
8
C'est encore mieux parce que c'est une fonction intégrée.
Wayne Werner
62

(jPL) Langage de programmation jQuery

Vous devez utiliser jQuery pour cela. Une solution simple à ce problème est la suivante:

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
la source
55
J'aime particulièrement la façon dont cela ne fait utiliser jQuery.
Kryan
8
-1 Votre nom de tableau doit inclure la notation hongroise, en particulier les objets jQuery signifiés en utilisant $, les tableaux en utilisant aet les résultats de window.promptas p.
Qantas 94 Heavy
2
La "partie délicate" est élégante. OP, essayez d'avoir ce genre de structure de code un jour.
Chris Barker
2
Cette "validation" F'n doble LOOOOOOOOOOOOL omg omg day made! édité pour moins de majuscules
HC_
54

C

Cette solution combine la concision et l’accès au système d'exploitation fourni par C avec les puissants composants logiciels réutilisables de 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
la source
4
Ou un "script": #!/usr/bin/sort.
Escargot mécanique le
54

Rubis

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

Assez explicite.

Ou demander que l’entrée soit réellement "un tableau de doubles":

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

Ne pas utiliser gets.chomppour plus de méchanceté. Également utiliser regex après le trailing jusqu'à, ce que je ne savais même pas que vous pouviez faire (merci Jan Dvorak) pour confondre OP encore plus!

Poignée de porte
la source
4
En développant l'idée, je demanderais à plusieurs reprises une entrée jusqu'à ce que l'utilisateur saisisse la chaîne an array of doubles.
Wrzlprmft
@Wrz Ok, c'est fait :-)
Poignée de porte
2
C’est formidable, car le pauvre OP devra trouver comment se débarrasser d’une nouvelle ligne (parce que vous utilisez getsau lieu de gets.chomp).
wchargin
@WChargin Oui, je l'avais dans la première révision (voir l'historique des révisions) mais je l'ai enlevé pour qu'il soit encore plus pervers>: D EDIT: Oh, attendez, peu importe, c'était mon autre réponse. Je vais éditer celui-ci :-)
Bouton de porte
1
+1 J'ai créé un compte ici juste pour dire, c'est exactement comment j'y répondrais! Aimer!
DGM
44

Python3.3

Bien sûr, voici le programme Python le plus simple qui puisse trier un tableau sous forme de liste littérale sur stdin:

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)

Malheureusement, cela ne fonctionne que dans python3.3 + car il utilise l' yield fromexpression. Le code devrait être assez explicite, de sorte que vous ne devriez pas avoir de problèmes lorsque vous le remettez à votre professeur.


La pêche à la traîne consiste à fournir une solution parfaitement opérationnelle qui fait exactement ce que le PO voulait, mais d'une manière qui:

  • impossible à comprendre (par un débutant)
  • impossible à traiter à l'enseignant car:
    • le PO ne peut pas le comprendre
    • même s'il pouvait, l'enseignant n'aurait pas le temps de déchiffrer pour le comprendre
  • effrayant pour un débutant naïf qui pourrait penser que la programmation est trop difficile pour lui

En résumé, cette réponse augmenterait considérablement la frustration de l'étudiant qui se moquait de leurs demandes avec des réponses parfaitement valables d'un certain point de vue.


(Ne lisez pas si vous considérez comme un défi la compréhension du code ci-dessus)

Je dois ajouter que la pêche à la traîne est également accrue par le fait que l’algorithme de tri mis en œuvre est en réalité

sorte de bulle! ... qui pourrait sûrement être mis en œuvre d'une manière que même le PO puisse comprendre. Ce n'est pas un algorithme obscur en soi, c'est juste une bonne obscurcissement de code de quelque chose que l'OP pourrait autrement parfaitement comprendre.

Bakuriu
la source
3
Je pense que cela pourrait utiliser plus d'explications; que faites-vous à l' enfer maintenant?
Kryan
1
Wow, vous pouvez faire des noms de variables non-ASCII en python? ne savait pas ...
kratenko
1
@kratenko De python3 +. En python2, l'interpréteur considère l'ASCII comme un encodage et aurait généré une erreur. En python3, l'interpréteur suppose que UTF-8 est un encodage et accepte tous les caractères qui sont des "lettres" selon les propriétés unicode des identificateurs.
Bakuriu
3
@KRyan: Il utilise évidemment la méthode de tri utilisée par Hell pour amener les gens dans les neuf cercles.
Joe Z.
10
Oh mon Dieu… +1 pour è.
Sean Allred
41

C - Style de codage lent, difficile à utiliser et inacceptable

L'algorithme de tri lui-même est connu sous le nom de slowsort et présente une complexité de cas optimale (simplexité) d'environ n ^ (log n / 2) . L'algorithme a été publié par Andrei Broder et Jorge Stolfi dans leur excellent article intitulé "Algorithmes pessimaux et analyse de la simplexité", que je recommande vivement pour des rires amusants ET des pistes de réflexion.

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

Cependant, le tri lui-même est inutile, nous avons donc besoin d'un moyen pour l'utilisateur de saisir les données qu'il souhaite trier. L'analyse des doublons est pénible, alors pourquoi ne pas les entrer octet par octet.

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

Pour prouver que cela fonctionne:

 $ 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

Au final nous avons:

  • L'algorithme de tri déterministe le plus lent que je connaisse
  • Limites codées dures et silencieuses sur la longueur de la liste
  • Absolument horrible entrée, je pourrais aussi rendre la sortie similaire mais je pense que c'est plus drôle de cette façon.
    • Considérez: vous aurez besoin de savoir quelle machine votre machine doit utiliser le programme.
    • De plus, vous ne pouvez pas entrer 0 (-0 c'est ok)
  • Arithmétique de pointeur et à peu près aucune préoccupation pour les types que les pointeurs sont exprimés de toute façon
Shiona
la source
Cela a un comportement indéfini pour toutes les entrées de plus de 7 octets. Pas une réponse acceptable.
Michael Spencer
1
Aimez le papier "Algorithmes Pessimal"; Merci.
Ryan
«L'algorithme de tri déterministe le plus lent que je connaisse» - l' algorithme manifestement le plus lent de tri déterministe. C'est tout le but du document, AFAIR.
Konrad Rudolph
@ MichaelSpencer Des soins à élaborer? J'ai donné un exemple avec une taille d'entrée de 24 octets et la sortie correspond à ce à quoi on pourrait s'attendre (je pense que je risque de rater une blague ici).
Shiona
2
@Sasho mais une sorte de bogo a un temps d'exécution optimal de \ Omega (n) (comparaisons n-1, 0 opérations). C'est beaucoup plus rapide, aka. pire que \ Omega (n ^ (log n / 2)).
Shiona
39

Ruby, le mal Bogosort! (Bonus: bogosort par entrée utilisateur)

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 * ","

Le "diable" se tord:

  • fonctionne vraiment vraiment vraiment vraiment vraiment vraiment très lentement, bien sûr
  • utilise la comparaison de chaînes, donc 10 est inférieur à 2. Peut être facilement corrigé en .map &:to_fajoutant à la deuxième ligne, mais OP peut ne pas savoir que
  • ne pas utiliser chompsi le dernier numéro a une fin de ligne mystérieuse à la fin
  • ne pas utiliser, stripil y a donc des espaces blancs mystérieux autour des nombres si les caractères sont séparés par des virgules (ex. L'espace 1.5, 2)

Ou, que diriez-vous de bogosorting par l' utilisateur ?! >: 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 * ","
Poignée de porte
la source
Pourquoi ne pas Bogobogosort ? (fonctionne dans un pittoresque temps O (n * (n!) ^ n))
wchargin
@Wchargin J'envisage peut-être :-) vous pouvez être intéressé par mon récent montage! (Désolée de ma lenteur, je suis actuellement au téléphone car je n’ai pas accès à un ordinateur :-P)
Bouton de porte
37

COBOL

Sûr! "Même un singe peut faire ça!"

Voici un programme COBOL simple qui triera l’entrée pour vous. Lisez les commentaires pour voir à quel point c'est extensible et trivial. Le véritable avantage de ce logiciel réside dans le fait qu’il s’agit d’un mécanisme éprouvé qui ne repose pas sur des langages nouveaux et relativement peu testés, tels que Java et tous les langages Web ou de Microsoft. Il compile très efficacement et les procédures de ce type sont utilisées par les sociétés financières les plus prospères de Fortune500 et par d’autres leaders du secteur. Ce code a été révisé par de nombreux experts et est reconnu comme étant un excellent mécanisme de tri.

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
la source
6
Seul vous utiliseriez COBOL pour répondre à cette question. +1
syb0rg
5
Ah, l'odeur fraîche des cartes perforées
Sklivvz
3
@EbenezerSklivvze - LOL. Une fois, j'ai sorti une carte perforée que j'utilisais comme marque-page lorsque mon professeur d'assemblée parlait à la classe de vieilles cartes perforées. Il était suffisamment terrassé (c'était en 1994 :). Je ne pense pas que beaucoup de mes contemporains aient déjà vu un jeu complet ...
DVK
30

OP n'a jamais dit COMMENT les trier ... ou quelle était sa définition des doubles. En supposant que le type de données soit doubleinterprété comme un doublon . Utiliser JavaScript ici.

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

Résultat: ordre alternatif [4, 11, 4, 9, 5, 7, 6, 7]

Kiruse
la source
4
"Assumer le type de données double mais l’interpréter comme un doublon". Seul un véritable génie penserait de la sorte. Tout simplement génial!
Felipe Miosso
@FelipeMiosso Pour être honnête, je ne suis pas sûr que vous soyez simplement sarcastique ...
Kiruse
1
Haha ... j'étais sarcastique. Je sais qu'il y a des gens qui pensent vraiment de cette façon. En tout cas ... ta réponse était épique! J'ai beaucoup ri.
Felipe Miosso
@ FelipeMiosso Heureux d'avoir pu aider à faire rire. ;)
Kiruse
console.log tout!
Emil Vikström
28

PHP

Voici une implémentation complète avec gestion des erreurs. C'est le plus rapide pour tous 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
la source
25
do
{
}
while(next_permutation(begin(ar), end(ar)));

La permutation suivante en C ++ fonctionne en renvoyant true lorsque le tableau est trié et false sinon (après permutation). Donc, vous êtes censé trier le tableau et l'utiliser ensuite dans un do-while comme ci-dessus (ainsi, le cercle complet sera renvoyé au tableau).

utilisateur974006
la source
+1 J'ai pensé à utiliser next_permutationpour ma réponse, mais c'est beaucoup plus propre que ce que j'avais en tête.
Jliv902
25

[solution par mauvaise direction ponctuelle]

Veuillez lire la norme correspondante, IEC 60559: 1989, Spécification pour l’arithmétique binaire en virgule flottante pour les systèmes à microprocesseur , que vous pouvez acheter ici . Dans la note de bas de page relative au §5.10 Détails du prédicat totalOrder , il est noté que:

totalOrder n'impose pas un classement total pour tous les encodages dans un format. En particulier, il ne fait pas la distinction entre différents codages de la même représentation en virgule flottante, comme lorsqu'un ou les deux codages sont non canoniques.

Nous voyons donc qu'il est impossible d'écrire du code pour trier les doublons. C'est une question piège. Ha, ha, très intelligent! S'il vous plaît dites à votre professeur que j'apprécie beaucoup son cours.

[edit: rien ne m'oblige à ne pas supposer que le problème demande un ordre total]

kps11346
la source
3
Mais le problème était de trier les doubles. Personne n'a exigé que les valeurs soient dans l'ordre (total). Par exemple, vous pouvez trier le tableau en deux nombres, positif et négatif. Vous avez été doublé par la question.
Shiona
23

Un JavaScript maléfique:

OP, je ne veux pas tout vous donner, alors je vous laisse comprendre comment obtenir vous-même les commentaires de l'utilisateur (indice: utilisation prompt).

Une fois que vous avez cela, voici une fonction dans laquelle vous pouvez passer votre tableau pour le trier. Vous devez simplement fournir le tableau, la valeur la plus basse du tableau et un incrément:

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

Voici un violon pour le voir en action avec l'exemple de saisie utilisateur [1.5, -3.5, 12, 10, -19.5].


Remarque: en plus d'être peu performant, complexe et non extensible au problème à résoudre, cela sera particulièrement frustrant si le PO ne connaît pas le calcul en virgule flottante. Par exemple, si l'entrée utilisateur est [8.1, 5, -.8, 2.3, 5.6, 17.9]et que le PO choisit les valeurs simples (ie minimumVal=-.8et increment=.1), le programme sera exécuté à tout jamais. Sur une note connexe, je suis actuellement l'heureux propriétaire de 2 onglets de navigateur qui ne fonctionnent pas à cause de ce problème :)

Note II: Je me sentais dégoûtant même en écrivant le code ci-dessus.

Remarque III: MWA HAHAHAHA!

Briguy37
la source
Bonne idée. Vous devez avoir été cool quand vous étiez encore un débutant en programmation.
Pierre Arlaud le
22

Voici une réponse que j'aime bien pour Java:

Ajoutez la ligne avant println et votre tableau est trié

Arrays.sort( array );

Aucune explication, confond le PO , mais fonctionne et obtiendra des votes positifs de programmeurs plus expérimentés.


Une autre réponse similaire :

Jetez un coup d'oeil à Arrays.sort ()

Indiquant indirectement au PO de faire ses propres recherches tout en lui donnant une réponse correcte et vague. Sans autre recherche, le PO reste confus . J'aime aussi le fait que le lien pointe vers une documentation plus ancienne.

syb0rg
la source
10
Ceci est utile et mérite donc un vote négatif.
emory
11
"Dire indirectement au PO de faire ses propres recherches tout en lui donnant une réponse correcte et vague" décrit assez bien mon style de réponse StackOverflow: /
Corey Goldberg
7
"Jetez un coup d'œil à Arrays.sort ()" ... "Pourrais-je avoir un exemple d'utilisation de ce programme dans mon programme?" ... brillant.
SimonT
5
+1 surtout parce que notre humble OP doit probablement écrire lui-même une sorte pour une classe, rendant Array.sort () complètement inutile.
Kevin
2
Ctrl + F -> "Pourrais-je avoir un exemple d'utilisation de ce programme dans mon programme?" = 3 résultats.
Qix
21

Algorithme génétique / méthode de Monte Carlo pour le problème de tri en JAVA

Le problème du tri est connu de l’informatique depuis longtemps et de nombreuses bonnes solutions ont été trouvées. Au cours des dernières années, la bio-informatique a beaucoup progressé et il a été démontré que la résolution des problèmes par la biologie était très utile pour résoudre des problèmes difficiles. Cet algorithme de tri utilise le meilleur de ces idées pour les utiliser afin de résoudre le problème de tri. l'idée est plutôt simple. Vous commencez avec un tableau non ordonné et découvrez comment le tri est déjà effectué. Vous lui attribuez une note de "tri" puis permutez le tableau avec une composante aléatoire - comme en biologie où il n’est pas clair à quoi ressembleront les enfants, même si vous savez tout sur les parents! C'est la partie algorithme génétique. Vous créez la progéniture de ce tableau pour ainsi dire. Ensuite, vous voyez si la progéniture est mieux triée que le parent (ou survie du plus apte!). Si tel est le cas, vous continuez avec ce nouveau tableau comme point de départ pour construire la permutation suivante et ainsi de suite jusqu'à ce que le tableau soit entièrement trié. La bonne chose à propos de cette approche est que cela prend plus court, si le tableau est déjà un peu trié depuis le début!

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

}

Suppléments

  • Mauvais usage de java.awt.List
  • nom variable variable et incohérent
  • complètement des conneries bla bla à propos de la bioinformatique
  • langage inventif et incohérent dans l'explication
  • monte carlo est manifestement le mauvais outil pour des problèmes déterministes simples
  • importations inutiles
  • probablement plus de goodies ...
Luksch
la source
Est-ce qu'appeler cette GA ou Monte Carlo est un autre niveau de troll? Je crois que c'est un algorithme d'escalade aléatoire.
Shiona
Associer ce programme à des noms de mot à la mode était intentionnel, mais je n'ai jamais entendu parler d'un "algorithme d'escalade aléatoire" ... et dans un sens plus large, je pense que GA et Monte Carlo ne sont pas trop loin pour se tromper ...
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)

Trie le tableau (liste) par la somme des 3 ème et 5 ème places décimales.

grc
la source
5
Malheureusement, cela est résolu de manière triviale en supprimant tout ce qui suit lambda x:et en le remplaçant par x. Pourtant, un codeur débutant ne le saura jamais, alors bravo!
Joe Z.
18

C ++

Cela fonctionne ... finalement.

Voici mon algorithme de tri:

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

Voici le programme complet:

#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
la source
6
Votre espèce d'algorithme m'a fait pleurer.
Nate
Hah, ce n'est pas un algorithme car il n'est pas accordé pour finir>: D
jmacedo
@joxnas, en réalité sur des systèmes où les périphériques aléatoires non déterministes ne sont pas disponibles, le randomiseur peut en fait être périodique. Cela dépend alors simplement du fait que l'ensemble des permutations possibles permises par le randomiseur subsume l'ensemble des permutations possibles $ S_n $ pour toutes les longueurs possibles du tableau d'entrée $ n $.
bug
Aw pants, j'ai oublié que LaTeX n'était supporté que par TeX.SE et Math.SE. Imaginez juste ces symboles en italix snooty.
bug
18

Ici, régalez vos yeux:

<?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>

Ce morceau de code affiche le tableau et demande à l'utilisateur d'entrer le plus petit double du tableau. Il ajoute ensuite le nombre à la liste des nombres triés, supprime le double du tableau et affiche les autres numéros.

* Mauvaise interprétation: point faible, mais le PO ne s'attend pas exactement à ce que le programme demande à l'utilisateur de l'aider à trier.

* Triche: l'utilisateur est celui qui fait le tri.

* Performances: chaque numéro de la baie de disques requiert un aller-retour sur un serveur et oblige l'utilisateur à rechercher manuellement le plus petit nombre. La performance ne peut pas être pire.

* Inacceptable: je pense avoir couvert ça. Et bonne chance pour le réutiliser. Dans le pire des cas, l'utilisateur pourrait se débarrasser de 90% du code et effectuer une boucle répétitive pour trouver les plus petites valeurs et les supprimer à chaque fois, ce qui lui donnerait l'un des algorithmes de tri les moins efficaces.

* Créatif et diabolique: tu me le dis.

Sylverdrag
la source
2
Vous dites "régalez vos yeux" et me donnez PHP Oo
Aidiakapi
3
"Mal" faisait partie des exigences, n'est-ce pas?
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
la source
6
Crédit lorsque le crédit est dû: dangermouse.net/esoteric/intelligentdesignsort.html
wchargin
1
Vous ne comprenez pas pourquoi vous critiquez le design intelligent dans un concours de programmation?
khebbie
12
@ khebbie Pourquoi pas?
Konrad Rudolph
Le problème, c’est que si l’utilisateur est celui qui a saisi les chiffres, il serait alors plus intelligent qu’eux-mêmes. ;)
d -_- b
16

Python - req. #1

Ce code triera les doubles dans l'ordre lexicographique plutôt que dans l'ordre croissant, en créant un arbre de préfixes de chiffres, puis en effectuant une itération récursive.

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

Cela fonctionne dans le n log ntemps et est en fait un moyen intelligent de conserver une liste triée sinon, mais malheureusement pour le PO, il fait complètement la mauvaise chose.

Joe Z.
la source
4
C'est également particulièrement sournois en ce que si tous les nombres ont le même nombre de chiffres avant le point décimal, cela fonctionnera correctement, de sorte que le PO peut même ne pas remarquer que le type fait quelque chose de mal s'il le teste simplement en utilisant une entrée de , dire 2, 1, 3, 8, 5.
Joe Z.
14

Trie le tableau des doubles. En 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;}

Par exemple:

[0.0, 1.5, 123]

va de la représentation binaire non triée de

011111111111000000000000000000000000000000000000000000000000000100000001011110110000000000000000000000000000000000000000000000

à l'élégant trié

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111

planetguy32
la source
11

J'ai besoin d'un programme où l'utilisateur entre un tableau de doubles et le programme sort le tableau trié. Pourriez-vous s'il vous plaît donner le code?

Edit par kealiste, je suppose que c'est mieux si commenté pour rendre la division sembler plausible. Dans 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

En jouant sur l’idée qu’ils ne savent pas vraiment ce qu’est un doublon, ils pourraient croire qu’une liste de doublons n’est qu’un tas de chiffres multipliés par deux.

Dr. Rebmu
la source
6
Peut-être ont-ils besoin d'être divisés par deux puisque l'entrée est déjà doublée!
kéaliste
@Kealist j'ai considéré que, cependant, cela joue sur l'idée que le "doublage" est en train de se produire. Je pense que ça passe un peu mieux d'avoir le [2 * num].
Dr. Rebmu
10

Délibérément mal comprendre la question:

En utilisant une approche récursive:

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

Il est garanti que le tableau trié sera sorti à un moment donné, pour tout type de données du tableau, même tout type d'ordre de tri et même tout type de séparateur pour l'entrée, ce qui rend cette approche extrêmement flexible. Son principal inconvénient est qu’il est un peu lent pour les tableaux de grande taille, mais vous pouvez le résoudre facilement avec le multithreading.

Valentin CLEMENT
la source