Potrzebuję programu, w którym użytkownik wprowadza tablicę podwójnych, a program wyświetla tablicę posortowaną

280

Uwaga: To pytanie zostało poważnie zredagowane od czasu, gdy opublikowałem je tutaj. Reguły zostały przeniesione tutaj , przeczytaj je przed opublikowaniem jakiejkolwiek odpowiedzi, aby zrozumieć cel tego. To było pierwsze pytanie stworzone w kategorii .

Wyobraź sobie, że leniwy użytkownik stosu przepełnienia stosu zadaje następujące pytanie:

Potrzebuję programu, w którym użytkownik wprowadza tablicę podwójnych, a program wyświetla tablicę posortowaną. Czy możesz podać kod?

Jak stworzyć fragment kodu, który będzie trollował tego użytkownika? Utwórz fragment kodu, który będzie przydatny dla niedoświadczonego programisty, ale w praktyce będzie całkowicie bezużyteczny.

Zwycięzca jest najbardziej uprzywilejowaną odpowiedzią, z wyjątkiem sytuacji, gdy odpowiedź nie jest w jakiś sposób kwalifikowalna (w celu spełnienia wymagań kwalifikacyjnych sprawdź opis tag-wiki ). Jeśli poprzednio najbardziej uprzywilejowana odpowiedź zostanie pobita w przyszłości w liczbie głosów pozytywnych po zaakceptowaniu, nowa najlepsza odpowiedź zostanie zaakceptowana, a poprzednia nie zostanie zaakceptowana. W przypadku remisu wybiorę zwycięzcę spośród remisów lub poczekam jeszcze trochę.

Odpowiedzi, które nie mają kodu, nie są kwalifikowalne. Mogą być zabawne i uzyskać pozytywne opinie, ale nie zostaną zaakceptowane.

Reguły można znaleźć w opisie tagu .

Uwaga: jest to pytanie . Proszę nie brać poważnie pytania i / lub odpowiedzi. Więcej informacji tutaj .

Victor Stafusa
źródło
48
Stack Oversort
ThiefMaster
6
@bluesm Jeśli ktoś już postanowił poprosić kogoś innego o rozwiązanie swojego problemu zamiast „marnowania” własnego czasu na naukę, opublikowanie linku do miejsca, w którym można się uczyć na własną rękę, nie przyniesie nic dobrego.
IQAndreas,
3
Wow, to pytanie otrzyma 100 głosów pozytywnych i 10 000 wyświetleń w mniej niż 24 godziny!
Joe Z.
18
Mój Boże, Victor, twoje pudełko About jest takie smutne ... wszyscy mamy swoje wzloty i upadki, ale nie powinieneś się bić, człowieku. Jesteś teraz bohaterem dla Code Golfers wszędzie!
SimonT
4
Jestem zaskoczony, nikt nie zaproponował rozwiązanie oparte na sen sortowania jeszcze
Frank Farmer

Odpowiedzi:

178

Czasami społeczność tutaj nie lubi pomagać w odrabianiu prac domowych. Dlatego dostajesz tyle żartów. Ale lubię pomagać. Oto kompletne rozwiązanie w „C” (ponieważ zakładam, że chcesz nauczyć się „programowania”, a nie „skryptowania” w Javie lub Ruby). Zawarłem wiele wskazówek, które chciałbym wiedzieć, kiedy uczyłem się po raz pierwszy

#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
źródło
32
prawie wszystkie porady są błędne i po prostu pytają o listę wejściową, dopóki nie wprowadzisz jej już posortowanej.
AShelly,
47
+1, dla 1st, 2th, 3th, 4th...operatora i downto - bardzo zaawansowane techniki programowania C.
Kaya
5
Należy użyć sscanf(input, "%5s", &input[0]), w przeciwnym razie podczas analizowania danych wejściowych mogą wystąpić błędy przepełnienia. Dane wejściowe należy zadeklarować char input[sizeof(int)+1], aby zapewnić zgodność wsteczną z systemami 64-bitowymi.
sh1
12
i==1?"st":"th"hahaha ...
Guy Sirton
15
Java ma wyrzucanie elementów bezużytecznych. Dlatego Java jest przeznaczona do „skryptowania”, a nie do prawdziwego programowania. To podstawowa CS101. (tak mówi troll).
AShelly
181

