Лысаков. Основы программирования (Лекции (2017)), страница 8

Дляупорядочения важны худшее, среднее и лучшее поведениеалгоритма в терминах размера списка (n). Для типичногоалгоритма хорошее поведение — это O(n log n) и плохоеповедение —этоO(n2).Идеальноеповедениедляупорядочения — O(n). Алгоритмы сортировки, использующиетолькоабстрактнуюоперациюсравненияключей,всегдануждаются по меньшей мере в O(n log n) сравнениях в среднем.2.Память — ряд алгоритмов требует выделения дополнительнойпамятиподвременноехранениеданных.Приоценкеиспользуемой памяти не будет учитываться место, котороезанимают исходный массив и не зависящие от входнойпоследовательностизатраты,например,нахранениекодапрограммы.3.Устойчивость (stability) — устойчивая сортировка не меняетвзаимного расположения равных элементов.4.Естественностьповедения —эффективностьметодаприобработке уже упорядоченных или частично упорядоченныхданных.

Алгоритм ведёт себя естественно, если учитывает этухарактеристику входной последовательности и работает лучше.6566www.phys.nsu.ru5.1.Сортировка пузырькомРасположим массив сверху вниз, от нулевого элемента к последнему.Идея метода: шаг сортировки состоит в проходе снизу вверх помассиву. По пути просматриваются пары соседних элементов. Еслиэлементы некоторой пары находятся в неправильном порядке, то меняемих местами (рис. 9).Рис. 10. Сортировка массива за шесть проходовСреднее число сравнений и обменов имеют квадратичный порядокроста: О(n2), отсюда можно заключить, что алгоритм пузырька оченьмедлителен и малоэффективен.Тем не менее, у него есть громадное преимущество в том, что он проств реализации, и его можно улучшать различными способами.5.2.Рис.

9. Нулевой проходПосле нулевого прохода по массиву «вверху» оказывается самый«легкий» элемент — отсюда аналогия с пузырьком. Следующий проходПирамидальнаясортировкаявляетсяметодом,быстродействиекоторого оценивается как O(n log n).•Назовем пирамидой (Heap) бинарное дерево высоты k, в которомвсе узлы имеют глубину k или (k – 1) — дерево сбалансированное;делается до второго сверху элемента, таким образом, второй по величинеэлемент поднимается на правильную позицию.Пирамидальная сортировка•при этом уровень (k – 1) полностью заполнен, а уровень kзаполненДелаем проходы по все уменьшающейся нижней части массива до техслеванаправо,т.еформапирамидыимеетприблизительно такой вид:пор, пока в ней не останется только один элемент (рис.

10). На этомсортировка заканчивается, так как последовательность упорядочена повозрастанию.;•выполняется «свойство пирамиды»: каждый элемент меньше либоравен родителю.6768www.phys.nsu.ruКак хранить пирамиду? Наименее хлопотно поместить ее в массив.Восстановить пирамиду из массива как геометрический объект легко:достаточно вспомнить схему хранения и нарисовать, начиная от корня.Фаза 1 сортировки: построение пирамидыНачать построение пирамиды можно с a[k]...a[n], k = [size / 2]. Этачасть массива удовлетворяет свойству пирамиды, так как не существуетиндексов i,j: i = 2i + 1 (или j = 2i + 2 )... Просто потому, что такие i и jСоответствие между геометрической структурой пирамиды как дереваи массивом устанавливается по следующей схеме:в a[0] хранится корень дерева;•левый и правый сыновья элемента a[i] хранятся соответственно вa[2i + 1] и a[2i + 2].верно: его элементы могут быть любыми.

Свойство пирамиды сохраняетсялишь в рамках исходного, основного массива a[0]...a[n].Далее будем расширять часть массива, обладающую столь полезным•Поэтому для массива, хранящего в себе пирамиду, выполняетсяследующее свойство: a[i] >= a[2i + 1] и a[i] >= a[2i + 2].свойством, добавляя по одному элементу за шаг. Следующий элемент накаждом шаге добавления — тот, который стоит перед уже готовой частью.Чтобы при добавлении элемента сохранялась пирамидальность, будемиспользовать следующую процедуру расширения пирамиды a[i + 1]..a[n]Плюсы такого хранения пирамиды очевидны:•Следует заметить, что неправильно говорить о том, что a[k]..a[n]является пирамидой как самостоятельный массив.

Это, вообще говоря, не••находятся за границей массива.никаких дополнительных переменных, нужно лишь пониматьсхему;•узлы хранятся от вершины и далее вниз, уровень за уровнем;•узлы одного уровня хранятся в массиве слева направо.Запишем в виде массива пирамиду, изображенную выше. Слевана элемент a[i] влево:1.Смотрим на сыновей слева и справа — в массиве это a[2i + 1]и a[2i + 2] и выбираем наибольшего из них.2.Если этот элемент больше a[i] — меняем его с a[i] местами и идемк шагу 2, имея в виду новое положение a[i] в массиве. Иначеконец процедуры.направо, сверху вниз:Новый элемент «просеивается» сквозь пирамиду.9467184455120642.Ниже дана иллюстрация процесса для пирамиды из 8-и элементов:На рисунке место элемента пирамиды в массиве обозначено цифройсправа и вверху от него.6970www.phys.nsu.ru44 55 12 42 // 9444 55 12 // 67 9444 55 // 18 67 9444 // 94 18 67 55// 94 67 18 44 55181812121206060606066742424242Справа — часть массива, удовлетворяющая свойству пирамиды.Остальные элементы добавляются один за другим, справа налево.44 просеяли сквозь 94 и 67, остановились на 42В геометрической интерпретации ключи из начального отрезкаa[size / 2] ...

