Анализ некоторых видов сортировок
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
шеизложенные методы.
Аналогичным образом делаются проходы по части массива, и аналогичным же образом в его начале "вырастает" отсортированная последовательность.
Однако в сортировке пузырьком или выбором можно было четко заявить, что на i-м шаге элементы a[0]...a[i] стоят на правильных местах и никуда более не переместятся. Здесь же подобное утверждение будет более слабым: последовательность a[0]...a[i] упорядочена. При этом по ходу алгоритма в нее будут вставляться (см. название метода) все новые элементы.
Будем разбирать алгоритм, рассматривая его действия на i-м шаге. Как говорилось выше, последовательность к этому моменту разделена на две части: готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n].
На следующем, (i+1)-м каждом шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива.
Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним.
В зависимости от результата сравнения элемент либо остается на текущем месте(вставка завершена), либо они меняются местами и процесс повторяется.
Таким образом, в процессе вставки мы "просеиваем" элемент x к началу массива, останавливаясь в случае, когда
.Hайден элемент, меньший x или
.Достигнуто начало последовательности.
void Pirmidalina9(kop,razmer,iter) - функция сортирующая массив пирамидальной сортировкой.
Пошаговое описание алгоритма
. Построение пирамиды
Пирамида представляет собой дерево, в котором каждый узел имеет не более двух потомков, причем узел всегда больше или равен своим потомкам (таким образом, на вершине дерева всегда находится наибольший элемент).
Если в исходном массиве n элементов, то последние (n / 2) элемента становятся основанием пирамиды (эти элементы являются листьями дерева, т.е. у них нет потомков, поэтому для них вышеуказанное правило выполняется автоматически).
Удобнее всего поместить пирамиду в массив. При этом распределение индексов массива по узлам дерева будет выглядеть так (на этом рисунке все цифры - это индексы элементов массива, а ни в коем случае не значения этих элементов):
Таким образом, для того, чтобы
каждый узел дерева был больше своих потомков, каждый элемент массива a[i] должен быть больше или равен элементам a[2 * i + 1] и a[2 * i + 2].
. Сортировка
В этой части алгоритма мы перемещаем в конец массива максимальный элемент, затем исключаем его из дальнейшего процесса сортировки. Поскольку максимальный элемент всегда находится на вершине пирамиды, мы должны поменять местами элементы a[0] и a[n-1] (т.е. последний элемент). Причем элемент a[n-1] необходимо добавлять так, чтобы не нарушился порядок пирамиды (при этом пирамиду придется частично перестроить). Далее мы будем рассматривать массив только до (n-2)-го элемента.
На следующем шаге мы меняем местами a[0] и a[n-2] и далее рассматриваем массив только до (n-3)-го элемента. Повторяем всю эту процедуру до тех пор, пока в рассматриваемой части массива не останется один элемент.
int Zadaniemassiva(int midx,int midy,int& metod,long int& razmer,int& p) - функция в которой задаётся размер массива,метод заполнения массива(рандомом,по возрастанию и по убыванию).Максимально вводимое число массива 24500 элементов.Пока не будет задан массив в программе будет активно только 2 кнопки Задание массива и Exit.
int F1(int midx,int midy) { - функция прорисовывающая название кнопок.
moveto((midx-7*14),midy-30);("Zadanie parametrov masiva");((midx-7*3),midy);("Puzirek");((midx-7*3),midy+30);("Vstavki");((midx-7*7),midy+60);("Protalkivani9");((midx-7*7),midy+90);("Piramidalina9");((midx-7*2),midy+120);("Exit");0;
}F(int midx,int midy,int h,int p) { - функция прорисовывающая кнопки меню.y=midy;(int i=-30;i<=120;i+=30) { (p==0) { //если переменная р=0 то это значит что массив ещё не задан и активнми будут только кнопки Задание массива и Exit.
setfillstyle(1,7);
bar(midx-100, y-10+i, midx+100,y+10+i);
}
if ((p==1) || (-1==(i/30)) || ((i/30)==4)) { // p=1 массив задан все кнопки меню активны.
setfillstyle(1,2);
bar(midx-100, y-10+i, midx+100,y+10+i);
}
if (h==(i/30)) { //данное условие определяет какая кнопка сейчас активна.
setfillstyle(1,3);
bar(midx-100, y-10+i, midx+100,(y+10)+i);
}
}
return F1(midx,midy);
}
int File(int*& kop,int k,int razmer) { - данная функция записывает отсортированный массив в файл с расширением .txt по убыванию или по возрастанию в зависимости от того,что выбрал пользователь.
FILE *out;((out = fopen("c:\\BORLANDC\\BIN\\1.txt", "w")) == NULL) {(stderr, "Cannot open output file.\n");1; }(k==1) {
for (int i=0; i<razmer; i++) {
fprintf(out, "%d ", kop[i] );
}
}(k==0) {
for (int i=razmer-1; i>=0; i--) {
fprintf(out, "%d ", kop[i] );
}
}
fclose(out);
return 0;
}
Заключение
Были исследованы некоторые методы сортировок.Была изучена литература по алгоритмам сортировок,составлены подпрограммы сортировок,проведён анализ и вычислено среднее время каждой сортировки,а также составлено графическое меню для пользователей.
Анализ показал,что при исходном массиве заполненном рандомом лучшее время показывает пирамидальная сортировка,с относительно небольшим количеством итераций.При исходном массиве заполненном по возрастанию лучшее время показывает метод пузырька 0 секунд и колличетсво иттераций 0.При массиве сгенерированном по убыванию лучшее время показала пирамидальная сортировка.Ниже представлены средние результаты проведённого анализа при количестве 24500 элементов.
Метод сортировкиСреднее время (сек) Кол.иттерацийтип заполнения массиваПузырёк1,37150305841Рандом00По возрастанию2,58300000000По убываниюВставка0,75205291Рандом0,330По возрастанию1,26150062500По убыв