Здравствуйте, lintik, Вы писали:
L>Ну что, кто-то все еще считает, что спрашивать стандартные вопросы про сортировки это бесполезная трата времени.
А какой в этом смысл? В большинстве контор прямо запрещено писать свои сортировки.
Здравствуйте, CoderMonkey, Вы писали:
BFE>>Нет, насколько я понимаю. Для Radix Sort надо начинать с последнего символа строки, а не с первого. CM> CM>То есть про разницу между LSD и MSD вариантами ты никогда не слышал.
Нет, не слышал. MSD вариант — это quicksort. Какой смысл его называть Radix Sort?
Здравствуйте, CoderMonkey, Вы писали:
BFE>>Нет, не слышал. MSD вариант — это quicksort. CM> CM>Даже и близко не похоже.
Да ну? Для алфавитов и двух или трех символов это чистый quicksort, а для для большего числа — оптимизация за счёт увеличения расхода памяти.
Здравствуйте, CoderMonkey, Вы писали:
BFE>>Да ну? Для алфавитов и двух или трех символов это чистый quicksort CM>Серьезно, ну что за чушь ты несешь?
Ага. Так в википедии написано.
И ещё.
Возьмём строки состоящие из одного символа, например 'A' и попробуем отсортировать вашим алгоритмом строки вида:
A
AA
AAA
AAAA
AAAAA
AAAAAA
AAAAAAA
...
Очевидно, что на каждой итерации вам потребуется две корзины. Одна корзина будет содержать один элемент, а другая все оставшиеся. Посчитаем число перекладываний в корзины.
шаг 0: n операций перекладывания в одну корзину
шаг 1: одна операция перекладывания в первую корзину и n — 1 во вторую.
шаг 2: одна операция перекладывания в первую корзину и n — 2 во вторую.
шаг 3: одна операция перекладывания в первую корзину и n — 3 во вторую.
шаг 4: одна операция перекладывания в первую корзину и n — 4 во вторую.
...
шаг n — 1: одна операция перекладывания в первую корзину
Общее количество перекладываний n + n-1 + n-2 + n-3 + ... + 1 = n*(n + 1) / 2
Не, он не мой дубль. Он пытается безуспешно до вас донести мысль, что когда вы начнете реализовывать а практике radix sort для элементов, отличных от чисел фиксированной разрядности (напимер, строк болшой длины), вас ждут интересные открытия.
Например, открытие того, что complexity radix sortа для массива длины N равна O(kN), где k — число цифр в элементе массива (и его нельзя считать константой когда оно само сопоставимо с числом элементов массива). Ваши посты демонстрируют весьма оригинальное понимание реализации radix sortа, я с интересом слежу, когда же наконец до вас дойдет (но пока не доходит) какую чушь вы тут порете
За этой дискуссией чудовищно интересно следить, как в зоопарке, даже жалко будет, когда она закончится
Здравствуйте, B0FEE664, Вы писали:
L>>Ну что, кто-то все еще считает, что спрашивать стандартные вопросы про сортировки это бесполезная трата времени. BFE>А какой в этом смысл?
Смысл в отсеивании неадекватных людей на ранних стадиях собеседования
> В большинстве контор прямо запрещено писать свои сортировки.
Запрещено переизобретать велосипед. Писать свои алгоритмы, весьма похожие на сортировку, иногда приходится. Например, когда данные лежат на ~500 разных машинах и суммарно занимают несколько сотен терабайт.
Здравствуйте, ylp, Вы писали:
ylp>Не, он не мой дубль. Он пытается безуспешно до вас донести мысль, что когда вы начнете реализовывать а практике radix sort для элементов, отличных от чисел фиксированной разрядности (напимер, строк болшой длины), вас ждут интересные открытия.
В отличие от тебя с твоим дублем, я уже делал это на практике. Собственно, всё.
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
ylp>>Не, он не мой дубль. Он пытается безуспешно до вас донести мысль, что когда вы начнете реализовывать а практике radix sort для элементов, отличных от чисел фиксированной разрядности (напимер, строк болшой длины), вас ждут интересные открытия.
CM>В отличие от тебя с твоим дублем, я уже делал это на практике. Собственно, всё.
Давайте, покажите работающий на практике этот чудо-алгоритм сортировки строк! Но ведь сольетесь же...
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
ylp>>Давайте, покажите работающий на практике этот чудо-алгоритм сортировки строк! Но ведь сольетесь же...
CM>Есть определенные сомнения, что ты вообще поймешь код Начнешь доказывать, что это на самом деле квиксорт, и прочую дурь в том же духе.
У меня есть сомнения, что вы этот код (MSD radix sort для массива строк длины N) написать вообще в состоянии.
Потому что как вы его писать начнете, сразу для себя много открытий сделате.
Если не сольетесь — выкладывайте его сюда, потестируем вместе и сравним его с обычным квиксортом на тех же данных по вашим же словам radix sort прекрасно применим во всех случаях, когда применим квиксорт.
Здравствуйте, ylp, Вы писали:
ylp>У меня есть сомнения, что вы этот код (MSD radix sort для массива строк длины N) написать вообще в состоянии. ylp>Потому что как вы его писать начнете, сразу для себя много открытий сделате.
Для начала, хотелось бы увидеть какие-то доказательства, что ты в состоянии этот код понять. Потому что, учитывая всю дурь, которую ты уже здесь написал — не хотелось бы устраивать очередной раунд метания бисера.
А писать ничего не надо — старый код уже лежит у меня на диске.
Здравствуйте, ylp, Вы писали:
L>>>Ну что, кто-то все еще считает, что спрашивать стандартные вопросы про сортировки это бесполезная трата времени. BFE>>А какой в этом смысл? ylp>Смысл в отсеивании неадекватных людей на ранних стадиях собеседования
Если все адекватные, так на работе и поговорить будет не о чем. Скучно.
>> В большинстве контор прямо запрещено писать свои сортировки. ylp>Запрещено переизобретать велосипед. Писать свои алгоритмы, весьма похожие на сортировку, иногда приходится. Например, когда данные лежат на ~500 разных машинах и суммарно занимают несколько сотен терабайт.
Ну если у вас 500 разных машинах и несколько сотен терабайт, то тогда, конечно, сортировку имеет смысл спрашивать.
