Комментарии 10
Очень интересно. В виде кода, правда, не очень (с некоторым трудом могу представить практическое применение) — разве что один раз сравнить с другими и забыть (кстати, где количество операций для среднего и наихудшего случая?), а вот вживую с колодой надо будет попробовать…
в худшем (когда карты в обратном порядке) кучек будет n, значит мы должны будем сравнивать каждую карту с каждой кучкой — получаем n^2 сравнений.
мы должны будем сравнивать каждую карту с каждой кучкой
Нет, кучки упорядочены, мы можем использовать бинарный поиск. Так что n*log(n)
N кучек будет в случае прямого порядка, нет? В обратном кучка как раз будет одна.
Почему? В случае обратно отсортированного массива будет одна кучка, т.е. один стек, из которого мы все значения и вытащим обратно (сравнивая каждое с одним другим значением). O(n).
В случае отсортированного массива будет как раз n кучек, из каждой кучки мы добавим по одной карте в очередь, из которой мы вытащим все значения обратно (ни с чем не сравнивая). O(n)
Не?
В случае отсортированного массива будет как раз n кучек, из каждой кучки мы добавим по одной карте в очередь, из которой мы вытащим все значения обратно (ни с чем не сравнивая). O(n)
Не?
В том то и дело, что реверс — это не худший случай, а лучший.
В этом случае создастся всего одна стопка (напомню, что стопки всегда обратно упорядочены).
В этом случае создастся всего одна стопка (напомню, что стопки всегда обратно упорядочены).
nlogn для массива изначально отсортированного в обратном порядке.
И n дополнительной памяти. При этом ее надо выделять очень хитро. Одним куском не выделить. Чую там накладных расходов море будет.
Зачем? Есть же mergesort и quicksort. Один гарантирует nlogn при n памяти выделенной одним куском, второй nlogn при минимальном везении и in place работает.
А для колоды и прочих таких случаев bucket sort. Его не обойти.
И n дополнительной памяти. При этом ее надо выделять очень хитро. Одним куском не выделить. Чую там накладных расходов море будет.
Зачем? Есть же mergesort и quicksort. Один гарантирует nlogn при n памяти выделенной одним куском, второй nlogn при минимальном везении и in place работает.
А для колоды и прочих таких случаев bucket sort. Его не обойти.
от 30 до 39 (да, конечно, внутри масти количество карт не равно ровно десяти, но вы поняли, что имеется ввиду).от 30 до
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Пасьянсная сортировка