Сейчас на форуме: bartolomeo, hgdagon (+6 невидимых) |
![]() |
eXeL@B —› Программирование —› Подскажите алгоритм сортировки (8гиг) |
. 1 . 2 . >> |
Посл.ответ | Сообщение |
|
Создано: 23 февраля 2006 10:13 · Личное сообщение · #1 |
|
Создано: 23 февраля 2006 11:53 · Личное сообщение · #2 |
|
Создано: 23 февраля 2006 11:54 · Личное сообщение · #3 |
|
Создано: 23 февраля 2006 11:58 · Поправил: PalR · Личное сообщение · #4 |
|
Создано: 23 февраля 2006 12:03 · Личное сообщение · #5 |
|
Создано: 23 февраля 2006 12:11 · Личное сообщение · #6 |
|
Создано: 23 февраля 2006 12:28 · Личное сообщение · #7 |
|
Создано: 23 февраля 2006 12:32 · Личное сообщение · #8 |
|
Создано: 23 февраля 2006 12:36 · Личное сообщение · #9 |
|
Создано: 23 февраля 2006 12:38 · Личное сообщение · #10 |
|
Создано: 23 февраля 2006 12:39 · Личное сообщение · #11 |
|
Создано: 23 февраля 2006 12:41 · Личное сообщение · #12 |
|
Создано: 23 февраля 2006 12:42 · Личное сообщение · #13 |
|
Создано: 23 февраля 2006 12:43 · Личное сообщение · #14 |
|
Создано: 23 февраля 2006 12:47 · Поправил: PalR · Личное сообщение · #15 |
|
Создано: 23 февраля 2006 13:03 · Личное сообщение · #16 |
|
Создано: 23 февраля 2006 13:12 · Личное сообщение · #17 Можно почитать третий томик Искусство програмирования от Д.Кнута... а если именно сортировать для удаления дубликатов - то создать, например, хэштаблицу мыл(привести почтовые адреса для начала к одному регистру), отсортировать хэши(несколько проще,чем строки) и уже в такой отсортированной таблице шустрым двоичным(или интерполяционным) поиском искать многократные вхождения ![]() |
|
Создано: 23 февраля 2006 14:23 · Личное сообщение · #18 Вообще каждая сортировка себя ведет по разному поэтому лучшего алгоритма нет. Но себя очень хорошо на практике показывают Универсальная быстрая (quicksort) и шейкер-сортировка. В институте мы их стук 20 изучали, я чуть не опух ![]() Обычно при выборе сортировки для большого количества данных, выделяют 3 типа данных: 1) хорошо упорядоченные 2) не очень упорядоченные 3) не упорядоченные Ну и соответственно выбирают соответствующую сортировку. ----- Никто не знает столько, сколько не знаю я ![]() |
|
Создано: 23 февраля 2006 16:33 · Личное сообщение · #19 |
|
Создано: 23 февраля 2006 17:10 · Личное сообщение · #20 Satanael пишет: очень хорошо на практике показывают Универсальная быстрая (quicksort) и шейкер-сортировка. шейкер, имхо, ничем не лучше пузырька. и не понимаю, как сортировка со сложностью n**2 может показывать себя на уровне наиболее быстрого из фундаментальных сортировок квиксорта, с его средней сложностью n*(log2 n). в данном случае лучше всего использовать merge sort, тем более замечательно распараллеливается. делишь всю последовательность строк на k подпоследотельностей, сортируешь их любой сортировкой, потом сливаешь в одну. я б сортировал пирамидальной. во-первых - точно можно посчитать время сортировки, во-вторых - ну не люблю я квиксорт ![]() ![]() |
|
Создано: 23 февраля 2006 18:12 · Личное сообщение · #21 NG я б сортировал пирамидальной. во-первых - точно можно посчитать время сортировки, во-вторых - ну не люблю я квиксорт ---------------------------- Не пирамидальная фегня, Квиксорт форева. Сделаю тест (если время будет) для этих двух сортировок, посмотрим какая быстрее окажется. Квиксорт форева!!!! Пирамидальная, хех, тыб ещё про метод простыми вставками вспомнил ![]() ----- Никто не знает столько, сколько не знаю я ![]() |
|
Создано: 23 февраля 2006 19:21 · Личное сообщение · #22 Satanael пишет: Не пирамидальная фегня, Квиксорт форева. Сделаю тест (если время будет) для этих двух сортировок, посмотрим какая быстрее окажется. Квиксорт форева!!!! Пирамидальная, хех, тыб ещё про метод простыми вставками вспомнил и чего ты хотел добиться подобными выкриками? любой из них весьма спорен. 1. "квиксорт форева". - пиздеж и провокация(я давно не писал в этот форум, меня забанят? ![]() не мог бы ты объяснить, с чего ты это взял? да, квиксорт отлично сортирует среднего размера порции данных(на небольших объемах слишком велики потери на организацию рекурсии, а на больших будет плохо стеку =)). худшее время квиксорта - n**2, тогда как у пирамидальной сортировки худшее время - n*(log2 n). и даже никаких программ писать не надо, все можно на пальцах посчитать. 2. причем тут метод простыми вставками? или это ты сказал чтобы сказать? ![]() |
|
Создано: 23 февраля 2006 19:44 · Поправил: PalR · Личное сообщение · #23 |
|
Создано: 23 февраля 2006 20:31 · Личное сообщение · #24 ну не знаю, я вот курсовую когда делал, писал на С++ в консоли и реализовывал все это дело на массиве курсоров и в очереди и работала почти быстрей всех из группы, советую писать именно в консоли, ибо не тратится много машинного времени на побочные действия, производимые например Дельфи. аа... я делал кстати алгоритм Шелла, модифицация простых вставок вот собственно #include <iostream.h>
тебе остается только на обычные массивы переделать, а результаты в тиках(какие доли секунды точно не помню) следующие 40 - 1000 элементов 240 - 2000 элементов 431 - 3000 элементов 1272 - 4000 элементов 1692 - 5000 элементов ![]() |
|
Создано: 23 февраля 2006 23:52 · Поправил: Satanael · Личное сообщение · #25 NG спакойно ![]() Да ладно пирамидальная сортировка всех отсартирует по самое нехочу. ![]() (пошёл изучать пирамидальную сортировку) 2. причем тут метод простыми вставками? или это ты сказал чтобы сказать? Ага ![]() Данные имеют различную степень упорядоченности, совершенно разное количество приходится делать итераций и прочей хрени поэтому причём тут n*(log2 n), на практике всё нетак. Ну шейкер не тоже самое что пузырьковая, всё таки она по производительней будет пузырьковой, могу на 500р поспорить ![]() Ща хорошие исходники приатачу Сортировка слиянием (на основе квиксорт,С++), только найду. ----- Никто не знает столько, сколько не знаю я ![]() |
|
Создано: 25 февраля 2006 00:16 · Личное сообщение · #26 |
|
Создано: 25 февраля 2006 03:24 · Личное сообщение · #27 Квиксорт рулит полюбому. > 1. "квиксорт форева". - пиздеж и провокация(я давно не писал в этот форум, меня забанят? ) Забанять точно, я постораюсь. Потерями на рекурсию пугать может только тупой пионер (даже если есть рекурсия это микросекунды), или тупой препод - qsort лехко реализутся без рекурсии и будет явно на порядо кбустрее метода вставки. Кто не согласен - к барьеру быстро! ![]() ![]() |
|
Создано: 25 февраля 2006 08:11 · Личное сообщение · #28 |
|
Создано: 25 февраля 2006 11:01 · Личное сообщение · #29 |
|
Создано: 25 февраля 2006 12:28 · Личное сообщение · #30 |
. 1 . 2 . >> |
![]() |
eXeL@B —› Программирование —› Подскажите алгоритм сортировки (8гиг) |