To jest pytanie do golfa.
Wejście
Lista liczb całkowitych nieujemnych w dowolnym formacie jest najwygodniejsza.
Wynik
Ta sama lista w porządku posortowanym w dowolnym formacie jest najwygodniejsza.
Ograniczenie
- Twój kod musi działać w czasie O (n log n) czasu w najgorszym przypadku , gdzie
n
oznacza liczbę liczb na wejściu. Oznacza to, że na przykład nie ma randomizowanego szybkiego sortowania. Istnieje jednak wiele innych opcji do wyboru. - Nie używaj żadnej biblioteki sortującej / funkcji / podobnej. Nie używaj też niczego, co wykonuje większość sortowania, jak biblioteki sterty. Zasadniczo, cokolwiek wdrożysz, zaimplementuj go od zera.
Możesz zdefiniować funkcję, jeśli chcesz, ale następnie pokaż jej przykład w pełnym programie, który faktycznie działa. Powinien działać pomyślnie i szybko na wszystkich poniższych testach.
Przypadki testowe
In: [9, 8, 3, 2, 4, 6, 5, 1, 7, 0]
Out:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
In: [72, 59, 95, 68, 84]
Out:[59, 68, 72, 84, 95]
In: [2, 2, 1, 9, 3, 7, 4, 1, 6, 7]
Out:[1, 1, 2, 2, 3, 4, 6, 7, 7, 9]
In: [2397725, 1925225, 3304534, 7806949, 4487711, 8337622, 2276714, 3088926, 4274324, 667269]
Out:[667269,1925225, 2276714, 2397725,3088926, 3304534, 4274324, 4487711, 7806949, 8337622]
Twoje odpowiedzi
Podaj zaimplementowany algorytm sortowania i długość swojego rozwiązania w tytule swojej odpowiedzi.
Algorytmy sortowania czasu O (n log n)
Istnieje wiele algorytmów czasowych O (n log n). Ta tabela zawiera listę niektórych z nich.
intersect
automatyczne sortowanie tablicy. Chyba też chcesz to wykluczyć. Co powiesz naunique
(usuń duplikaty, posortuj wynik)?intersect
jest objęty „podobnym”, jeśli automatycznie sortuje tablicę. Jeśli usuniesz duplikaty, otrzymasz nieprawidłowe dane wyjściowe.Odpowiedzi:
Haskell,
878089Jest to sortowanie scalone, realizowane od dołu do góry. najpierw pakujemy każdy element do jego własnej listy, a następnie łączymy je dwa na dwa, i ponownie łączymy je dwa na dwa, dopóki nie zostanie nam jedna lista.
(%)
to funkcja scalaniaj
łączy pary na liście listr
łączy pełną listę lists
jest funkcją sortowania.Sposób użycia: Uruchom tłumacza i wprowadź
s [3,5,2,6,7]
.Edycja: sposób, w jaki wcześniej łączyłem rzeczy, nie był prawidłowy, więc aby to naprawić, potrzebowałem jeszcze 9 znaków.
źródło
main = print (s [5,3,6,8])
, która ustawi główną opcję drukowania wyniku sortowania.[]%s=s
, ponieważ jeśli pierwszy element jest[]
,(x:a)
dopasowanie nie powiedzie się, a ostatni przypadek odwróci elementy, więc sięs%[]
powiedzie.JavaScript (ES6),
195193191189188186183182179174172 bajtówTo implementacja heapsortu. Oczekuję, że ktoś wymyśli krótsze połączenie, ale podoba mi się ten: P.
Aktualizacja: R scalono pobity. Ruby dalej: D
Test (Firefox)
Pokaż fragment kodu
źródło
Python3, 132 bajty
Proste połączenie. Sporo bajtów zostało wydanych, aby upewnić się, że faktycznie działa w O (n log n), jeśli tylko algorytm , ale nie implementacja musi być O (n log n), można to skrócić:
Python3, 99 bajtów
To nie jest O (n log n), ponieważ
.pop(0)
jest O (n), co powoduje, że funkcja scalania O (n ^ 2). Ale jest to dość sztuczne, jak.pop(0)
łatwo mogło być O (1).źródło
Julia, 166 bajtów
Wywoływana jest funkcja podstawowa,
M
która wywołuje funkcję pomocnikam
. Używa sortowania scalonego , które ma O ( n log n ) jako najgorszy przypadek złożoności.Przykładowe zastosowanie:
Nie golfowany:
źródło
R, 181 bajtów, Mergesort
Wcięte, z nowymi liniami:
Przypadki testowe:
źródło
Scala, funkcja 243 bajtów (samodzielna aplikacja 315 bajtów), Mergesort
Ta odpowiedź ma być funkcją, ale może zostać rozszerzona jako samodzielna aplikacja.
Tylko funkcja (243 bajty):
Aplikacja autonomiczna (315 bajtów):
Stosowanie:
Przykładowe dane wejściowe:
Wynik:
Ograniczenia i uwagi:
Przypisanie:
m()
funkcję) zainspirowaną tą odpowiedzią: https://codereview.stackexchange.com/a/21590/28856źródło
Galaretka, 29 bajtów, sortuj według scalania
Podobnie jak odpowiedź Python w orlp, ta metoda jest używana
list.pop(0)
pod maskąO(n)
, ale implementacja jest formalnaO(n log n)
.Wypróbuj tutaj.
Wyjaśnienie
źródło
.pop(0)
jest O (n), czyniąc funkcję scalania O (n ^ 2). Ale jest to dość sztuczne, jak.pop(0)
łatwo mogło być O (1).Ḣ
zaimplementowana jako.pop(0)
.Rubinowy, 167 bajtów
Algorytm sortowania scalonego z golfem, który ma najgorszy przypadek O (n log n)
Sprawdź to tutaj!
Aby przetestować, skopiuj i wklej kod do okna, a następnie dodaj
puts f[x]
na dole, gdzie x jest tablicą z danymi wejściowymi. (Oczywiście upewnij się, że wybrałeś Ruby jako język) Na przykładputs f[[2, 2, 1, 9, 3, 7, 4, 1, 6, 7]]
źródło
Rubinowy, 297 bajtów
Scal sortowanie. Kompletny program zamiast funkcji. Wymaga dwóch argumentów w czasie wykonywania: pliku wejściowego i pliku wyjściowego, każdy z jednym elementem w wierszu.
źródło
$stdin.readlines
już jest mniej niż bajtyopen(ARGV[0]).readlines
, to samo zputs
nadopen(ARGV[1],"w"){|f|f.puts
if $0==__FILE__
są naprawdę niepotrzebne w golfie kodowym. Możesz także skondensować, zastępując każdą;
z nową linią - to ta sama liczba bajtów i (prawdopodobnie) usuwa przewijanie kodu w poziomie. Polecam również sprawdzenie wskazówek dotyczących gry w golfa w Ruby .