a[n] является листьями в бинарном дереве, как изображенониже. Один за другим остальные элементы продвигаются на свои места, итак будет продолжаться, пока не будет построена вся пирамида.На рисунках ниже изображен процесс построения. Неготовая частьпирамиды (начало массива) окрашена в белый цвет, удовлетворяющийсвойству пирамиды конец массива — в темный.Фаза 2: собственно сортировкаИтак, задача построения пирамиды из массива успешно решена. Каквидно из свойств пирамиды, в корне всегда находится максимальныйэлемент. Отсюда вытекает алгоритм фазы 2:1.Берем верхний элемент пирамиды a[0]...a[n] (первый в массиве)и меняем его с последним элементом местами.

Теперь «забываем»об этом элементе и далее рассматриваем массив a[0]...a[n–1]. Дляпревращения его в пирамиду достаточно просеять лишь новыйпервый элемент.2.Повторяем шаг 1, пока обрабатываемая часть массива неуменьшится до одного элемента.Исходная картина: 94, 18, 06, 67 – листья42 сравнили с 67 и поменяли их местами12 сравнили с max (18, 6) = 1855 сравнили с max (67, 94) = 9471Обменяли 94 и 42, «забыли» о 94Просеяли 42 сквозь 67 и 5572www.phys.nsu.ru6. Производные типы данных. Списки данныхИз базовых типов языка С можно формировать производные типыданных, к которым относятся массивы, структуры и объединения. Такжеможно отнести сюда и строки, которых до сих пор не хватало, чтобыдостаточно простым образом оперировать с различными именами и т. п.6.1.Обменяли 06 и 67, «забыли» о 67Просеяли 06 сквозь 55 и 44Очевидно, в конец массива каждый раз попадает максимальныйэлемент из текущей пирамиды, поэтому в правой части постепенноСтрокиСтрока определяется как частный случай одномерного массива(поскольку состоит их набора символов).

При этом последний элементобязан быть равен '/0', что обозначает конец строки.Приведемвозникает упорядоченная последовательность.примеропределениястрокиисчитыванияименипользователя, и затем его распечатки:Ниже приведена иллюстрация второй фазы сортировки во внутреннемпредставлении пирамиды.9467554442181206 //•67 18 44 55 12 06 42 //55 44 06 42 18 12 // 9442 44 06 12 18 // 67 9442 18 06 12 // 55 67 9412 18 06 // 44 55 67 9412 06 // 42 44 55 67 9406 // 18 42 44 55 67 9412 18 42 44 55 67 94Пирамидальнаясортировканеиспользуетcout << zapros;}дополнительнойМетод не является устойчивым: по ходу работы массив так«перетряхивается», что исходный порядок элементов можетизмениться случайным образом.•cin >> name;cout << "Hello " << name << "!" << endl;Если необходимо определить длину введенной строки, то можнопамяти.•void main(){char name[80];char zapros[80] = "Input your name: ";Поведение неестественно: частичная упорядоченность массиваиспользовать следующий способ:int n;for(n=0;;n++){if(name[n] == '\0')break;}cout << "Your name contain " << n << " letters";никак не учитывается.7374www.phys.nsu.ru6.2.Структурный типструктуры.

При этом объем необходимой памяти определяется с помощьюЭтот тип задает внутреннее строение определяемых с помощью негоструктурныхпеременных.Частоприменяетсяпростоназваниетип структуры.Доступ к полям структур осуществляется следующим образом:«структура».Структурафункции sizeof(), которой в качестве параметра можно передать имя или—этообъединенноевединоецелоеИмя_Объекта . полемножествопоименованных элементов данных. В отличие от массивов данных, всегдалибоУказатель_на_Объект -> полесостоящих из данных одного типа, структуры могут содержать различныетипа данных.

Например, может быть введена структура, описывающаястудента университета со следующими компонентами (полями):Приведем в качестве примера фрагмент кода, в котором создаетсяпеременная структурного типа, осуществляется инициализация всех полейи распечатка через указатель на структуру.••••имя;фамилия;номер группы;год рождения.#include <iostream>using namespace std;Для данного примера структура создается следующим образом:struct Student{char Name[80];char Surname[80];int Group;int Birth_year;};struct Student{char Name[80];char Surname[80];int Group;int Birth_year;};void main(){Student Vasya;Таким образом, для того чтобы ввести в программу студентовcincincincinопределенного факультета, можно, например, создать массив, состоящийиз таких структур данных.

Это позволит упростить написание подобныхпрограмм.пользовательским, то он должен быть определен вне функций дляcoutcoutcoutcoutобеспечения максимальной области видимости.Переменная структурного типа создается таким же образом, как75Vasya.Name;Vasya.Surname;Vasya.Group;Vasya.Birth_year;Student* pVasya;pVasya = &Vasya;Обратите внимание, что поскольку структурный тип данных являетсяи любые другие переменные.