Écrivez un programme de tri qui semble erroné mais qui est en fait correct [fermé]

12

Écrivez un programme qui trie un vecteur de nombres (ou n'importe quel type d'élément) qui ressemble à un ou plusieurs bogues, mais c'est en fait correct.

  • Le code doit être clair. Quelqu'un qui regarde le code doit facilement identifier qu'il s'agit d'un algorithme de tri et doit facilement confondre un morceau de code correct avec un bogue.
  • Le bogue (apparent) peut par tout ce qui rend le code syntaxiquement ou sémantiquement mal formé (par exemple, rendre le programme non compilable / exécuté, présenter UB lorsqu'il est exécuté), faire en sorte que le programme produise des résultats incorrects, ne se termine pas ou ne soit pas déterministe.
  • Le code doit en fait être bien formé et le programme doit produire de manière déterministe la sortie correcte dans un temps fini.
  • L'entrée peut être codée en dur dans le programme ou peut être lue (à partir de l'utilisateur, du fichier, etc.).
  • L'entrée est considérée comme valide et le programme n'est pas nécessaire pour vérifier l'exactitude de l'entrée.
  • Tout algorithme de tri est accepté. Il n'est pas nécessaire que la structure de données pour contenir les nombres soit un vecteur réel. Le programme peut être conçu pour trier un nombre variable de nombres ou un nombre fixe de nombres (par exemple, un programme pour trier 3 nombres est correct ). Le tri peut être stable ou non (note: un programme conçu pour faire un tri stable qui a un bug apparent qui rend le tri instable, mais en réalité ce n'est pas un bug: le programme fait en fait un tri stable - est une réponse valide ).
  • vous pouvez appeler toutes les fonctions (y compris les fonctions de tri) à l'exception des outils tiers (à moins qu'elles ne soient largement répandues et utilisées, par exemple boospour C++, JQuerypour Javascript- celles-ci peuvent être utilisées)
  • spécifier la langue
  • commentez dans le code la partie qui ressemble à un bug.
  • expliquez à quoi ressemble le bug en faisant mal.
  • expliquer (dans une boîte de spoiler) pourquoi ce n'est pas un bug.

Il s'agit d'un concours de popularité. La réponse avec la plupart des votes l'emporte.


Ce défi est maintenant terminé. Le gagnant est @Clueless /codegolf//a/30190/11400 avec 8 votes. Merci à tous les auteurs!

Si vous souhaitez participer après l'attribution du gagnant, n'hésitez pas à ajouter une nouvelle réponse. Vous êtes hors course, mais nous sommes tous intéressés à voir des réponses intéressantes.

bolov
la source
Puis-je utiliser des booléens nilables au lieu de nombres?
Junurous
oui, édité la question aussi: tout type d'éléments
bolov
1
Je vote pour fermer cette question comme hors sujet car les défis sournois ne sont plus sur le sujet sur ce site. meta.codegolf.stackexchange.com/a/8326/20469
cat

Réponses:

11

C ++

Inspiré d' Apple goto fail; bug .

#include <vector>
#include <map>
#include <iostream>

/**
 * Sorts a vector of doubles in reverse order using the bucket sort algorithm.
 */
std::vector<double> reverse_bucket_sort(const std::vector<double>& input) {
    // put each element into a bucket as many times as it appears
    std::map<double, int> bucket_counts;
    for (auto it : input)
        ++bucket_counts[it];

    std::vector<double> sorted_elements; // the return value

    // loop until we are done
    while (bucket_counts.size() > 0) {
        // find the largest element
        double maximum = std::numeric_limits<double>::lowest();
        for (auto it : bucket_counts) {
            if (it.first > maximum)
                maximum = it.first;
                maximum = it.first;
        }

        // add the largest element N times to our sorted vector
        for (int i = 0; i < bucket_counts[maximum]; ++i)
            sorted_elements.push_back(maximum);

        // and now erase the bucket
        bucket_counts.erase(maximum);
    }

    return sorted_elements;
}

int main(int argc, const char * argv[]) {
    std::vector<double> test_case = { 0, 1, 2.5, 10, 2.5, 2 };

    std::cout << "unsorted:";
    for (auto it : test_case) std::cout << " " << it;
    std::cout << std::endl;

    std::cout << "sorted:";
    for (auto it : reverse_bucket_sort(test_case)) std::cout << " " << it;
    std::cout << std::endl;

    return 0;
}

Au milieu de la page, il y a un bug: nous avons une ligne en double après notre ifvérification! Nous allons toujours mettre à jour le maximum avec la dernière valeur bucket_count. Heureusement, nous allons bien. En C ++ std::mapest trié par clés. Nous inversons donc simplement les seaux, ce que nous voulons.

