Классический код сортировки по гольфу

11

Это вопрос кода-гольфа.

вход

Список неотрицательных целых чисел в любом формате является наиболее удобным.

Выход

Один и тот же список в отсортированном порядке в любом удобном формате.

ограничение

  • Ваш код должен выполняться за O (n log n) в худшем случае, когда nчисло входных чисел. Это означает, что рандомизированная быстрая сортировка отсутствует, например. Однако есть много других вариантов на выбор.
  • Не используйте сортировочную библиотеку / функцию / подобное. Также не используйте ничего, что выполняет большую часть работы по сортировке, как библиотека кучи. В принципе, что бы вы ни реализовывали, реализуйте это с нуля.

Вы можете определить функцию, если хотите, но затем, пожалуйста, покажите пример ее в действующей полной программе. Он должен работать успешно и быстро на всех тестовых примерах ниже.

Контрольные примеры

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]

Ваши ответы

Пожалуйста, укажите алгоритм сортировки, который вы реализовали, и длину вашего решения в заголовке вашего ответа.

O (n log n) алгоритмы сортировки по времени

Существует много O (n log n) временных алгоритмов. Эта таблица содержит список некоторых из них.


источник
Некоторые функции набора, такие как intersectавтоматическая сортировка массива. Я полагаю, вы тоже хотите это исключить. Как насчет unique(удалить дубликаты, отсортировать результат)?
Луис Мендо
@DonMuesli Я делаю .. Я думаю, intersectподпадает под "аналог", если он автоматически сортирует массив. Если вы удалите дубликаты, вы получите неправильный вывод.
Что касается неправильного ввода, оставьте это мне :-) Можно ли тогда использовать "удалить дубликаты и отсортировать"?
Луис Мендо
3
Nitpick: 0 не является положительным целым числом. (Под входом )
мензурка
1
Мне нравится, как только этот вопрос имеет какое-либо отношение к производительности, все уходят от языков игры в гольф, хотя это все еще код-гольф, и самое короткое решение все равно победит.
Cyoce

Ответы:

8

Хаскелл, 87 80 89

s%[]=s
(x:a)%q|x<=q!!0=x:a%q
p%q=q%p
j(x:y:s)=x%y:j s
j a=a
r[x]=x
r s=r$j s
s=r.map(:[])

Это сортировка слиянием, реализованная снизу вверх. сначала мы упаковываем каждый элемент в его собственный список, а затем объединяем их два на два и снова объединяем их два на два, пока у нас не останется один список.

(%)это функция
jслияния пар слияния в списке списков
rслияния полный список списков
sявляется функцией сортировки.

Использование: Запустите переводчик и введите s [3,5,2,6,7].

Изменить: способ, которым я слил вещи раньше, был неправильным порядком, поэтому, чтобы исправить это, мне нужно было еще 9 символов.

гордый хаскеллер
источник
1
@Lembik, если вы хотите протестировать программу и не хотите устанавливать Haskell, вы можете использовать ideone и добавить строку наподобие main = print (s [5,3,6,8]), которая установит main для печати результата сортировки.
гордый haskeller
Я думаю, что вам не нужно []%s=s, потому что, если первый элемент [], (x:a)совпадение не удается, и последний случай переворачивает элементы, так что это s%[]успешно.
Ними
Ты победитель! Единственный ответ, использующий меньше байтов, не выполнялся в O (n log n).
@Lembik Правильно, я забыл, что ответ Jelly не соответствует.
гордый haskeller
1
Теперь это кажется :)
5

JavaScript (ES6), 195 193 191 189 188 186 183 182 179 174 172 байта

Это реализация heapsort. Я ожидаю, что кто-то предложит более короткую сортировку, но мне нравится эта: P

Обновление: R mergesort избит. Рубин до следующего: D

