Tulis program penyortiran yang keliru tetapi sebenarnya sudah benar [ditutup]

12

Tulis program yang mengurutkan vektor angka (atau jenis elemen apa pun) yang terlihat seperti memiliki satu atau lebih bug, tetapi sebenarnya tidak apa-apa.

  • Kode harus jelas. Seseorang yang melihat kode harus dengan mudah mengidentifikasi bahwa itu adalah semacam algoritma dan harus dengan mudah mengacaukan bagian kode yang benar dengan bug.
  • Bug (jelas) dapat oleh apa saja yang membuat kode sintaksis atau semantik terbentuk (misalnya membuat program tidak mengkompilasi / menjalankan, menunjukkan UB ketika dijalankan), membuat program menghasilkan hasil yang salah, tidak berakhir, atau tidak deterministik.
  • Kode harus benar-benar terbentuk dengan baik dan program harus secara deterministik menghasilkan output yang benar dalam waktu yang terbatas.
  • Masukan dapat dikodekan dalam program atau dapat dibaca (dari pengguna, dari file dll.).
  • Input dianggap valid dan program tidak diperlukan untuk memverifikasi kebenaran input.
  • Algoritma pengurutan apa pun diterima. Struktur data untuk menampung angka tidak perlu menjadi vektor yang sebenarnya. Program ini dapat dirancang untuk mengurutkan jumlah variabel angka atau jumlah angka tetap (misalnya program untuk mengurutkan 3 angka ok ). Penyortiran bisa stabil atau tidak (catatan: program yang dirancang untuk melakukan penyortiran stabil yang memiliki bug jelas yang membuat penyortiran terlihat tidak stabil, tetapi dalam kenyataannya itu bukan bug: program ini benar-benar melakukan penyortiran yang stabil - adalah jawaban yang valid ).
  • Anda dapat memanggil fungsi apa saja (termasuk fungsi sortir) kecuali alat pihak ke-3 (kecuali jika tersebar luas dan digunakan misalnya boosuntuk C++, JQueryuntuk Javascript- itu boleh digunakan)
  • tentukan bahasa
  • komentar dalam kode bagian yang terlihat seperti bug.
  • jelaskan apa yang keliru dilakukan bug.
  • jelaskan (dalam kotak spoiler) mengapa sebenarnya bukan bug.

Ini adalah kontes popularitas. Jawaban dengan suara terbanyak menang.


Tantangan ini sudah berakhir. Pemenangnya adalah @Clueless /codegolf//a/30190/11400 dengan 8 suara. Terima kasih untuk semua submitter!

Jika Anda ingin masuk setelah pemenang diberikan, jangan ragu untuk menambahkan jawaban baru. Anda keluar dari perlombaan, tetapi kami semua tertarik untuk melihat jawaban yang menarik.

bolov
sumber
Bisakah saya menggunakan boolean nilable sebagai ganti angka?
Kamis
ya, edit pertanyaannya juga: semua jenis elemen
bolov
1
Saya memberikan suara untuk menutup pertanyaan ini sebagai di luar topik karena tantangan curang tidak lagi pada topik di situs ini. meta.codegolf.stackexchange.com/a/8326/20469
cat

Jawaban:

11

C ++

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

Sekitar setengah halaman ada bug: kami memiliki baris duplikat setelah ifcek kami ! Kami akan selalu memperbarui maksimum dengan apa pun nilai terakhir di bucket_count. Syukurlah kita baik-baik saja. Di C ++ std::mapdiurutkan berdasarkan kunci. Jadi kami hanya membalikkan ember, itulah yang kami inginkan.

Tidak mengerti
sumber
Anda tidak menggunakan goto, karena itu tidak ada bug. (Mengacu pada semua orang yang mengatakan bug tidak akan pernah terjadi jika Apple tidak menggunakan goto)
user253751
Selamat, Anda telah memenangkan tantangan ini dengan memiliki suara terbanyak (8 suara setelah 7 hari). Selain itu, saya sangat suka jawaban Anda karena Anda menggunakan bug kehidupan nyata.
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

