Автор Тема: Задачка на сортировку  (Прочитано 5120 раз)

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Задачка на сортировку
« : Ноябрь 26, 2013, 09:10:57 pm »
Вобщем ничего такого сложного, но поскольку я на нее потратил сильно больше времени, чем казалось она того стоит (может просто тупил, да), то решил поделиться. ИМХО как вариант для собеседования тоже подойдет.

Дано: дерево в виде таблицы id'шек:
parent_id    id
--------------
10          1
10          2
20          3
-1          20
20          10
parent_id = -1 означает корень, корней может быть больше одного

Плучить: таблицу отсортированную так, что каждому следующему parent_id предшествует его "объявление" в виде id. Т.е., для данного примера это будет:
parent_id  id
--------------
-1          20
20          3
20          10
10          1
10          2

Решаем на любом языке (оберон как всегда интереснее всего :)
Решение на чистом SQL (из него все пошло) тоже интересно :)

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Re: Задачка на сортировку
« Ответ #1 : Ноябрь 26, 2013, 10:03:43 pm »
Решение на чистом SQL (из него все пошло) тоже интересно :)

Решение на SQL работало на том основании, что id генерировались последовательно и родитель всегда создавался первым.  Соответственно, банальный "ORDER BY parent_id, id" замечательно решал задачу. Случай перемещения из одного родителя в другой был довольно редок и про него забыли. Но в один прекрасный день (сегодня, гхм) он о себе напомнил. Пришлось переписывать на питоне :)

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Задачка на сортировку
« Ответ #2 : Ноябрь 26, 2013, 10:21:32 pm »
Решение в лоб (-1 корень, как я понял):  :)
function print_tree(t, key)
   for _, elem in pairs(t) do
      if elem[1] == key then
         print(elem[1], elem[2])
         print_tree(t, elem[2])
      end
   end
end

local t = {
   {10,  1},
   {10,  2},
   {20,  3},
   {-1, 20},
   {20, 10}
}

print_tree(t, -1)
ps Просто вывод на экран.

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Re: Задачка на сортировку
« Ответ #3 : Ноябрь 26, 2013, 10:46:26 pm »
Решение в лоб (-1 корень, как я понял):  :)

Зачет! Получилось слишком просто, усложним задачу :) Как насчет детектирования сирот?

P.S. Можно еще поработать над сложностью. В данном варианте получается что-то типа O(n^depth), где n - количество записей, а depth глубина дерева (какая-то усредненная).

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: Задачка на сортировку
« Ответ #4 : Ноябрь 27, 2013, 02:51:16 am »
Решаем на любом языке (оберон как всегда интереснее всего :)
Решение на чистом SQL (из него все пошло) тоже интересно :)
Это не сортировка, а обход дерева в ширину (горизонтальный обход).
На нормальном языке: построить дерево, обойти в ширину  :)
На SQL сводится к изучению рекурсивных извратов для конкретной реализации.

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Задачка на сортировку
« Ответ #5 : Ноябрь 27, 2013, 08:13:30 am »
Не обязательно обход в ширину. Это вполне себе может топологическая сортировка.

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Задачка на сортировку
« Ответ #6 : Ноябрь 27, 2013, 10:02:39 am »
Решение в лоб (-1 корень, как я понял):  :)

Зачет! Получилось слишком просто, усложним задачу :) Как насчет детектирования сирот?
Ну просто флаг в таблицу добавить, и отобрать потом по нему ентих сирот.

P.S. Можно еще поработать над сложностью. В данном варианте получается что-то типа O(n^depth), где n - количество записей, а depth глубина дерева (какая-то усредненная).
В реальных задачах делается ровно так же, только у таблицы есть индекс по ключу.

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: Задачка на сортировку
« Ответ #7 : Ноябрь 27, 2013, 11:38:43 am »
Не обязательно обход в ширину. Это вполне себе может топологическая сортировка.
Может быть, но все зависит от требований. Например, есть один родитель с кучей детей. При топологической сортировке без извратов дети будут в случайном порядке. А при построении и обходе  дерева легко добиться, чтобы дети были отсортированы.

P.S. Хотя для топологической, кажется, тоже легко написать соотв. функцию сравнения.
« Последнее редактирование: Ноябрь 27, 2013, 11:44:03 am от Peter Almazov »