Код гольф: объединение нескольких отсортированных списков в один отсортированный список

Question

Реализовать алгоритм для объединения произвольного количества отсортированных списков в один отсортированный список. Цель состоит в том, чтобы создать самую маленькую рабочую программу на любом языке, который вам нравится.

Например:

input:  ((1, 4, 7), (2, 5, 8), (3, 6, 9))
output: (1, 2, 3, 4, 5, 6, 7, 8, 9)

input:  ((1, 10), (), (2, 5, 6, 7))
output: (1, 2, 5, 6, 7, 10)

Примечание : решения, которые объединяют входные списки, а затем используют предоставляемую языком функцию сортировки, не соответствуют духу гольфа и не будут приняты:

sorted(sum(lists,[])) # cheating: out of bounds!

Помимо всего прочего, ваш алгоритм должен быть (но не должен быть) намного быстрее!

Четко укажите язык, любые недостатки и количество символов. Включайте в счет только значащие символы, но не стесняйтесь добавлять пробелы в код для художественных / читабельных целей.

Чтобы сохранить порядок, предложите улучшить комментарии или отредактировать ответы там, где это необходимо, вместо создания нового ответа для каждой "редакции".

РЕДАКТИРОВАТЬ : если бы я снова отправлял этот вопрос, я бы расширил правило «сортировка без языка», чтобы «не объединять все списки, а сортировать результат». Существующие записи, которые выполняют конкатенацию-затем-сортировку, на самом деле очень интересны и компактны, поэтому я не буду активно вводить правило, которое они нарушают, но не стесняюсь работать с более ограничительной спецификацией в новых представлениях.

---

Вдохновлен Объединение двух отсортированных списков в Python

Answer 1

C #

static void f(params int[][] b)
{
    var l = new List<int>();
    foreach(var a in b)l.AddRange(a);
    l.OrderBy(i=>i).ToList().ForEach(Console.WriteLine);
}
static void Main()
{
    f(new int[] { 1, 4, 7 },
      new int[] { 2, 5, 8 },
      new int[] { 3, 6, 9 });
}

Answer 2

Javascript

function merge(a) {
    var r=[], p;
    while(a.length>0) {
        for (var i=0,j=0; i<a.length && p!=a[j][0]; i++)
            if (a[i][0]<a[j][0])
                j = i;

        r.push(p = a[j].shift());

        if (!a[j].length)
            a.splice(j, 1);
    }
    return r;
}

Тест:

var arr = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]​;
alert(merge(arr));

Answer 3

F #, 32 знака

let f x=List.sort(List.concat x)

И без использования встроенной функции для конкат (57 символов):

let f x=List.sort(Seq.toList(seq{for l in x do yield!l}))

Answer 4

Perl: 22 символа, включая два значащих пробельных символа.

sub a{sort map{@$_}@_}

Только встроенные здесь. Увидеть? ;)

Звоните так:

my @sorted = a([1, 2, 3], [5, 6, 89], [13, -1, 3]);
print "@sorted" # prints -1, 1, 1, 2, 3, 3, 5, 6, 89

Честно говоря, отрицание языковых особенностей (примечание: не библиотеки ...) кажется своего рода контрацептивом. Самый короткий код для реализации на языке должен включать встроенные функции / языковые функции. Конечно, если вы импортируете модуль, вы должны считать этот код в своем решении.

Редактировать: удалены ненужные {} вокруг $ _.

Answer 5

Ruby:

41 значащий символ, 3 значащих пробела в теле метода слияния.

arrs - массив массивов

  def merge_sort(arrs)
    o = Array.new
    arrs.each do |a|
      o = o | a
    end
    o.sort!
  end

Для тестирования в irb:

  arrs = [ [ 90, 4, -2 ], [ 5, 6, -100 ], [ 5, 7, 2 ] ]
  merge_sort(arrs)

Возвращает: [-100, -2, 2, 4, 5, 6, 7, 90]

Редактировать: Использовал предоставленный язык слияния / сортировки, потому что он, вероятно, поддерживается кодом C и отвечает требованию «быстрее» Я подумаю над решением без позже (здесь выходные, а я в отпуске).

Answer 6

VB, как правило, не является языком выбора для кода гольф, но здесь все равно.

Настройка -

        Dim m1 As List(Of Integer) = New List(Of Integer)
        Dim m2 As List(Of Integer) = New List(Of Integer)
        Dim m3 As List(Of Integer) = New List(Of Integer)
        Dim m4 As List(Of Integer) = New List(Of Integer)

        m1.Add(1)
        m1.Add(2)
        m1.Add(3)

        m2.Add(4)
        m2.Add(5)
        m2.Add(6)

        m3.Add(7)
        m3.Add(8)
        m3.Add(9)

        Dim m5 As List(Of List(Of Integer)) = New List(Of List(Of Integer))
        m5.Add(m1)
        m5.Add(m2)
        m5.Add(m3)