Uji coba

list.sortkembali None, jadi bagian setelah elseitu None + None. Untungnya ini tidak menimbulkan masalah karena perbandingan daftar dan int (L > 1)adalah selalu True. Fungsi selalu kembali Nonejadi kami mengabaikan nilai kembali dan Hanya mencetak Lyang telah diurutkan di tempat Menggabungkan bagian yang diurutkan dengan katenasi tidak akan berfungsi baik bahkan jika eksekusi memang sampai di sana.

gnibbler
sumber
Selamat, Anda mendapat posisi kedua dengan 6 suara setelah 7 hari. Terima kasih atas kiriman Anda.
bolov
5

C

Menggunakan sortir secara tidak benar - pada sistem 64 bit intadalah 4 byte dan char *8 byte, jadi seharusnya tidak berfungsi.

Kode:

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

Membangun:

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

Lari:

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

Yap, macam-macam oke!

Lima hal yang terjadi: 1) qsortmeneruskan pointer ke integer, yang ukurannya sama dengan pointer ke karakter. 2) String tidak lebih dari empat byte panjangnya (tiga + satu terminator) = ukuran bilangan bulat, yang secara rutin diperlakukan sebagai bilangan bulat. 3) Kebanyakan kompiler memaksa penyelarasan struktur data, jadi string yang lebih pendek mengambil ruang yang sama. Lebih besar lagi dan bersiaplah untuk kegagalan. 4) Endian-ness. 5) Nol inisialisasi byte internal.


sumber
Terima kasih atas kiriman Anda. Anda telah menempatkan ke-3. Selamat!
bolov
2

Kobra

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 sayang, tampaknya aku salah ditugaskan n... dan bagaimana semua koma itu sampai di sana !?

Ketika nditugaskan, kompiler mengasumsikan bahwa ia memberikan bagian pertama dari pasangan nilai kunci (karena koma), tetapi tidak ada pasangan nilai kunci sehingga kompiler tidak mengeluh ketika tidak dapat menetapkan bagian kedua itu ke variabel tidak ada. Ini menghasilkan nhanya diberi nilai kunci .. yang dalam hal ini adalah nomor indeks. Semua koma out-of-place-looking lainnya di baris terakhir sebenarnya adalah bagian dari sintaks Cobra standar.

Suram
sumber
Terima kasih atas kiriman Anda. Anda telah menempatkan ke-3. Selamat!
bolov
2

Jawa

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 

Berfungsi karena nilai acak spesifik ini mengembalikan '1' untuk 10 hasil pertama

Roy van Rijn
sumber
1
Bahasa apa yang Anda gunakan?
Knerd
Java, maaf lupa menyebutkannya (diedit).
Roy van Rijn
2

Perl

Kontraktor hari ini! Tidakkah mereka tahu bahwa <=>operator (alias "pesawat ruang angkasa") hanya digunakan untuk pengurutan angka?

Dan mengapa mereka membandingkan operator?

Bagaimana kode ini bahkan lulus tes ketat kami ?? !! Bahkan menggunakan strictdan 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??!!

Mengapa Perl mengkompilasi

Satu-satunya <=>operator nyata adalah yang ada di tengah. Dua lainnya hanyalah cara penulisan lainnya glob("="). Ini berarti bahwa <=><=><=>(dijuluki "armada luar angkasa") dievaluasi menjadi 0.


Mengapa ini berhasil?

The asciibeticallysubrutin merupakan implementasi dari string-membandingkan cmpOperator: Binary " cmp" kembali -1, 0atau 1tergantung pada apakah argumen kiri stringwise kurang dari, sama dengan, atau lebih besar dari argumen yang tepat.

Zaid
sumber
3
Yah Perl tetap seperti bug bagi saya ...
chill0r