Теоретическое сравнение сортировок методом простых вставок и методом пузырька

Выполним по рекомендованной литературе теоретическое сравнение алгоритмов сортировок, рассматриваемых в данном курсовом проекте. Основным критерием сравнения сортировок является их эффективность, то есть число сравнений и число пересылок. Данные показатели также влияют на время сортировки. Укажем основные формулы, использующиеся для вычисления эффективности данных сортировок:

− число сравнений ключей элементов при i-ом просеивании;

−минимальное число сравнений ключей;

− максимальное число сравнений ключей;

− среднее число сравнений ключей;

− число пересылок (присваиваний) элементов при i-ом просеивании;

− минимальное число пересылок

− максимальное число пересылок

− среднее число пересылок

− размер массива;

Рассмотрим сортировку методом простых вставок

Рассмотрим сортировку методом пузырька

На основе данных методических формул составим сравнительную таблицу для сортировок методом простых вставок и методом пузырька:

Таблица 2. Сравнительный анализ сортировок методом простых вставок и методом пузырька

На основе полученных в таблице 2 значений составим сравнительные графики, для числа сравнений ключей и для числа пересылок по обоим методам сортировки:

Рисунок 10. Графики числа сравнений ключей: число сравнений ключей П - для метода пузырька, число сравнений ключей В - для метода простых вставок.

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

Рисунок 11. Графики числа пересылок в сортировках: число пересылок П - для метода пузырька, число пересылок В - для метода простых вставок.

Основываясь на полученных графиках можно сказать, что при малых значениях размерности массива число пересылок для обоих методов примерно одинаково. При относительно больших размерах массива (от 512 и более) число пересылок в методе

пузырька возрастает быстрее, чем в методе простых вставок. Следовательно, эффективность метода вставок выше по данной характеристике.

Ссылаясь на таблицу 1 можно также отметить, что сортировка методом пузырька требует больше времени, чем сортировка методом вставок.

Из чего следует, что в целом сортировка методом простых вставок эффективнее сортировки методом пузырька.