Попытка в VB.NET (без сортировки)

        While m5.Count > 0
            Dim idx As Integer = 0
            Dim min As Integer = Integer.MaxValue
            For k As Integer = 0 To m5.Count - 1
                If m5(k)(0) < min Then min = m5(k)(0) : idx = k
            Next
            m4.Add(min) : m5(idx).RemoveAt(0)
            If m5(idx).Count = 0 Then m5.RemoveAt(idx)
        End While

Другая попытка VB.NET (с разрешением sort)

    Private Function Comp(ByVal l1 As List(Of Integer), ByVal l2 As List(Of Integer)) As Integer
        Return l1(0).CompareTo(l2(0))
    End Function
    .
    .
    .
    While m5.Count > 0
        m5.Sort(AddressOf Comp)
        m4.Add(m5(0)(0)) : m5(0).RemoveAt(0)
        If m5(0).Count = 0 Then m5.RemoveAt(0)
    End While

Вся программа -

        Dim rand As New Random
        Dim m1 As List(Of Integer) = New List(Of Integer)
        Dim m2 As List(Of Integer) = New List(Of Integer)
        Dim m3 As List(Of Integer) = New List(Of Integer)
        Dim m4 As List(Of Integer) = New List(Of Integer)
        Dim m5 As List(Of List(Of Integer)) = New List(Of List(Of Integer))
        m5.Add(m1)
        m5.Add(m2)
        m5.Add(m3)

        For Each d As List(Of Integer) In m5
            For i As Integer = 0 To 100000
                d.Add(rand.Next())
            Next
            d.Sort()
        Next

        Dim sw As New Stopwatch
        sw.Start()
        While m5.Count > 0
            Dim idx As Integer = 0
            Dim min As Integer = Integer.MaxValue
            For k As Integer = 0 To m5.Count - 1
                If m5(k)(0) < min Then min = m5(k)(0) : idx = k
            Next
            m4.Add(min) : m5(idx).RemoveAt(0)
            If m5(idx).Count = 0 Then m5.RemoveAt(idx)
        End While
        sw.Stop()

        'Dim sw As New Stopwatch
        'sw.Start()
        'While m5.Count > 0
        '    m5.Sort(AddressOf Comp)
        '    m4.Add(m5(0)(0)) : m5(0).RemoveAt(0)
        '    If m5(0).Count = 0 Then m5.RemoveAt(0)
        'End While
        'sw.Stop()

        Console.WriteLine(sw.Elapsed)
        Console.ReadLine()

Answer 7

Как у Haskell (158, но можно удалить более 24 пробелов.):

mm = foldl1 m where
  m [] b = b
  m a [] = a
  m (a:as) (b:bs)
   | a <= b = a : m as (b:bs)
   | true   = b : m (a:as) bs

Answer 8

Python, 107 символов:

def f(l):  
 n=[]  
 for t in l:  
  for i in t: n+=[t]  
 s=[]  
 while n: s.+=[min(n)]; n.remove(min(n))  
 return s  

Answer 9

VB.NET (2008) 185 символов

Принимает список (Of List (Of Byte))

Function s(i)

    s=New List(Of Byte)

    Dim m,c
    Dim N=Nothing

    Do
        m=N
        For Each l In i:
            If l.Count AndAlso(l(0)<m Or m=N)Then m=l(0):c=l

        Next

        If m<>N Then s.Add(m):c.Remove(m)       

    Loop Until m=N

End Function

Answer 10

BASH в 250 основных символов

BASH не очень хорош в манипулировании списками, в любом случае это делает работу.

# This merges two lists together
m(){ 
    [[ -z $1 ]] && echo $2 && return; 
    [[ -z $2 ]] && echo $1 && return; 
    A=($1); B=($2); 
    if (( ${A[0]} > ${B[0]} ));then 
        echo -n ${B[0]}\ ;
        unset B[0];
    else 
        echo -n ${A[0]}\ ;
        unset A[0];
    fi;
    m "${A[*]}" "${B[*]}";
}
# This merges multiple lists
M(){
    A=$1;
    shift;
    for x in $@; do
        A=`m "$A" "$x"`
    done
    echo $A
}

$ M '1 4 7' '2 5 8' '3 6 9'
1 2 3 4 5 6 7 8 9