Исследование алгоритмов сортировки в среде OC LINUX

basearraycopy – копия сортируемого массива.

Auxarray – вспомогательный массив, состоящий из 16000*factor элементов типа LongInt, factor = 1.4

Константы:

maxnumber      – вспомогательная константа, равная 70000

factor – константа, равная 1.4 = размер(auxarray)/размер(basearray)

 

Таблица и график результатов  исследования

 

Таблица

Результатов исследования зависимости времени (в мс) сортировки массива от его  размеров и способа заполнения.

 

                                                                                               

График

Зависимости времени сортировки от размера сортируемой  последовательности, заполненной случайным  образом.

 

    

 
 
 

             Начало

     

                       Задание размера массива и типа

                                его заполнения

   

Заполнение  массива

                Сохранение копии массива

 

              Обнуление таймера

           Сортировка методом Шелла

         Получение времени сортировки

             

                                   Проверка,               

                     правильно ли отсортирован   нет  

     массив?

 

   Да

Восстановление  исходного 

массива из копии

                               Обнуление таймера

                             Сортировка массивом

                         Получение времени сортировки

     Проверка,    Нет

правильно ли отсортирован

                              массив?

   Да

                             Проверка,

Да  есть ли неисследованные   

комбинации размера массива и

                            типа его заполнения?

 

      Нет

Вывод результатов

 

6. Анализ результатов эксперимента

 
 

В результате исследования я установил, что метод  Шелла является более эффективным  по сравнению с сортировкой массивом при сортировке упорядоченных и вырожденных данных, причем преимущество в скорости в случае с вырожденными данными возрастает с увеличением количества сортируемых элементов, что объясняется многочисленными перестановками при сортировке часто повторяющихся данных в алгоритме сортировки массивом. Метод Шелла приблизительно одинаково эффективен при упорядочивании данных любого типа и время сортировки пропорционально количеству элементов в массиве. А вот со случайными данными и данными обратного порядка очень быстро справляется сортировка массивом, опережая сортировку методом Шелла.

 

7.   Выводы

 

Проанализировав результаты эксперимента, я сделал вывод, что метод Шелла является более простым и хорошо справляется  с упорядоченными и вырожденными данными, причем в случае с вырожденными данными, чем больше количество сортируемых элементов, тем эффективнее этот метод по сравнению с сортировкой массивом. Результаты сортировки вырожденных данных отчетливо показывают крайнюю неэффективность алгоритма сортировки массивом. С набором повторяющихся данных он справляется значительно медленнее, чем метод Шелла. Но зато сортировка массивом замечательно справляется с упорядочиванием случайных данных, а ведь в основном числа, с которыми приходится иметь дело в реальной жизни расположены случайным образом, поэтому на практике чаще используется именно этот метод. Но наряду с этим метод сортировки массивом является более сложным методом относительно сортировки методом Шелла, требует больше памяти и не всегда будет наилучшим выбором.