S=l=>{e=l.length
W=(a,b)=>[l[a],l[b]]=[l[b],l[a]]
D=s=>{for(;(c=s*2+1)<e;s=r<s?s:e)s=l[r=s]<l[c]?c:s,W(r,s=++c<e&&l[s]<l[c]?c:s)}
for(s=e>>1;s;)D(--s)
for(;--e;D(0))W(0,e)}

Тест (Firefox)

PurkkaKoodari
источник
Я бы с удовольствием написал ответ с использованием heapsort, но с Haskell это не очень хорошо работает. Моей следующей попыткой будет JS, но вы сделали это. Возможно я все еще сделаю это все же. Idk
гордый haskeller
@proudhaskeller Ах да .. я только что посмотрел stackoverflow.com/a/2186785/2179021 .
3

Python3, 132 байта

def S(l):
 if len(l)<2:return l
 a,b,o=S(l[::2]),S(l[1::2]),[]
 while a and b:o.append([a,b][a[-1]<b[-1]].pop())
 return a+b+o[::-1]

Простая сортировка. Много байтов было потрачено, чтобы убедиться, что это действительно выполняется в O (n log n), если только алгоритм , но не реализация должна быть O (n log n), это можно сократить:

Python3, 99 байт

def m(a,b):
 while a+b:yield[a,b][a<b].pop(0)
S=lambda l:l[1:]and list(m(S(l[::2]),S(l[1::2])))or l

Это не O (n log n), потому что .pop(0)это O (n), что делает функцию слияния O (n ^ 2). Но это довольно искусственно, так как это .pop(0)легко могло быть O (1).

orlp
источник
Спасибо тебе за это. Я определенно имел в виду алгоритм и реализацию должны быть O (n log n).
Чтобы было понятно, это означает, что версия 132 в порядке, но 99-байтовая версия не соответствует.
2

Юлия, 166 байт

m(a,b,j=1,k=1,L=endof)=[(j<=L(a)&&k<=L(b)&&a[j]<b[k])||k>L(b)?a[(j+=1)-1]:b[(k+=1)-1]for i=1:L([a;b])]
M(x,n=endof(x))=n>1?m(M(x[1:(q=ceil(Int,n÷2))]),M(x[q+1:n])):x

Вызывается основная функция, Mкоторая вызывает вспомогательную функцию m. Он использует сортировку слиянием , которая имеет O ( n log n ) в качестве наихудшего варианта сложности.

Пример использования:

x = [9, 8, 3, 2, 4, 6, 5, 1, 7, 0]
println(M(x))              # prints [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
println(M(x) == sort(x))   # prints true

Ungolfed:

function m(a, b, i=1, k=1, L=endof)
    return [(j <= L(a) && k <= L(b) && a[j] < b[k]) || k > L(b) ?
            a[(j+=1)-1] : b[(k+=1)-1] for i = 1:L([a; b])]
end

function M(x, n=endof(x))
    q = ceil(Int, n÷2)
    return n > 1 ? m(M(x[1:q]), M([q+1:n])) : x
end
Алекс А.
источник
Рад видеть Джулию здесь. Теперь нам нужно NIM и ржавчина тоже :)
1
@Lembik Я думаю, что Sp3000 и Doorknob - наши постоянные эксперты Nim и Rust соответственно. Надеюсь, они тоже присоединятся к веселью. ;)
Алекс А.
2

R, 181 байт, Mergesort

L=length;s=function(S)if(L(S)<2){S}else{h=1:(L(S)/2);A=s(S[h]);B=s(S[-h]);Z=c();if(A[L(A)]>B[1])while(L(A)&L(B))if(A[1]<B[1]){Z=c(Z,A[1]);A=A[-1]}else{Z=c(Z,B[1]);B=B[-1]};c(Z,A,B)}

С отступом, с новыми строками:

L=length
s=function(S)
    if(L(S)<2){
        S
    }else{
        h=1:(L(S)/2)
        A=s(S[h])
        B=s(S[-h])
        Z=c()
        if(A[L(A)]>B[1])
#Merge helper function incorporated from here ...
            while(L(A)&L(B))
                if(A[1]<B[1]){
                    Z=c(Z,A[1])
                    A=A[-1]
                }else{
                    Z=c(Z,B[1])
                    B=B[-1]
                }
#...to here. Following line both finishes merge function and handles 'else' case:
        c(Z,A,B)
    }

Тестовые случаи:

> L=length;s=function(S)if(L(S)<2){S}else{h=1:(L(S)/2);A=s(S[h]);B=s(S[-h]);Z=c();if(A[L(A)]>B[1])while(L(A)&L(B))if(A[1]<B[1]){Z=c(Z,A[1]);A=A[-1]}else{Z=c(Z,B[1]);B=B[-1]};c(Z,A,B)}
> s(c(2397725, 1925225, 3304534, 7806949, 4487711, 8337622, 2276714, 3088926, 4274324,  667269))
 [1]  667269 1925225 2276714 2397725 3088926 3304534 4274324 4487711 7806949 8337622
> s(c(2, 2, 1, 9, 3, 7, 4, 1, 6, 7))
 [1] 1 1 2 2 3 4 6 7 7 9
> s(c(72, 59, 95, 68, 84))
 [1] 59 68 72 84 95
> s(c(9, 8, 3, 2, 4, 6, 5, 1, 7, 0))
 [1] 0 1 2 3 4 5 6 7 8 9
plannapus
источник
2

Scala, функция 243 байта (автономное приложение 315 байтов), Mergesort

Этот ответ предназначен для использования в качестве функции, но его можно расширить, чтобы он стал отдельным приложением.

Только для функции (243 байта):