Oto java. Jest to całkowite oszustwo, niedopuszczalne i niemożliwe do naprawienia, ponieważ tworzy bazę danych MySQL, wstawia tam liczbę, dokonuje wyboru za pomocą klauzuli ORDER BY i wyświetla liczby podane przez MySQL. W rzeczywistości to MySQL dokonuje sortowania, a nie program.

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
źródło
103
To w rzeczywistości trochę za blisko domu, na co wielu programistów Java uważa akceptowalne dopasowanie rozwiązania do specyfikacji !!
Dr. Rebmu,
10
Weź również pod uwagę przypadek, w którym musisz posortować bardzo dużą liczbę obiektów. Sortowanie ich „poza programem” w bazie danych jest wykonalnym rozwiązaniem.
Viktor Seifert,
40
Za mało abstrakcji tutaj. Potrzebujesz co najmniej 10 interfejsów, 20 implementacji, wyliczeń, testów jednostkowych, testów zasięgu, Maven, testów integracyjnych, próbnych ...
Naftuli Kay
6
@NaftuliTzviKay Powinniśmy stworzyć MySQLSortEnterpriseEdition, aby zrealizować Twój pomysł. Czy Victor wyrazi zgodę na licencję GPL na kod tutaj, abyśmy mogli zacząć?
Joe Z.
14
@JoeZ. Tak, w mojej odpowiedzi brakuje komentarzy na temat modelu licencjonowania i powinienem skłonić użytkownika do zaakceptowania umowy EULA na początku programu. Ale ponieważ daję go leniwemu OP, jest darmowy do użytku niekomercyjnego, w tym przydatny do tworzenia długo oczekiwanego premium MySQLSortEnterpriseEdidtion.
Victor Stafusa,
142

C # - Nie ma zabójstwa jak przesada

Po pierwsze, drogi GiMmEtHaCoDeZ, spróbujmy rozbić twoje zadanie:

  1. Przeczytaj liczby
  2. Sortuj je
  3. Wyjście posortowanych liczb.

Ponieważ „Dziel i rządź” jest bardzo ważną strategią podczas pracy z problemami z oprogramowaniem, rozwiążmy je pojedynczo

1. Czytanie

Kolejną ważną kwestią w oprogramowaniu jest wszechstronność. Ponieważ nie jest określone, w jaki sposób użytkownik będzie wprowadzał liczby, może się to zdarzyć za pośrednictwem konsoli, pliku, usługi internetowej itp. Może nawet jakaś metoda, o której obecnie nie możemy myśleć. Dlatego ważne jest, aby nasze rozwiązanie było w stanie pomieścić różne rodzaje danych wejściowych. Powiedzmy, że najłatwiejszym sposobem na osiągnięcie tego jest wyodrębnienie ważnej części interfejsu

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

  DoubleArrayReaderType Type {get;}
}

gdzie DoubleArrayReaderTypepodano wyliczenie z

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

Ważne jest również, aby oprogramowanie było testowalne od podstaw, aby implementacja interfejsu była możliwa

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

Następnie logicznym pytaniem jest, skąd będziemy wiedzieć, jak załadować odpowiedni IDoubleArrayReaderkod do kodu. To proste, o ile korzystamy z prostej fabryki:

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

Zauważ, że używamy refleksji do ładowania wszystkich aktywnych czytników, więc wszelkie przyszłe rozszerzenia będą automatycznie dostępne Teraz, w głównej części naszego kodu, po prostu:

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

2. Przetwarzanie (sortowanie)

Teraz musimy przetworzyć, tzn. Posortować uzyskane liczby. Zauważ, że kroki są całkowicie niezależne od siebie, więc dla podsystemu sortowania nie ma znaczenia, w jaki sposób wprowadzono liczby. Ponadto zachowanie podczas sortowania również może ulec zmianie, np. Może być konieczne wprowadzenie bardziej wydajnego algorytmu sortowania. Oczywiście wyodrębnimy żądane zachowanie przetwarzania w interfejsie:

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

  DoubleArrayProcessorType Type {get;}
}

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

A zachowanie sortowania po prostu zaimplementuje interfejs:

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

Oczywiście potrzebujemy fabryki do ładowania instancji przetwarzania i zarządzania nimi.

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. Zapis wyników

Nie ma tu wiele do powiedzenia, ponieważ jest to proces, który odzwierciedla dane wejściowe. W rzeczywistości możemy połączyć fabryki czytania i pisania w jeden DoubleArrayInputOutputFactory, jak poniżej:

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

}

Kładąc wszystko razem

Wreszcie nasz główny program wykorzysta całą tę wspaniałość, którą już zbudowaliśmy, więc kod będzie po prostu:

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

gdzie na przykład możemy zdefiniować reader, writera processorza pomocą

IDoubleArrayReader reader = DoubleArrayInputOutputFactory.CreateDoubleArrayReader(DoubleArrayReaderType.MockService);
IDoubleArrayProcessor processor = DoubleArrayProcessorFactory.CreateDoubleArrayProcessor(DoubleArrayProcessorType.Sorter);
IDoubleArrayWriter writer = DoubleArrayInputOutputFactory.CreateDoubleArrayWriter(DoubleArrayWriterType.Console);
SWeko
źródło
49
Lol, ListSort Enterprise Edition © :-P +1
Klamka
14
+1 za szalone podkręcanie. Sugeruję, abyś podzielił swoją odpowiedź na 3 lub więcej odpowiedzi „modułowych”, abym mógł dać +1 osobno
greggo
15
A wisienka na górze polega na tym, że faktycznie używa sortowania bibliotecznego :) Jest to całkowicie
zgodne
9
To było piękne.
Andrew
7
Użycie DI po prostu pomyli OP, ponieważ jest to tylko szybki przykład.
SWeko
132

Jeszcze bardziej dosłowna interpretacja:

echo " aaehrrty"