Aucune idée
la source
Vous ne l'avez pas utilisé goto, donc il n'y a pas de bug. (Se référant à toutes les personnes qui ont dit que le bogue ne se serait jamais produit si Apple n'avait pas utilisé goto)
user253751
Félicitations, vous avez remporté ce défi en obtenant le plus de votes (8 votes après 7 jours). De plus, j'aime beaucoup votre réponse car vous avez utilisé un bug réel.
bolov
8

Python2.x

import random
L = [random.randrange(20) for x in range(20)]
print "Unsorted:", L

def sort(L):
    # terminal case first. Otherwise sort each half recursively and combine
    return L.sort() if L > 1 else sort(L[:len(L)//2]) + sort(L[len(L)//2:])

sort(L)
print "Sorted:", L

Essai

list.sortrenvoie None, donc la partie après le elseest None + None. Heureusement, cela ne pose pas de problème car la comparaison d'une liste et d'un int l' (L > 1)est toujours True. La fonction retourne toujours Nonedonc nous ignorons la valeur de retour et juste imprimer Lqui a été trié en place La fusion des moitiés triées par caténation n'aurait pas fonctionné non plus même si l'exécution y était parvenue.

grignoteur
la source
Félicitations, vous avez terminé deuxième avec 6 votes après 7 jours. Merci pour votre soumission.
bolov
5

C

Utilisation incorrecte du tri - sur un système 64 bits, cela intfait 4 octets et char *8 octets, donc cela ne devrait pas fonctionner.

Code:

#include <stdlib.h>
#include <stdio.h>

/* Compare integers to sort in reverse order */
int compare(const void *p, const void *q)
{
    const int *a = p;
    const int *b = q;

    return *b - *a;
}

int main()
{
    char *strings[] = {"B", "Que", "Ro", "Sum", "T"};
    int i;

    /* Let's use the integer compare to sort strings */
    qsort(&strings, sizeof(strings) / sizeof(char *), sizeof(char *), compare);

    /* Output the sorted results */
    for (i = 0; i < sizeof(strings) / sizeof(char *); i++)
        printf("%s\n", strings[i]);

    return 0;
}

Construire:

$ gcc -o sort-no-sort sort-no-sort.c 

Courir:

$ ./sort-no-sort 
T
Sum
Ro
Que
B

Ouais, trie bien!

Cinq choses se passent: 1) qsortpasse des pointeurs aux entiers, qui sont de la même taille que les pointeurs aux caractères. 2) Les chaînes ne dépassent pas quatre octets (trois + un terminateur) = la taille d'un entier, que la routine de tri traite avec bonheur comme un entier. 3) La plupart des compilateurs forcent l'alignement des structures de données, donc les chaînes plus courtes occupent le même espace. Cependant, soyez plus grand et préparez-vous aux échecs. 4) Endianité. 5) Zéro initialisation des octets internes.


la source
Merci pour votre soumission. Vous avez terminé 3e. Félicitations!
bolov
2

Cobra

class Program
    var _target as List<of bool?> = [true, true, false, true, true, nil, nil, false, true, nil, true]
    def main
        .sort(_target)
        print _target
    def sort(target as List<of bool?>)
        for i in target.count, for n, in target.count -1, if target[n] <> target[n + 1] and (target[n] or target[n + 1] == nil), target[n], target[n + 1] = target[n + 1], target[n]
            #should return sorted as [nil][false][true]

Oh mon dieu, il semble que j'aie mal attribué n... et comment toutes ces virgules sont-elles arrivées!?

Lorsque nest attribué, le compilateur suppose qu'il donne la première moitié d'une paire clé-valeur (en raison de la virgule), mais il n'y a pas de paire clé-valeur, de sorte que le compilateur ne se plaint pas lorsqu'il ne peut pas affecter la seconde moitié de celui-ci à une variable inexistante. Cela se traduit nsimplement par la valeur de clé .. qui dans ce cas est un numéro d'index. Toutes les autres virgules qui ne sont pas à leur place dans la dernière ligne font en fait partie de la syntaxe Cobra standard.

Οurous
la source
Merci pour votre soumission. Vous avez terminé 3e. Félicitations!
bolov
2

Java

public final class WeirdSort {
    public static void main(final String[] args) {

        //Random
        final Random random = new Random(441287210);

        //Some numbers:
        final List<Integer> list = new ArrayList<Integer>();
        list.add(9);
        list.add(11);
        list.add(3);
        list.add(5);
        list.add(7);

        //Sort randomly:
        Collections.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(final Integer o1, final Integer o2) {
                return (o1 - o2) + random.nextInt(10);
            }
        });

        //Print
        for(final Integer i:list) {
            System.out.print(i + " ");
        }
    }
}

Prints: 3 5 7 9 11 

Fonctionne car cette valeur aléatoire spécifique renvoie «1» pour les 10 premiers résultats

Roy van Rijn
la source
1
Quelle langue utilisez-vous?
Knerd
Java, désolé oublié de mentionner cela (édité).
Roy van Rijn
2

Perl

Entrepreneurs de nos jours! Ne savent-ils pas que l' <=>opérateur (alias "vaisseau spatial") n'est utilisé que pour le tri numérique?

Et pourquoi comparent-ils les opérateurs?

Comment ce code a-t-il réussi nos tests rigoureux ?? !! Il utilise même strictet warnings!

use strict;
use warnings;

sub asciibetically { 0-($a lt $b) || 0+($a gt $b) || <=><=><=> }
                                                   #  ^  ^  ^
                                                   # What?? How did Perl even compile??!!

my @sorted = sort asciibetically qw( bravo charlie alpha );

print "@sorted";   # "alpha bravo charlie"
                   # And how come it works??!!

Pourquoi Perl compile

Le seul véritable <=>opérateur est celui du milieu. Les deux autres ne sont qu'une autre façon d'écrire glob("="). Cela signifie que <=><=><=>(surnommé "flotte spatiale") évalue 0.


Pourquoi ça marche

Le asciibeticallysous-programme est une implémentation de l' cmpopérateur de comparaison de chaînes : " cmp" binaire renvoie -1, 0ou 1selon que l'argument gauche est inférieur, égal ou supérieur à l'argument droit.

Zaid
la source
3
Eh bien, Perl ressemble à un bug de toute façon pour moi ...
chill0r