Практические задания 2021. Алгоритмы и анализ сложности (практика) Экспериментальный анализ различных методов сортировки

• Название: Алгоритмы и анализ сложности (практика) Экспериментальный анализ различных методов сортировки
• Дата: 11.12.2022
• Размер: 47.5 Kb.
• Имя файла: Практические задания 2021.doc
• Тип: Документы; #839262

Алгоритмы и анализ сложности (практика)

Экспериментальный анализ различных методов сортировки

1. Реализовать различные методы сортировки и проверить на практике оценки их сложности:

• 
  простые схемы
  
• 
  сортировка Шелла (с различными длинами промежутков)
  
• 
  быстрая сортировка
  
• 
  сортировка слиянием
  
• 
  сортировка кучей
  
• 
  поразрядная сортировка
  
• 
  встроенная в язык программирования сортировка
  

2. Сравнить их между собой на различных входных данных:

• 
  массивах различных типов
  
  • 
    массивах цифр (от 0 до 9) (однобайтовый тип данных)
    
  • 
    массивах целых чисел
    
  • 
    массивах строк
    
  • 
    массивах структур (например, дат)
    

• 
  массивах различной длины (малой – до 100, средней – до 10000, большой – до 1000000 элементов), например:
  
  • 
    порядка 50 элементов
    
  • 
    порядка 500 элементов
    
  • 
    порядка 5000 элементов
    
  • 
    порядка 50000 элементов
    
  • 
    порядка 500000 элементов
    
  • 
    
    *другие варианты? Плавное увеличение размера с некоторым шагом?
    
• 
  по-разному порожденных массивах
  
  • 
    случайно сгенерированных
    
  • 
    частично упорядоченных («неупорядоченный хвост» и т.п.)
    
  • 
    упорядоченных в обратном порядке
    
  • 
    *дополнительные варианты (факультативно)
    
    • 
      имеются дополнительные сведения о структуре массива:
      
    • 
      большая доля одинаковых элементов
      
    • 
      состоящих из групп одинаковых элементов (разного размера)
      
    • 
      специальные «хорошие» и «плохие» случаи
      

3. Наглядно представить полученные результаты и сделать выводы (соответствие теоретическим оценкам, в каких ситуациях какую сортировку использовать и т.д.).

• 
  описать методику сравнения;
  
• 
  для достоверности результатов проводить серии испытаний, а не единичные сравнения;
  
• 
  указать результативность методов в среднем;
  
• 
  проанализировать причины, которые привели к полученным результатам;
  
• 
  для наглядности использовать диаграммы, гистограммы и прочую визуализацию, а программный код убрать в приложения.
  

Дополнительные (необязательные) задания:

4*. Построить нерекурсивные реализации рекурсивных методов сортировки и сравнить с исходными (проверить, работает ли рекурсия медленнее). Как быть с переполнением стека? Как выполнять сортировку больших массивов?

5*. На основе полученных результатов сформулировать и реализовать собственную гибридную сортировку, использующую преимущества разных методов в зависимости от входных данных.


* В каких случаях оправданно использование поразрядной сортировки?


** В каких случаях можно обогнать встроенную в язык сортировку?


*** В каких случаях имеет смысл использовать простые методы сортировки?


**** Какая сортировка лучше, если не знаем ничего про входные данные?
Примечание.
В этой работе будут рассмотрены различные методы сортировок на основе экспериментальных данных. Главная задача – проверить, как же согласуется теоретическая модель сложности с практической; определить аспекты, которые на практике могут быть решающими при выборе сортировок; оценить нюансы поведения сортировок на различных типах входных данных; выявить, если это возможно, какие сортировки с худшим временем работы в теории, будут не такими плохими в применении на практике и т.д.

Исходя из смысла задания и рекомендаций по его выполнению, понятно, что в главную часть этой работы не должно входить описание сортировок и принципы их работы – это рассматривается на лекциях. Гораздо важнее иллюстративность представленного материала и выводы, напрямую не касающиеся теоретических изложений, а лишь подтверждающие или опровергающие их.

• 
  Желательно не просто описывать полученные результаты (такая-то сортировка лучше в таком-то сценарии), но и пытаться проанализировать причины именно таких результатов (такая-то сортировка оказалась лучше/хуже, потому что …).
  

• 
  Делать промежуточные выводы!
  

• 
  Отдельно сравнивать «лидеров»
  

Типичные ошибки

• 
  Сравнение скорости одной и той же сортировки на разных типах данных вместо сравнения между сортировками.
  
• 
  Сливающиеся графики
  
• 
  Ненаглядные диаграммы
  
• 
  Время выполнения – ноль
  
• 
  Отсутствие сравнения с сильнейшими сортировками