to znaczy „posortowana” tablica.

RBerteig
źródło
5
Przyszedłem tutaj, aby to opublikować.
Quuxplusone
5
zapisz jako plik sort.shi zadzwoń jakosh sort.sh "an array of doubles"
Kyss Tao
Myślę, że przegapiłeś „użytkownik wprowadza tablicę podwójnych”.
Dukeling
1
@Dukeling właśnie o to komentuje Kyss Tao. "an array of doubles"można przekazać do skryptu jako argument wiersza polecenia.
AJMansfield
108

Perl

Ze wszystkich rzeczy, które zrobiłem dla CodeGolf.SE, zajęło to chyba najwięcej czasu, przynajmniej kilka godzin.

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

Dane wejściowe mają formę, [2,4,5,7,7,3]a dane wyjściowe mają formę [2,3,4,5,7,7].

Nie mam teraz czasu na wyjaśnienia ... wrócę później.

W każdym razie w Perlu istnieje coś takiego jak tablica anonimowa. Jest to tablica, ale nie ma nazwy. Wiemy jednak, że jest to odniesienie (lokalizacja pamięci). Szereg liczb w nawiasach kwadratowych tworzy anonimową tablicę i zwraca odwołanie do niej.

Ta odpowiedź składa się z szeregu anonimowych tablic, do których odniesienia są przechowywane @_. Dane wejściowe są przekształcane w anonimową tablicę. Następnie tworzymy inne anonimowe tablice, z których każdy element jest odniesieniem do elementu z poprzedniej tablicy. Zamiast sortować elementy w tablicy, sortujemy wskaźniki do elementów w tej tablicy. Ponadto tworzymy nową tablicę dla każdego kroku (i więcej) w operacji sortowania.

PhiNotPi
źródło
3
zło! zło! zło!
DGM
56
mniej więcej tak odczytywalny jak jakikolwiek inny skrypt Perla dla mnie :)
Corey Goldberg
6
@swelljoe Właściwie $_to pusty ciąg w tym momencie. Zapisałem pożądaną moc wyjściową $\ , która jest separatorem rekordów wyjściowych.
PhiNotPi
4
@Andy proste. "Jak to działa?"
John Dvorak
1
a wszystkie zmienne tworzone przez użytkowników mają ładne nazwy zgodne ze wszystkimi możliwymi do przyjęcia konwencjami
Hagen von Eitzen,
80

Pyton

Daje użytkownikowi posortowaną tablicę, usuwając z tablicy wejściowej wszystkie elementy, które nie są posortowane.

import sys

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

Algorytm przechodzi przez listę, dodając tylko każdy element, jeśli nie sprawi, że lista nie będzie nieposortowana. Tak więc wynik jest posortowaną listą, a nie taką, która zawiera wszystkie elementy oryginalnej listy. Jeśli op tylko sprawdzi, czy lista jest posortowana, może nie zauważyć, że w danych wyjściowych brakuje wartości.

Winston Ewert
źródło
1
Przed opublikowaniem własnych zapoznaj się z innymi odpowiedziami. Powinieneś dodać nazwę swojego języka. Aby odpowiedzieć na to pytanie, musisz również krótko wyjaśnić, co robisz, aby trollować PO.
Wasi
5
Hehe, ten naprawdę mnie rozśmieszył. W każdym razie zgadzam się, że nieco lepsze wyjaśnienie byłoby pomocne.
oconnor0
2
Czy podwójne wezwanie do sys.stdin.read()literówki lub części prawdziwej odpowiedzi na trolling? Z pewnością frustrowałoby OP, aby podać tablicę jako dane wejściowe i nadal czekać na wynik ...
Bakuriu
Wow, to zło w porządku.
Sylverdrag,
13
O(n)Algorytm sortowania. Miły.
ejrb
65

Bash, 54 znaki

Wiele odpowiedzi przy użyciu powolnych, niewydajnych języków, takich jak C i Python ... Przyspieszmy trochę, oferując rozwiązanie dla wszystkich języków skryptowych: Bash.

Wiem, co myślisz - Bash nie jest w stanie poradzić sobie nawet z arytmetyką zmiennoprzecinkową, więc jak to będzie sortować, prawda? Cóż, oto moja implementacja potężnego algorytmu 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."

Program jest wyposażony w dane wejściowe jako argumenty wiersza poleceń. Przykładowy przebieg:

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

Ma to tę zaletę, że być może jest najkrótszym ze wszystkich działających algorytmów tutaj przedstawionych. Zgadza się - jedna potężna linia bash , wykorzystująca tylko wbudowane bash i nie wywołująca żadnych zewnętrznych plików binarnych (to znaczy, jeśli nie liczymy czysto opcjonalnego pełnego wyjścia). W przeciwieństwie do bogosortów, jego czas działania jest deterministyczny.

Wskazówka: skuteczną optymalizacją jest podzielenie liczb wejściowych przez współczynnik przed sortowaniem. Wdrożenie należy do czytelnika.

Edytować:

Skrócona wersja golfowa z 54 znakami i mniej ładnym nadrukiem:

#!/bin/sh
for i in $@;do echo $(sleep $i)$i&done;wait
Zamieszki
źródło
11
Trolling 1: Algorytm działa, ale jest oczywiście potencjalnie bardzo powolny - odradza wątek dla każdej liczby, śpi przez tę liczbę sekund przed wyprowadzeniem liczby (co jest w tej kolejności). Trolling 2: Dodatkowo większość kodu jest wydawana na napisanie miłego komentarza o tym, ile wątków się pojawia i niepotrzebnie czyta i analizuje informacje o procesorze systemu tylko ze względu na dodatkowe pełne informacje wyjściowe. Trolling 3: Na końcu wyświetla „posortowaną tablicę”, która wydaje się być zrobiona. Trolling 4: Użytkownik nie może anulować „sortowania”, naciskając ctrl-c.
Riot
4
5. Działa tylko na GNU / Linux , ze względu na użycie /proc/cpuinfo.
kps11346
5
Nawiasem
8
To jest niesamowite. Nie potrafię nawet wyrazić, jakie to niesamowite. Zastanawiam się nad użyciem tego aktywnie, ponieważ DLACZEGO NIE.
4
Naprawdę mam gdzieś taką wersję w produkcji. Ale w tej sytuacji czas wykonywania procesu jest ważny, więc to moja wymówka ...
Riot
64

JavaScript ma wbudowaną sort()funkcję, możesz go używać w następujący sposób:

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

... och, całkowicie zapomniałem wspomnieć, sortuje się w porządku leksykograficznym, tj . 10 < 9i 9 < -100. Prawdopodobnie i tak tego oczekujesz.

Aleksiej Lebiediew
źródło
8
To jeszcze lepsze, ponieważ jest to funkcja wbudowana.
Wayne Werner
62

(jPL) jQuery Programming Language

W tym celu musisz użyć jQuery. Proste rozwiązanie tego problemu jest następujące:

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
źródło
72
„-1 za mało jQuery”
grc 27.12.13
55
Szczególnie podoba mi się to, że tak naprawdę nie używa jQuery.
KRyan
8
-1 Nazwy tablic muszą zawierać notację węgierską, w szczególności obiekty jQuery oznaczane za pomocą $, tablice za pomocą ai wyniki window.promptas p.
Qantas 94 Heavy
2
„Podstępna część” jest elegancka. OP, staraj się kiedyś mieć tego rodzaju strukturę kodu.
Chris Barker,
2
To F'n Doble „walidacja” LOOOOOOOOOOOOL omg omg dzień zrobione! edytowano dla mniejszych limitów
HC_
54

do

To rozwiązanie łączy zwięzłość i dostęp na poziomie systemu operacyjnego zapewniany przez C z potężnymi komponentami oprogramowania wielokrotnego użytku w 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
źródło
4
Lub „scenariusz”: #!/usr/bin/sort.
Ślimak mechaniczny
54

Rubin

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

Dość oczywiste.

Lub wymagać, aby dane wejściowe faktycznie były „tablicą podwójnych”:

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

Nie używać gets.chompdla dodatkowego zła. Również używanie wyrażenia regularnego po trailing do, czego nawet nie wiedziałem, że możesz zrobić (dzięki Jan Dvorak), aby jeszcze bardziej pomylić OP!

Klamka
źródło
4
Rozwijając ten pomysł, wielokrotnie prosiłem o dane wejściowe, dopóki użytkownik nie wprowadzi ciągu an array of doubles.
Wrzlprmft,
@Wrz Ok, gotowe :-)
Klamka
2
To bardzo wspaniałe, ponieważ słaba OP będzie musiała wymyślić, jak pozbyć się nowej linii (ponieważ używasz getszamiast gets.chomp).
wchargin
@WChargin Tak, miałem to w pierwszej wersji (patrz historia wersji), ale usunąłem ją, aby była jeszcze bardziej zła>: D EDYCJA: Och, czekaj, nieważne, to była moja druga odpowiedź. Zmienię ten :-)
Klamka
1
+1 Utworzyłem tutaj konto, żeby powiedzieć, że właśnie tak bym mu odpowiedział! Kocham to!
DGM
44

Python 3.3

Jasne, oto najprostszy program w języku Python, który może sortować tablicę podaną jako literał listy na 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)

Niestety działa tylko w python3.3 +, ponieważ używa yield fromwyrażenia. Kod powinien być dość zrozumiały, więc nie powinieneś mieć żadnych problemów z przekazaniem go swojemu profesorowi.


Trolling polega na zapewnieniu idealnie działającego rozwiązania, które robi dokładnie to, co zamierzał OP, ale w sposób, który:

  • niemożliwe do zrozumienia (przez początkującego)
  • niemożliwe do przekazania nauczycielowi, ponieważ:
    • OP nie może tego zrozumieć
    • nawet gdyby mógł, nauczyciel nie miałby czasu na rozszyfrowanie, aby to zrozumieć
  • przerażające dla naiwnego początkującego, który może uważać, że programowanie jest dla niego zbyt trudne

