Блочная сортировка

Cтраница 2

Блочная сортировка является примером уступки в отношении требуемой памяти ради уменьшения времени выполнения. Она использует больший объем памяти, но выполняется быстрее. Данный вариант блочной сортировки требует на каждом шаге копирования всех данных обратно в исходный массив. Другая возможность состоит в создании второго двумерного блочного массива и многократном перемещении данных между этими двумя блочными массивами до тех пор, пока все данные не будут скопированы в строку с номером нуль одного из массивов. [16]

Время быстрой сортировки одного миллиона элементов. [17]

Самый простой способ справиться с этой проблемой - просто игнорировать ее. Если вы знаете, что данные не имеют такого распределения, то ничего изменять не надо. Если данные имеют небольшой диапазон значений, то вамстоитрассмотреть другой алгоритм сортировки. Алгоритмы сортировки подсчетом и блочной сортировки, описанные в этой главе чуть позже, очень эффективны для списков, где диапазон значений данных невелик. [18]

Заметим, что двумерный массив блоков в десять раз больше размера массива, который сортируется. Эта техника сортировки обеспечивает более высокую производительность по сравнению с пузырьковой, но требует много больше памяти. Для пузырьковой сортировки требуется всего один дополнительный элемент данных. Это пример дилеммы память-время: блочная сортировка использует больше памяти, чем пузырьковая, но работает лучше. Другая возможность заключается в создании двумерного массива блоков и повторного обмена данными между двумя массивами блоков. [19]

Страницы: 1 2