object G{
type S=Stream[Int]
def m(f:(S,S)):S=f match{
case(x#::a,b@(y#::_))if x<=y=>x#::m(a,b)
case(a,y#::b)=>y#::m(a,b)
case(a,Empty)=>a
case(_,b)=>b}
def s(a:S):S=if(a.length>1)((q:S,w:S)=>m(s(q),s(w))).tupled(a.splitAt(a.length/2))else a
}

Автономное приложение (315 байт):

object G extends App{
type S=Stream[Int]
def m(f:(S,S)):S=f match{
case(x#::a,b@(y#::_))if x<=y=>x#::m(a,b)
case(a,y#::b)=>y#::m(a,b)
case(a,Empty)=>a
case(_,b)=>b}
def s(a:S):S=if(a.length>1)((q:S,w:S)=>m(s(q),s(w))).tupled(a.splitAt(a.length/2))else a
println(s(args(0).split(",").map(_.toInt).toStream).toList)
}

Использование:

Функция: G.s(List(**[Paste your array here]**).toStream).toList

Заявка: sbt "run **[Paste your array here]**"

Пример ввода:

scala> G.s(List(10,2,120,1,8,3).toStream).toList

(OR)

$ sbt "run 5423,123,24,563,65,2,3,764"

Выход:

res1: List [Int] = List (1, 2, 3, 8, 10, 120)

ИЛИ ЖЕ

Список (2, 3, 24, 65, 123, 563, 764, 5423)

Ограничения и соображения:

  • Требуется скаляр (очень распространенная библиотека, здесь не используется для сортировки)
  • Работает на 100% (ничего не меняется!)

Attribution:

  • Реализация слияния ( m()функция), вдохновленная этим ответом: /codereview//a/21590/28856
Руслан
источник
2

Желе, 29 байт, сортировка слиянием

Как ответ на Python orlp, это использование list.pop(0)под капотом, который O(n), однако реализация формально O(n log n).

ṛð>ṛḢð¡Ḣ;ñ
ç;ȧ?
s2Z߀ç/µL>1µ¡

Попробуй это здесь.

объяснение

               Define f(x, y):    (merge helper)
                 Implicitly store x in α.
ṛ    ð¡          Replace it with y this many times:
 ð>ṛḢ              (x > y)[0].
       Ḣ         Pop the first element off that list (either x or y).
        ;ñ       Append it to g(x, y).

               Define g(x, y):    (merge)
  ȧ?             If x and y are non-empty:
ç                  Return f(x, y)
                 Else:
 ;                 Return concat(x, y).

               Define main(z):    (merge sort)
       µL>1µ¡    Repeat (len(z) > 1) times:
s2                 Split z in chunks of length two.   [[9, 7], [1, 3], [2, 8]]
  Z                Transpose the resulting array.     [[9, 1, 2], [7, 3, 8]]
   ߀              Apply main() recursively to each.  [[1, 2, 9], [3, 7, 8]]
     ç/            Apply g on these two elements.     [1, 2, 3, 7, 8, 9]
Линн
источник
Не могли бы вы добавить объяснение, пожалуйста.
Есть много объяснений :) Дайте мне посмотреть, смогу ли я сыграть в гольф на последней строчке чуть-чуть больше
Линн
Когда вы говорите, что реализация O (n log n), но она использует list.pop (0) под капотом, а это O (n), я запутался. Что вы имеете в виду?
Я имею в виду именно то, что написал orlp в своем ответе: Это не O (n log n), потому что .pop(0)есть O (n), что делает функцию слияния O (n ^ 2). Но это довольно искусственно, так как это .pop(0)легко могло быть O (1).
Линн
Jelly реализован на Python и реализован как .pop(0).
Линн
1

Рубин, 167 байт

Алгоритм сортировки методом слияния по гольфу, который имеет наихудший O (n log n)

f=->x{m=->a,b{i,j,l,y,z=0,0,[],a.size,b.size
while i<y&&j<z
c=a[i]<b[j]
l<<(c ?a[i]:b[j])
c ?i+=1:j+=1
end
l+=a[i,y]+b[j,z]}
l=x.size
l>1?m[f[x[0,l/2]],f[x[l/2,l]]]:x}

Проверьте это здесь!

Для проверки скопируйте и вставьте код в окно и добавьте puts f[x]внизу, где x - это массив с входными данными. (Убедитесь, что вы выбрали Ruby в качестве языка, конечно) Например,puts f[[2, 2, 1, 9, 3, 7, 4, 1, 6, 7]]

Значение чернил
источник
Спасибо тебе за это! Можете ли вы показать это тоже работает?
1
Я добавил ссылку, чтобы вы могли проверить это.
Value Ink
1

Рубин, 297 байт

Сортировка слиянием. Полная программа, а не функция. Требуется два аргумента во время выполнения: входной файл и выходной файл, каждый с одним элементом в строке.

if $0==__FILE__;v=open(ARGV[0]).readlines.map{|e|e.to_i}.map{|e|[e]};v=v.each_slice(2).map{|e|a,b,r=e[0],e[1],[];while true;if(!a)||a.empty?;r+=b;break;end;if(!b)||b.empty?;r+=a;break;end;r<<(a[0]<b[0]?a:b).shift;end;r}while v.size>1;open(ARGV[1],"w"){|f|f.puts(v[0].join("\n"))if !v.empty?};end
jose_castro_arnaud
источник
Если это укорачивает ваш код, вам следует рассмотреть возможность адаптации кода к функции, которая получает массив в качестве входных данных и возвращает отсортированную последовательность. кажется, это избавит вас от большого количества байтов.
гордый haskeller
Если вы собираетесь сохранить его как целую программу вместо функции, могу ли я предложить использовать STDIN и STDOUT в качестве ввода / вывода, соответственно? $stdin.readlinesуже меньше байт , чем open(ARGV[0]).readlines, то же самое с putsболееopen(ARGV[1],"w"){|f|f.puts
Значение Ink
2
И такие вещи if $0==__FILE__действительно не нужны в коде гольфа. Вы также можете заменить каждую ;из них новой строкой - это тот же счетчик байтов и (вероятно) удаляет горизонтальную прокрутку кода. Также я рекомендую проверить советы по игре в гольф в Ruby .
Даниеро