17. Алгоритмы сортировки

Цель работы - изучение алгоритмов сортировки

Задания и указания по их выполнению

Задание 1.  Реализовать функции сортировки массива целых чисел по следующему алгоритму:

а)  пузырьковой сортировки - void sort_bubble(int*ptrarr, int n);

б)  шейкерной (перемешиванием) сортировки - void sort_kokteil(int*ptrarr, int n);

в)  сортировки простым выбором - void sort_select(int*ptrarr, int n);

г)  сортировки вставками - void sort_insert(int*ptrarr, int n);

Попробуйте выполнить реализацию руководствуясь блок-схемами  алгоритмов

Задание 2.  Разработать программный комплекс для проведения вычислительных экспериментов по оценке эффективности алгоритмов.

Для этого из предшествующих работ добавить функции 

• формирования массива int* full_array(int *, int);

• вывода (печати) массива int put_array(int *, int); 

В главной функции реализовать ввод размера массива и замер времени вычисления:

full_array(ptrarr, size);

t = clock();

sort_insert(ptrarr, size);

time = (clock() - t)*1. / CLOCKS_PER_SEC;

Задание 3.  Проведите вычислительный эксперимент по одному из вариантов:

1) сравнение простых сортировок (выбором, пузырьковая, коктельная, вставками) для различных размеров выборок  100, 1000, 10000 значений

2) сравнение простых сортировок (выбором, пузырьковая, коктельная, вставками) для различных типов данных - int, long, float, double, long double  при фиксированном размере элементов массива

3) сравнение быстрых сортировок (Шелла, быстрая Хоара и слиянием) с функцией стандартной библиотеки sort()  для различных размеров выборок  1000, 10000 целочисленных значений

4) оценка влияния выбора шага на скорость сортировки Шелла для фиксированного размера выборки (Рассмотреть выбор шага для следующих случаев:

• первоначально используемая Шеллом последовательность длин промежутков: { d1=N/2, d1=d1/2, ... dk=1} 

• предложенная Хиббардом последовательность: 2N-1 

• предложенная Седжвиком последовательность:  ;

• предложенная Праттом последовательность: ; 

• эмпирическая последовательность Марцина Циура  { d={1,4,10,23,57,132,301,701,1750}}; 

• эмпирическая последовательность, основанная на числах Фибоначчи.

5) оценка влияния расстояния между сравниваемыми элементами на скорость сортировки расческой для фиксированного размера выборки