Podsumowując, ta odpowiedź znacznie zwiększyłaby frustrację ucznia wyśmiewającego swoje prośby z całkowicie poprawnymi odpowiedziami z pewnego punktu widzenia.


(Nie czytaj, jeśli zastanawiasz się nad zrozumieniem powyższego kodu)

Muszę dodać, że trollowanie jest również zwiększone przez fakt, że zaimplementowany algorytm sortowania jest w rzeczywistości

sortowanie bąbelkowe! ... które z pewnością można wdrożyć w sposób zrozumiały dla nawet PO. Nie jest to niejasny algorytm per se, tylko dobre zaciemnienie kodu czegoś, co w przeciwnym razie OP mógłby doskonale zrozumieć.

Bakuriu
źródło
3
Myślę, że przydałoby się więcej wyjaśnień; co teraz robisz z Inferno ?
KRyan
1
Wow, możesz robić w Pythonie nazwy zmiennych innych niż ascii? nie wiedziałem ...
kratenko
1
@kratenko From python3 +. W python2 interpreter przyjmuje kodowanie ASCII i spowodowałoby błąd. W python3 interpreter przyjmuje kodowanie UTF-8 i akceptuje wszystkie znaki, które są „literami” według właściwości Unicode dla identyfikatorów.
Bakuriu
3
@KRyan: Najwyraźniej stosuje metodę sortowania, której używa Hell, aby wprowadzić ludzi do dziewięciu kręgów.
Joe Z.
10
O mój Boże… +1 za è.
Sean Allred,
41

C - Wolny, trudny w użyciu, niedopuszczalny styl kodowania

Sam algorytm sortowania nazywany jest spowolnieniem i ma najlepszą złożoność przypadków (simpleksowość) wynoszącą około n ^ (log n / 2) . Algorytm został opublikowany przez Andrieja Brodera i Jorge Stolfi w ich wspaniałej pracy „Algorytmy pesymalne i analiza simpleksowości”, którą gorąco polecam dla dobrego śmiechu ORAZ do przemyślenia.

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

Jednak samo sortowanie jest bezużyteczne, dlatego potrzebujemy sposobu na wprowadzenie danych, które chcą posortować. Parsowanie podwójnych jest bólem, więc dlaczego nie wprowadzić ich bajt po bajcie.

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

Aby udowodnić, że to działa:

 $ 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

W końcu mamy:

  • Najwolniejszy deterministyczny algorytm sortowania, o którym wiem
  • Ciche zakodowane ograniczenia długości listy
  • Absolutnie okropne dane wejściowe, mógłbym również sprawić, by dane wyjściowe były podobne, ale myślę, że w ten sposób jest zabawniej.
    • Zastanów się: musisz wiedzieć, jaki endianess ma twój komputer, aby korzystać z programu.
    • Nie można również wprowadzić 0 (-0 jest w porządku)
  • Arytmetyka wskaźników i praktycznie nie ma znaczenia dla typów, ponieważ wskaźniki są rzucane w dowolny sposób
shiona
źródło
To ma niezdefiniowane zachowanie dla wszystkich danych wejściowych większych niż 7 bajtów. Nie do przyjęcia odpowiedź.
Michael Spencer,
1
Uwielbiam artykuł „Algorytmy pesymalne”; dzięki.
Ryan
„Najwolniejszy deterministyczny algorytm sortowania, o którym wiem” - prawdopodobnie najwolniejszy deterministyczny algorytm sortowania. To jest sedno artykułu, AFAIR.
Konrad Rudolph
@MichaelSpencer Chcesz opracować? Podałem przykład o wielkości wejściowej 24 bajtów, a wynik jest taki, jakiego można się spodziewać (myślę, że tutaj brakuje mi żartu).
shiona
2
@Sasho, ale bogo-sort ma najlepszy czas działania \ Omega (n) (porównania n-1, 0 operacji). To o wiele szybsze, jang. gorzej niż \ Omega (n ^ (log n / 2)).
shiona
39

Ruby, zły Bogosort! (Bonus: bogosort według danych wprowadzonych przez użytkownika)

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

„Złe” zwroty akcji:

  • oczywiście działa naprawdę naprawdę bardzo bardzo bardzo powoli
  • używa porównania ciągów, więc 10 jest mniejsze niż 2. Można łatwo naprawić za pomocą .map &:to_fdołączenia do drugiej linii, ale OP może tego nie wiedzieć
  • nieużywanie, chompwięc ostatni numer ma na końcu tajemniczą nową linię
  • nieużywany, stripwięc wokół liczb występuje tajemnicza biała spacja, jeśli wprowadzane są z odstępami wokół przecinków (np. spacja w 1.5, 2)

A może bogosortowanie według danych wprowadzonych przez użytkownika ? >: 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 * ","
Klamka
źródło
Dlaczego nie bogobogosort ? (biegnie w osobliwym czasie O (n * (n!) ^ n))
wchargin
@Wchargin Mogę to rozważyć :-) możesz być zainteresowany moją ostatnią edycją! (Przepraszam, że jestem powolny, aktualnie rozmawiam przez telefon, ponieważ nie mogę uzyskać dostępu do komputera :-P)
Klamka
37

COBOL

Pewnie! „Nawet małpa może to zrobić!”

Oto prosty program COBOL, który posortuje dane wejściowe dla Ciebie. Przeczytaj komentarze, aby zobaczyć, jak dokładnie jest to trywialne i rozszerzalne. Prawdziwymi zaletami tego jest to, że jest wypróbowanym i prawdziwym mechanizmem, nie opiera się na nowych i stosunkowo niesprawdzonych językach, takich jak Java i cokolwiek opartego na sieci Web lub od Microsoft. Kompiluje się naprawdę skutecznie, a takie procedury są stosowane przez najbardziej udane firmy finansowe z listy Fortune500 i innych liderów branży. Ten kod został sprawdzony przez wielu ekspertów i jest uznawany za doskonały mechanizm sortowania.

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
źródło
6
Tylko Ty użyłbyś COBOL jako odpowiedzi na to pytanie. +1
syb0rg
5
Ach, świeży zapach kart
ponczowych
3
@EbenezerSklivvze - LOL. Kiedyś wyjąłem kartę perforowaną, której używałem jako zakładkę, kiedy mój profesor z college'u opowiadał klasie o starych kartach perforowanych. Był wystarczająco pływający (to było w 1994 roku :). Nie sądzę, że wielu moich współczesnych kiedykolwiek widziało cały pokład ...
DVK
30

OP nigdy nie powiedział, JAK je posortować ... ani jaka jest jego definicja podwójności. Zakładając, że typ danych jest doubleinterpretowany jako duplikat . Za pomocą JavaScript tutaj.

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

Wynik: kolejność naprzemienna [4, 11, 4, 9, 5, 7, 6, 7]

Kiruse
źródło
4
„Zakładając, że typ danych jest podwójny, ale interpretuje go jako duplikat”. Tylko prawdziwie geniusz mógłby tak myśleć. Po prostu genialne!
Felipe Miosso,
@FelipeMiosso Szczerze mówiąc, nie jestem pewien, czy jesteś po prostu sarkastyczny ...
Kiruse
1
Haha ... Byłem sarkastyczny. Wiem, że są ludzie, którzy naprawdę tak myślą. W każdym razie ... twoja odpowiedź była niesamowita! Śmiałem się dużo.
Felipe Miosso,
@FelipeMiosso Cieszę się, że mogę się rozśmieszyć. ;)
Kiruse,
console.log wszystko!
Emil Vikström,
28

PHP

Oto pełna implementacja z obsługą błędów. Jest najszybszy dla każdego 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
źródło
25
do
{
}
while(next_permutation(begin(ar), end(ar)));

Następna permutacja w C ++ działa, zwracając true, gdy tablica jest sortowana, a false w przeciwnym razie (po permutacji). Więc powinieneś posortować tablicę, a następnie użyć jej do-while jak powyżej (aby utworzyło pełne koło z powrotem do posortowanej tablicy).

użytkownik974006
źródło
+1 Myślałem o użyciu next_permutationdla mojej odpowiedzi, ale jest to o wiele czystsze niż to, co miałem na myśli.
jliv902
25

[rozwiązanie przez punktowe błędne ukierunkowanie]

Proszę przeczytać odpowiednią normę, IEC 60559: 1989 Specyfikacja binarnej arytmetyki zmiennoprzecinkowej dla systemów mikroprocesorowych , którą można kupić tutaj . W przypisie do §5.10 Szczegóły predykatu totalOrder zauważono, że:

totalOrder nie narzuca całkowitego uporządkowania wszystkich kodowań w formacie. W szczególności nie rozróżnia różnych kodowań tej samej reprezentacji zmiennoprzecinkowej, jak gdy jedno lub oba kodowania są niekanoniczne.

Widzimy więc, że nie można pisać kodu do sortowania podwójnych. To podchwytliwe pytanie. Ha, ha, bardzo sprytne! Powiedz profesorowi, że bardzo podoba mi się jego kurs.

[edit: nic nie wymaga ode mnie nie do przyjęcia, że problem wymaga całkowitego zamówienie]

kps11346
źródło
3
Problem polegał jednak na uporządkowaniu podwójnych. Nikt nie wymagał, aby wartości były (łącznie) w porządku. Na przykład możesz posortować tablicę na dwie liczby dodatnie i ujemne. Pytanie podwójnie cię zaskoczyło.
shiona
23

Zły JavaScript:

OP, nie chcę ci wszystkiego dawać, więc pozwolę ci dowiedzieć się, jak samemu uzyskać informacje od użytkownika (wskazówka: użyj prompt).

Gdy to zrobisz, oto funkcja, do której możesz przekazać tablicę, aby ją posortować. Musisz tylko podać tablicę, najniższą wartość w tablicy i przyrost:

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

Oto skrzypce, aby zobaczyć, jak działa w przykładzie z danymi wejściowymi użytkownika [1,5, -3,5, 12, 10, -19,5].


Uwaga: Oprócz tego, że jest mało wydajny, złożony i nierozwiązywalny dla danego problemu, będzie to szczególnie frustrujące, jeśli OP nie będzie wiedział o matematyce zmiennoprzecinkowej. Na przykład, jeśli dane wejściowe użytkownika są, [8.1, 5, -.8, 2.3, 5.6, 17.9]a OP wybierze proste wartości (tj. minimumVal=-.8I increment=.1), program będzie działał na zawsze. W związku z tym jestem obecnie dumnym posiadaczem 2 niedziałających kart przeglądarki z powodu tego właśnie problemu :)

Uwaga II: Czułem się obrzydliwy nawet pisząc powyższy kod.

Uwaga III: MWA HAHAHAHA!

Briguy37
źródło
Dobry pomysł. Musisz być fajny, gdy byłeś jeszcze początkującym programistą.
Pierre Arlaud
22

Oto aktualna odpowiedź , którą lubię w Javie:

Dodaj linię przed println, a tablica zostanie posortowana

Arrays.sort( array );

Bez wyjaśnień, myli OP , ale działa i otrzyma opinie od bardziej doświadczonych programistów.


Inna podobna odpowiedź :

Spójrz na Arrays.sort ()

Pośrednio mówi OP, aby przeprowadził własne badania, dając mu niejasną poprawną odpowiedź. Bez dalszych badań PO jest nadal zdezorientowany . Podoba mi się również, że link wskazuje na starszą dokumentację.

syb0rg
źródło
10
Jest to przydatne, a zatem warte odrzucenia.
emory
11
„Pośrednio mówi OP, aby przeprowadził własne badania, dając mu niejasną poprawną odpowiedź”, w przybliżeniu opisuje mój styl odpowiadania na StackOverflow: /
Corey Goldberg
7
„Spójrz na Arrays.sort ()” ... „Czy mogę dostać przykład, jak używać go w moim programie?” ... znakomity.
SimonT
5
+1, zwłaszcza że nasz skromny OP prawdopodobnie musi napisać coś dla siebie, co sprawi, że Array.sort () będzie dla niego całkowicie bezużyteczny.
Kevin
2
Ctrl + F -> „Czy mogę uzyskać przykład użycia go w moim programie?” = 3 wyniki.
Qix,
21

Algorytm genetyczny / metoda Monte Carlo dla problemu sortowania w JAVA

Problem sortowania znany jest komputerowo od dawna i znaleziono wiele dobrych rozwiązań. W ostatnich latach nastąpił wielki postęp w biokomputerze, a patrzenie na to, jak biologia rozwiązuje problemy, okazało się bardzo pomocne w rozwiązywaniu trudnych problemów. Ten algorytm sortowania wykorzystuje najlepsze z tych pomysłów, aby wykorzystać je do rozwiązania problemu z sortowaniem. Pomysł jest dość prosty. Zaczynasz z nieuporządkowaną tablicą i dowiadujesz się, jak już jest posortowana. Dajesz mu wynik „sortowania”, a następnie permutujesz tablicę losowym składnikiem - tak jak w biologii, gdzie nie jest jasne, jak będą wyglądać dzieci, nawet jeśli wiesz wszystko o rodzicach! To część algorytmu genetycznego. Można powiedzieć, że tworzysz potomstwo tej tablicy. Następnie zobaczysz, czy potomstwo jest lepiej posortowane niż rodzic (inaczej przeżycie najsilniejszych!). W takim przypadku kontynuujesz z nową tablicą jako punktem wyjścia do budowania następnej permutacji i tak dalej, aż tablica zostanie w pełni posortowana. Fajną rzeczą w tym podejściu jest to, że trwa krócej, jeśli tablica jest już trochę posortowana od samego początku!

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

}

Dodatki

  • Niewłaściwe użycie listy java.awt.List
  • niespójne i złe nazewnictwo zmiennych
  • całkowicie bzdury bla bla na temat biokomputerów
  • pomysłowy i niespójny język w wyjaśnieniach
  • Monte Carlo jest po prostu niewłaściwym narzędziem dla prostych problemów deterministycznych
  • niepotrzebny import
  • prawdopodobnie więcej gadżetów ...
luksch
źródło
Czy nazywanie tego GA lub Monte Carlo kolejnym poziomem trolli? Uważam, że jest to algorytm randomizowany do wspinaczki.
shiona
kojarzenie tego programu z modnymi nazwami było celowe, ale nigdy nie słyszałem o „losowym algorytmie wspinaczki na wzgórzu”… i, w szerszym znaczeniu, myślę, że GA i Monte Carlo nie są zbyt daleko, by być po prostu błędne…
luksch
19

Pyton

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

Sortowanie tablicy (lista) przez w sumie 3 rd i 5 th miejsc po przecinku.

grc
źródło
5
Niestety jest to trywialnie naprawione poprzez usunięcie wszystkiego po lambda x:i zastąpienie go x. Mimo to początkujący programista nigdy by tego nie wiedział, więc chwała!
Joe Z.
18

C ++

To działa ... ostatecznie.

Oto mój algorytm sortowania:

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

Oto pełny program:

#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
źródło
6
Twój „algorytm” wprawił mnie we łzy.
Nate
Hah, to nie jest algorytm, ponieważ nie przyznaje się go do ukończenia>: D
jmacedo
@ joxnas, w rzeczywistości w systemach, w których niedeterministyczne urządzenia losowe nie są dostępne, randomizator może faktycznie być okresowy. Wtedy zależałoby to po prostu od tego, czy zestaw możliwych permutacji dozwolonych przez randomizator obejmuje zbiór możliwych permutacji $ S_n $ dla wszystkich możliwych długości tablicy wejściowej $ n $.
błąd
Aw spodnie, zapomniałem, że LaTeX był obsługiwany tylko w TeX.SE i Math.SE. Wyobraźcie sobie te symbole w snooty italix.
błąd
18

Rozkoszuj się oczami:

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

Ten fragment kodu wyświetla tablicę i prosi użytkownika o wprowadzenie najmniejszego podwójnego pola tablicy. Następnie dodaje liczbę do listy posortowanych liczb, usuwa podwójną liczbę z tablicy i wyświetla pozostałe numery tablic.

* Błędna interpretacja: słaby punkt, ale OP nie spodziewa się, że program poprosi użytkownika o pomoc w sortowaniu.

* Oszukiwanie: użytkownik dokonuje właściwego sortowania.

* Wydajność: każda liczba macierzy wymaga obchodu serwera i użytkownik musi ręcznie znaleźć najmniejszą liczbę. Wydajność nie może być znacznie gorsza.

* Niedopuszczalne: Myślę, że mam to ubezpieczone. Powodzenia w ponownym użyciu. Najgorsze przychodzi najgorsze, użytkownik może pozbyć się 90% kodu i powtarzać w pętli, aby znaleźć najmniejsze wartości i usuwać je za każdym razem, co dałoby mu jeden z najmniej wydajnych algorytmów sortowania.

* Twórczy i zły: mówisz mi.

Sylverdrag
źródło
2
Mówisz „
rozkoszuj
3
„Zło” było częścią wymagań, prawda?
Sylverdrag,
17

Javascript Inteligentny projekt Sortuj

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
źródło
6
Kredyt, na który przypada kredyt: dangermouse.net/esoteric/intelligentdesignsort.html
wchargin
1
Nie rozumiesz, dlaczego krytykujesz inteligentny projekt w konkursie programistycznym?
khebbie
12
@khebbie Dlaczego nie?
Konrad Rudolph,
Problem polega na tym, że jeśli użytkownik jest tym, który wprowadza liczby, to byłby bardziej inteligentny od siebie. ;)
d -_- b
16

Python - wymagania # 1

Ten kod posortuje liczby podwójne w kolejności leksykograficznej, a nie w kolejności numerycznej, tworząc drzewo prefiksów cyfr, a następnie powtarzając je cyklicznie.

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

Działa na n log nczas i w rzeczywistości jest sprytnym sposobem na utrzymanie posortowanej listy w przeciwnym razie, ale niestety dla OP robi to całkowicie niewłaściwą rzecz.

Joe Z.
źródło
4
Jest również szczególnie przebiegły w tym, że jeśli wszystkie liczby mają tę samą liczbę cyfr przed kropką dziesiętną, to faktycznie będzie działać poprawnie, więc OP może nawet nie zauważyć, że sort robi coś złego, jeśli po prostu przetestuje to za pomocą danych wejściowych powiedzmy 2, 1, 3, 8, 5.
Joe Z.
14

Sortuje tablicę podwójnych. W Javie:

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

Na przykład:

[0.0, 1.5, 123]

pochodzi z nieposortowanej reprezentacji binarnej

011111111111000000000000000000000000000000000000000000000000000100000001011110110000000000000000000000000000000000000000000000

do elegancko posortowanych

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111

planetguy32
źródło
11

Potrzebuję programu, w którym użytkownik wprowadza tablicę podwójnych, a program wyświetla tablicę posortowaną. Czy możesz podać kod?

Edytuj według @kealist, myślę, że lepiej jest skomentować, aby podział wydawał się prawdopodobny. W 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

Pomijając pomysł, że tak naprawdę nie wiedzą, co to jest dublet, i mogą wierzyć, że lista dubletów była tylko zbiorem liczb pomnożonych przez dwa.

Dr. Rebmu
źródło
6
Może trzeba je zmniejszyć o połowę, ponieważ nakład jest już podwojony!
kealist
@kealist Rozważyłem to, jednak podąża za ideą, że ma miejsce „podwojenie”. Myślę, że lepiej jest mieć [2 * num].
Dr. Rebmu,
10

Celowo niezrozumienie pytania:

Stosując podejście rekurencyjne:

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

Posortowana tablica gwarantuje, że w pewnym momencie zostanie wyprowadzona, dla dowolnego rodzaju danych w tablicy, nawet dla dowolnego rodzaju sortowania, a nawet dla każdego separatora dla danych wejściowych, co czyni to podejście niezwykle elastycznym. Jego główną wadą jest to, że jest nieco powolny w przypadku dużych tablic, ale można to łatwo rozwiązać za pomocą wielowątkowości.

Valentin CLEMENT
źródło