Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
1.Структуры языка СИ.
Структурой в языке C называется совокупность логически связанных переменных различных типов, сгруппированных под одним именем для удобства дальнейшей обработки.
Структура – это способ связать воедино данные разных типов и создать пользовательский тип данных. В языке Pascal подобная конструкция носит название записи.
Структура – тип данных, задаваемый пользователем. В общем случае при работе со структурами следует выделить четыре момента:
- объявление и определение типа структуры,
- объявление структурной переменной,
- инициализация структурной переменной,
- использование структурной переменной.
Определение типа структуры представляется в виде
struct ID
{
<тип> <имя 1-го элемента>;
<тип> <имя 2-го элемента>;
…………
<тип> <имя последнего элемента>;
};
Определение типа структуры начинается с ключевого слова struct и содержит список объявлений, заключенных в фигурные скобки. За словом struct следует имя типа, называемое тегом структуры (tag – ярлык, этикетка). Элементы списка объявлений называются членами структуры или полями. Каждый элемент списка имеет уникальное для данного структурного типа имя. Однако следует заметить, что одни и те же имена полей могут быть использованы в различных структурных типах.
Определение типа структуры представляет собой шаблон (template), предназначенный для создания структурных переменных.
Объявление переменной структурного типа имеет следующий вид:
struct ID var1;
при этом в программе создается переменная с именем var1 типа ID. Все переменные, использующие один шаблон (тип) структуры, имеют одинаковый набор полей, однако различные наборы значений, присвоенные этим полям. При объявлении переменной происходит выделение памяти для размещения переменной. Шаблон структуры позволяет определить размер выделяемой памяти.
В общем случае, под структурную переменную выделяется область памяти не менее суммы длин всех полей структуры, например,
struct list
{
char name[20];
char first_name[40];
int;
}L;
В данном примере объявляется тип структура с именем list, состоящая из трех полей, и переменная с именем L типа struct list,при этом для переменной L выделяется 64 байта памяти.
Отметим, что определение типа структуры может быть задано в программе на внешнем уровне, при этом имя пользовательского типа имеет глобальную видимость (при этом память не выделяется). Определение типа структуры также может быть сделано внутри функции, тогда имя типа структуры имеет локальную видимость.
Создание структурной переменной возможно двумя способами: с использованием шаблона (типа) или без него.
Создание структурной переменной pt на основе шаблона выполняется следующим образом:
struct point //Определение типа структуры
{
int x;int y;
};
……
struct point pt; //Создание структурной переменной
Структурная переменная может быть задана уникальным образом:
struct //Определение анонимного типа структуры
{
char name[20];
char f_name[40];
char s_name[20];
} copymy; //Создание структурной переменной
При размещении в памяти структурной переменной можно выполнить ее инициализацию. Неявная инициализация производится для глобальных переменных, переменных класса static. Структурную переменную можно инициализировать явно при объявлении, формируя список инициализации в виде константных выражений.
Формат: struct ID name_1={значение1, … значениеN};
Внутри фигурных скобок указываются значения полей структуры, например,
struct point pt={105,17};
при этом первое значение записывается в первое поле, второе значение – во второе поле и т. д., а сами значения должны иметь тип, совместимый с типом поля.
Над структурами возможны следующие операции:
- присваивание значений одной структурной переменной другой структурной переменной, при этом обе переменные должны иметь один и тот же тип;
- получение адреса переменной с помощью операции &;
- осуществление доступа к членам структуры.
Присваивание значения одной переменной другой выполняется путем копирования значений соответствующих полей, например:
struct point pt={105,15},pt1;
pt1=pt;
В результате выполнения этого присваивания в pt1.x будет записано значение 105, а в pt1.y – число 15.
Работа со структурной переменной обычно сводится к работе с отдельными полями структуры. Доступ к полю структуры осуществляется с помощью операции. (точка) посредством конструкции вида:
имя_структуры.имя_поля_структуры;
при этом обращение к полю структуры представляет собой переменную того же типа, что и поле, и может применяться везде, где допустимо использование переменных такого типа.
Например,
struct list copy = {"Ivanov","Petr",1980};
Обращение к "Ivanov" имеет вид copy.name. И это будет переменная типа указатель на char. Вывод на экран структуры copy будет иметь вид: printf("%s%s%d\n",copy.name,copy.first_name,copy.i);
Структуры нельзя сравнивать. Сравнивать можно только значения конкретных полей.
К началу главы
12.2. Структуры и функции
Структуры могут быть переданы в функцию в качестве аргументов и могут служить в качестве возвращаемого функцией результата.
Существует три способа передачи структур функциям:
- передача компонентов структуры по частям;
- передача целиком структуры;
- передача указателя на структуру.
Например, в функцию передаются координаты двух точек:
void showrect(struct point p1,struct point p2)
{
printf("Левый верхний угол прямоугольника:%d %d\n",
p1.x, p1.y);
printf("Правый нижний угол прямоугольника:
%d %d\n", p2.x, p2.y);
}
При вызове такой функции ей надо передать две структуры:
struct point pt1={5,5},
pt2={50,50};
showrect(pt1,pt2);
Теперь рассмотрим функцию, возвращающую структуру:
struct point makepoint (int x,int y) /*makepoint – формирует точку по компонентам x и y*/
{
struct point temp;
temp.x = x;
temp.y = y;
return temp;
}
Результат работы этой функции может быть сохранен в специальной переменной и выведен на экран:
struct point buf;
buf=makepoint(10,40);
printf("%d %d\n",buf.x,buf.y);
После выполнения этого фрагмента на экран будут выведены два числа: 10 и 40.
К началу главы
12.3. Указатели на структуру
Если функции передается большая структура, то эффективнее передать указатель на эту структуру, нежели копировать ее в стек целиком. Указатель на структуру по виду ничем не отличается от указателей на обычные переменные.
Формат: struct point *pp;
где pp – указатель на структуру типа struct point, *pp – сама структура, (*pp).x и (*pp).y – члены структуры.
Скобки (*pp).x необходимы, так как приоритет операции (.) выше приоритета операции (*). В случае отсутствия скобок *pp.x понимается как *(pp.x).
Инициализация указателя на структуру выполняется так же, как и инициализация указателей других типов: struct point var1, *S1; здесь var1 – структурная переменная, *S1 – указатель на структуру.
Для определения значения указателя ему нужно присвоить адрес уже сформированной структуры:
S1 = &var1;
Теперь возможно еще одно обращение к элементам структуры:
(*S1).name.
Указатели на структуры используются весьма часто, поэтому для доступа к ее полям была введена короткая форма записи. Если р – указатель на структуру, то p → <поле структуры> зволяет обратиться к указанному полю структурной переменной.
Знак → (стрелка) вводится с клавиатуры с помощью двух символов: '–' (минус) и '>' (больше). Например, pp → x; pp → y.
Операторы доступа к полям структуры (.) и (→) вместе с операторами вызова функции () и индексами массива [] занимают самое высокое положение в иерархии приоритетов операций в языке C.
Указатели на структуру используются в следующих случаях:
· доступ к структурам, размещенным в динамической памяти;
· создание сложных структур данных – списков, деревьев;
· передача структур в качестве параметров в функции.
К началу главы
12.4. Массивы структур
При необходимости хранения некоторых данных в виде нескольких массивов одной размерности, но разного типа, возможна организация массива структур. Наглядно массив структур можно представить в виде таблицы, где столбцы таблицы представляют собой поля структуры, а строки – элементы массива структур.
Например, имеется два разнотипных массива:
char c[N];
int i[N];
Объявление
struct key
{
char c;
int i;
} keytab[N];
создает тип структуры key и объявляет массив keytab[N], каждый элемент которого есть структура типа key.
Возможна запись:
struct key
{
char c;
int i;
};
struct key keytab[N];
Инициализация массива структур выполняется следующим образом:
struct key
{
char c;
int i;
} keytab[]={
'a', 0,
'b', 0
};
В этом примере создается массив на две структуры типа key с именем keytab. Рассмотрим обращение к полю структуры в этом случае – для примера выведем на экран содержимое массива:
for(int i=0;i<2;i++)
printf("%c %d\n",keytab[i].c,keytab[i].i);
При обращении к полю структуры сначала происходит обращение к элементу массива (keytab[i]), а затем только обращение к полю структуры (keytab[i].c).
Доступ к полю элемента массива структур может быть получен через константу-указатель на массив и смещение внутри массива, например, доступ к полю элемента массива с номером i следует записать следующим образом:
(*(keytab+i)).c или (keytab+i)→ c.
Массив структур также может быть передан в функцию в качестве аргумента, передача массива происходит через указатель на массив.
Пример программы, в которой массив точек формируется и выводится на экран с помощью функций:
#include <stdio.h>
#define N 5
struct point
{
int x,y;
};
void form_mas(struct point* mas, int n)
{
printf("Enter koordinates!\n");
for(int i=0;i<n;i++)
{
printf("x→");
scanf("%d",&mas[i].x);
printf("y→");
scanf("%d",&mas[i].y);
}
}
void print_mas(struct point* mas, int n)
{
printf(" x y\n");
for(int i=0; i<n; i++)
printf("%4d %6d\n",(mas+i)→x,(mas+i)→y);
}
int main()
{
struct point Points[N];
form_mas(Points,N);
print_mas(Points,N);
return 0;
}
Функция form_mas() заполняет массив точек, который передан в функцию через указатель mas. Параметр функции n определяет количество элементов массива. Доступ к элементу массива – через операцию . (точка). Выражение &mas[i].x вычисляет адрес элемента структуры mas[i].x, так как операция & имеет более низкий приоритет, чем операции [] и · (точка).
Функция print_mas() выводит массив на экран. Передача массива в функцию происходит также через указатель mas. Параметр n – количество элементов массива. Доступ к элементу массива – через операцию → (стрелка).
К началу главы
12.5. Вложенные структуры
Полем структурной переменной может быть переменная любого типа, в том числе другая структурная переменная. Поле, представляющее собой структуру, называется вложенной структурой.
Тип вложенной структуры должен быть объявлен раньше. Кроме того, структура не может быть вложена в структуру того же типа.
Объявление вложенной структуры:
struct point
{
int x,y;
};
struct rect
{
struct point LUPoint, RDPoint;
char BorderColor[20];
};
struct rect Rect;
В переменной Rect два поля LUPoint (точка, соответствующая левому верхнему углу прямоугольника) и RDPoint (точка, соответствующая правому нижнему углу) представляют собой вложенные структуры. Для доступа к полю вложенной структуры следует сначала обратится к внешней структуре, затем к вложенной: Rect.LUPoint.x.
Пример создания и использования вложенной структуры:
struct rect Rect={10,5,50,25,"White"};
printf("Параметры прямоугольника:\n");
printf("Координаты левого верхнего угла %d %d\n", Rect.LUPoint.x, Rect.LUPoint.y);
printf("Координаты левого верхнего угла %d %d\n", Rect.RDPoint.x, Rect.RDPoint.y);
printf("Цвет границы: %s\n", Rect.BorderColor);
В качестве поля структуры также можно использовать указатели на любые структуры, в том числе на структуры того же типа:
struct PointList
{
int x,y;
struct PointList* LastPoint;
};
Структуры, имеющие в своем составе поля-указатели на такую же структуру, используются для создания сложных структур данных – списков, деревьев.
C++. Динамические массивы
Обычно, объем памяти, необходимый для той или иной переменной, задается еще до процесса компиляции посредством объявления этой переменной. Если же возникает необходимость в создание переменной, размер которой неизвестен заранее, то используют динамическую память. Резервирование и освобождение памяти в программах на C++ может происходить в любой момент времени. Осуществляются операции распределения памяти двумя способами:
с помощью функции malloc, calloc, realloc и free;
посредством оператора new и delete.
Функция malloc резервирует непрерывный блок ячеек памяти для хранения указанного объекта и возвращает указатель на первую ячейку этого блока. Обращение к функции имеет вид:
void *malloc(size);
Здесь size — целое беззнаковое значение, определяющее размер выделяемого участка памяти в байтах. Если резервирование памяти прошло успешно, то функция возвращает переменную типа void *, которую можно привести к любому необходимому типу указателя.
Функция - calloc также предназначена для выделения памяти. Запись ниже означает, что будет выделено num элементов по size байт.
void *calloc (nime, size);
Эта функция возвращает указатель на выделенный участок или NULL при невозможности выделить память. Особенностью функции является обнуление всех выделенных элементов.
Функция realloc изменяет размер выделенной ранее памяти. Обращаются к ней так:
char *realloc (void *p, size);
Здесь p — указатель на область памяти, размер которой нужно изменить на size. Если в результате работы функции меняется адрес области памяти, то новый адрес вернется в качестве результата. Если фактическое значение первого параметра NULL, то функция realloc работает также, как и функция malloc, то есть выделяет участок памяти размером size байт.
Для освобождения выделенной памяти используется функция free. Обращаются к ней так:
void free (void *p size);
Здесь p — указатель на участок памяти, ранее выделенный функциями malloc, calloc или realloc.
Операторы new и delete аналогичны функциям malloc и free. New выделяет память, а его единственный аргумент — это выражение, определяющее количество байтов, которые будут зарезервированы. Возвращает оператор указатель на начало выделенного блока памяти. Оператор delete освобождает память, его аргумент — адрес первой ячейки блока, который необходимо освободить.
Динамический массив — массив переменной длины, память под который выделяется в процессе выполнения программы. Выделение памяти осуществляется функциями calloc, malloc или оператором new. Адрес первого элемента выделенного участка памяти хранится в переменной, объявленной как указатель. Например, следующий оператор означает, что описан указатель mas и ему присвоен адрес начала непрерывной области динамической памяти, выделенной с помощью оператора new:
int *mas=new int[10];
Выделено столько памяти, сколько необходимо для хранения 10 величин типа int.
Фактически, в переменной mas хранится адрес нулевого элемента динамического массива. Следовательно, адрес следующего, первого элемента, в выделенном участке памяти - mas+1, а mas+i является адресом i-го элемента. Обращение к i-му элементу динамического массива можно выполнить, как обычно mas[i], или другим способом *(mas +i). Важно следить за тем, чтобы не выйти за границы выделенного участка памяти.
Когда динамический массив (в любой момент работы программы) перестает быть нужным, то память можно освободить с помощью функции free или оператора delete.
4. Свя́зный спи́сок — базовая динамическая структура данных в информатике, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка.[1] Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.
Линейный связный список[править | править исходный текст]
Односвязный список (Однонаправленный связный список)[править | править исходный текст]
Здесь ссылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла, невозможно.
Двусвязный список (Двунаправленный связный список)[править | править исходный текст]
Здесь ссылки в каждом узле указывают на предыдущий и на последующий узел в списке. По двусвязному списку можно передвигаться в любом направлении — как к началу, так и к концу. В этом списке проще производить удаление и перестановку элементов, так как всегда известны адреса тех элементов списка, указатели которых направлены на изменяемый элемент.
XOR-связный список[править | править исходный текст]
Основная статья: XOR-связный список
Кольцевой связный список[править | править исходный текст]
Разновидностью связных списков является кольцевой (циклический, замкнутый) список. Он тоже может быть односвязным или двусвязным. Последний элемент кольцевого списка содержит указатель на первый, а первый (в случае двусвязного списка) — на последний.
Реализация такой структуры происходит на базе линейного списка. В каждом кольцевом списке есть указатель на первый элемент. В этом списке константы NULL не существует.
Также существуют циклические списки с выделенным головным элементом, облегчающие полный проход через список.
5.СТЕКИ
Стек — это особый способ хранения данных, при котором в каждый момент времени доступ возможен только к одному из элементов, а именно к тому, который был занесен в стек последним. Часто главный принцип стека формулируют в виде: “первым пришел — последним вышел” (в англоязычной литературе применяется более строгий термин LIFO — это сокращение от Last In — First Out, что означает последним пришел — первым вышел).
При описании работы стека принято говорить, что он имеет фиксированное основание (нижнюю границу, дно) и подвижную вершину, через которую, собственно, и происходит запись и чтение данных (см. рис. 1).
Рис. 1
В начальный момент времени основание и вершина стека совпадают. По мере записи данных область, занятая информацией (на рис. 1 она закрашена серым цветом), расширяется; вершина стека при этом смещается вверх. При извлечении данных из стека происходит противоположный процесс. Когда стек свободен от данных (вершина и основание совпадают), попытка считывания данных является грубой ошибкой. В другом предельном случае, когда данных чрезмерно много (вершина совпадает с верхней границей области памяти, отведенной под стек), некорректной, напротив, становится запись.
Над стеком можно определить следующие операции:
· добавление нового элемента в стек (общепринят термин PUSH — “заталкивать” в стек);
· извлечение элемента из стека (POP — “выталкивать” из стека);
· операции по изменению верхнего элемента стека (так как операнд один, то такие операции называют “унарными”);
· бинарные операции с двумя извлеченными из стека верхними элементами; результат возвращается обратно в вершину стека.
Подчеркнем, что все приведенные выше принципы настолько общие, что пока никак не связаны с компьютерной реализацией. А теперь подумаем, как практически реализовать стек в памяти машины.
Прежде всего очевидно, что для манипуляций со стеком нужно где-то постоянно хранить координаты (адрес) текущего положения вершины стека. Договоримся называть эту важнейшую характеристику указателем, но пока не будем конкретизировать место его хранения, обозначая в максимально общем виде R — некоторый регистр процессора.
Учитывая, что стек может расти как в сторону увеличения, так и в сторону уменьшения адресов, а также тот факт, что существуют равноправные договоренности о последовательности операций при записи/чтении (например, сначала менять адрес, а потом читать данные или наоборот), возможно предложить несколько разных вариантов организации стека в оперативной памяти (ОЗУ). Тем не менее, несмотря на теоретическое разнообразие, программисты практически всегда строят стек единообразно. А именно, при заполнении стека значение указателя уменьшается, а при извлечении данных — растет. Кроме того, для записи данных используется алгоритм, который можно обозначить как “–(R)”, т.е. сначала значение указателя уменьшается, а затем происходит запись данных. Очевидно, что такой выбор предопределяет алгоритм чтения типа “(R)+”, при котором сперва считываются данные, а затем наращивается указатель стека.
Стек — метод неявной адресации
Как следует из описанных выше принципов, конкретный адрес при обращении к памяти берется из указателя стека. Например, для записи в стек содержимого некоторого регистра Ri достаточно указать команду PUSH Ri, никак не ссылаясь на адрес информации в ОЗУ. Подобные способы обращения к данным, когда адрес данных не указывается, а подразумевается, принято называть неявными.
Стек является одним из образцов неявной адресации, причем очень развитым и необычайно полезным образцом. “Важным преимуществом стека по сравнению с адресной организацией памяти является то, что его элементами можно манипулировать, не адресуясь к ним явно, не называя их имени” [2].
Очевидным преимуществом неявной адресации является короткая форма записи программы и ее практически полная независимость от конкретных адресов ОЗУ (программы, которые способны без изменения исполняться с любого адреса памяти, часто называют перемещаемыми). И хотя это весьма важное с теоретической точки зрения достоинство, истинное значение стекового метода адресации все же не в этом: данный механизм позволяет реализовать многие структуры алгоритмов или данных, которые без него осуществить необычайно сложно. Рассмотрим показательный, хотя и не совсем тривиальный, пример из книги [3].
“Во всех языках программирования есть понятие процедур с локальными переменными. Эти переменные доступны во время выполнения процедуры, но перестают быть доступными после окончания процедуры. Возникает вопрос: где должны храниться такие переменные?
К сожалению, предоставить каждой переменной абсолютный адрес в памяти невозможно. Проблема заключается в том, что процедура может вызывать себя сама… Достаточно сказать, что если процедура вызывается дважды, то хранить ее переменные под конкретными адресами в памяти нельзя, поскольку второй вызов нарушит результаты первого”.
Стековая память является простым и весьма эффективным решением сформулированной проблемы.
7.Линейная сортировка, метод пузырька
Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²).
Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка.
Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).
Линейная сортировка (сортировка отбором)
Идея линейной сортировки по невозрастанию заключается в том, чтобы, последовательно просматривая весь массив, отыскать наибольшее число и поменять его местами с первым элементом. Затем просматриваются элементы массива, начиная со второго, снова находится наибольший, который меняется местами со вторым и т. д. (листинг 4.5).
Листинг 4.5. Программа линейной сортировки по невозрастанию
const count=20;
m: array [1..count] of byte = (9,11,12,3,19,1,5,17,10,18,3,19,17,9,12,20,20,19,2,5);
var i,j,buf,l: byte; a: integer;
begin
writeln('Исходный массив:');
for i:=1 to count do write(' ', m[i]);
writeln; readln;
a:=0; { обнуляем счетчик итераций }
{ изменение размера неотсортированной части массива }
for i:=1 to count-1 do
{ сравниваем поочередно i-й элемент неотсортированной части массива }
{ со всеми от i+1-го до конца }
for j:=i+1 to count do
begin
a:=a+1;
if m[i]
{ нашли элемент, больший, чем i-й, то меняем их местами }
begin
buf := m[i]; { buf — буфер обмена }
m[i] := m[j] ;
m[j] := buf;
end;
for 1:=1 to count do write(' ', m[l]); { после сортировки }
writeln('; итерация # ', a);
end;
end.
По последнему значению а определяем, что для данного массива линейная сортировка по невозрастанию выполняется за 190 итераций.
8.Сортировка вставкой, посредством выбора.
Сортировка вставкой
Упорядоченный массив B' получается из В следующим образом: сначала он состоит из единственного элемента К1; далее для i=2,...,N выполняется вставка узла Кi в B' так, что B' остается упорядоченным списком длины i.
Например, для начального списка B=< 20,-5,10,8,7 > имеем:
B=< 20,-5,10,8,7> B'=< >
B=< -5,10,8,7 > B'=< 20 >
B=< 10,8,7 > B'=< -5,20 >
B=< 8,7 > B'=< -5,10,20 >
B=< 7 > B'=< -5,8,10,20 >
B=< > B'=< -5,7,8,10,20 >
Функция insert реализует сортировку вставкой.
/* сортировка методом вставки */
float *insert(float *s, int m, int n)
{
int i,j,k;
float aux;
for (i=m+1; i<=n; i++)
{ aux=s[i];
for (k=m; k<=i && s[k]=k; j--) s[j+1]=s[j];
s[k]=aux;
}
return(a);
}
Здесь оба списка В и В' размещаются в массиве s, причем список В занимает часть s c индексами от i до n, а B' - часть s c индексами от m до i-1 (см. рис.26).
При сортировке вставкой требуется Q=(n-m)*(n-m) сравнений и не требуется дополнительной памяти.
Рис.26. Схема движения индексов при сортировке вставкой.
2.2.3. Сортировка посредством выбора
Упорядоченный список В' получается из В многократным применением выборки из В минимального элемента, удалением этого элемента из В и добавлением его в конец списка В', который первоначально должен быть пустым.
Например:
B=<20,10,8,-5,7>, B'=< >
B=<20,10,8,7>, B'=<-5>
B=<20,10,8>, B'=<-5,7>
B=<20,10>, B'=<-5,7,8>
B=<20>, B'=<-5,7,8,10>
B=< >, B'=<-5,7,8,10,20> .
Функция select упорядочивает массив s сортировкой посредством выбора.
/* сортировка методом выбора */
double *select( double *s, int m, int n)
{
int i,j;
double c;
for (i=m; is[j])
{ c=s[i];
s[i]=s[j];
s[j]=c;
}
return(s);
}
Здесь, как и в предыдущем примере оба списка В и В' размещаются в разных частях массива s (см. рис.27). При сортировке посредством выбора требуется Q=(n-m)*(n-m) действий и не требуется дополнительной памяти.
Рис.27. Схема движения индексов при сортировке выбором.
Сортировка квадратичной выборкой. Исходный список В из N элементов делится на М подсписков В1,В2,...,Вm, где М равно квадратному корню из N, и в каждом В1 находится минимальный элемент G1. Наименьший элемент всего списка В определяется как минимальный элемент Gj в списке , и выбранный элемент Gj заменяется новым наименьшим из списка Bj. Количество действий, требуемое для сортировки квадратичной выборкой, несколько меньше, чем в предыдущих методах Q= N*N, но требуется дополнительная память для хранения списка G.
9.Сортировка списков путем слияния.
Сортировка слиянием — вероятно, один из самых простых алгоритмов сортировки (среди «быстрых» алгоритмов). Особенностью этого алгоритма является то, что он работает с элементами массива преимущественно последовательно, благодаря чему именно этот алгоритм используется при сортировке в системах с различными аппаратными ограничениями (например, при сортировке данных на жёстком диске, или даже на магнитной ленте). Кроме того, сортировка слиянием — чуть ли не единственный алгоритм, который может быть эффективно использован для сортировки таких структур данных, как связанные списки. Последовательная работа с элементами массива значительно увеличивает скорость сортировки в системах с кэшированием.
Сортировка слиянием — стабильный алгоритм сортировки. Это означает, что порядок «равных» элементов не изменяется в результате работы алгоритма. В некоторых задачах это свойство достаточно важно.
Этот алгоритм был предложен Джоном фон Нейманом в 1945 году
Везде в лекции элементы массивов нумеруются с нуля.
Допустим, у нас есть два отсортированных массива A и B размерами и соответственно, и мы хотим объединить их элементы в один большой отсортированный массив C размером . Для этого можно применить процедуру слияния, суть которой заключается в повторяющемся «отделении» элемента, наименьшего из двух имеющихся в началах исходных массивов, и присоединении этого элемента к концу результирующего массива. Элементы мы переносим до тех пор, пока один из исходных массивов не закончится. После этого оставшийся «хвост» одного из входных массивов дописывается в конец результирующего массива. Пример работы процедуры показан на рисунке:
Рис. 1. Пример работы процедуры слияния
Алгоритм слияния формально можно записать следующим образом:
|
(1) |
Для обеспечения стабильности алгоритма сортировки нужно, чтобы в случае равенства элементов тот элемент, что идёт раньше во входном массиве, попадал в результирующий массив в первую очередь. Мы увидим далее, что если два элемента попали в разные массивы (A и B), то тот элемент, что шёл раньше, попадёт в массив A. Следовательно, в случае равенства элемент из массива A должен иметь приоритет. Поэтому в алгоритме стои́т знак вместо < при сравнении элементов.
Недостатком представленного алгоритма является необходимость дописывать оставшийся кусок, из-за чего при дальнейших модификациях алгоритма нам придётся писать много повторяющегося кода. Чтобы этого избежать, будем использовать чуть менее эффективный, но более короткий алгоритм, в котором копирование «хвоста» встроено в основной цикл:
|
(2) |
Очевидно, время работы процедуры слияния составляет .
Реализация процедуры слияния на языке программирования C++ представлена в листинге 1.
template<class T> void Merge(T const *const A, int const nA,
T const *const B, int const nB,
T *const C)
{ //Выполнить слияние массива A, содержащего nA элементов,
// и массива B, содержащего nB элементов.
// Результат записать в массив C.
int a(0), b(0); //Номера текущих элементов в массивах A и B
while( a+b < nA+nB ) //Пока остались элементы в массивах
{
if( (b>=nB) || ( (a<nA) && (A[a]<=B[b]) ) )
{ //Копирую элемент из массива A
C[a+b] = A[a];
++a;
} else { //Копирую элемент из массива B
C[a+b] = B[b];
++b;
}
}
}
Листинг 1. Компактная (не самая быстрая) реализация процедуры слияния
Процедура слияния требует два отсортированных массива. Заметив, что массив из одного элемента по определению является отсортированным, мы можем осуществить сортировку следующим образом:
Проще всего формализовать этот алгоритм рекурсивным способом (в следующем разделе мы реализуем этот алгоритм итерационным способом). Функция сортирует участок массива от элемента с номером a до элемента с номером b:
|
(3) |
Поскольку функция сортирует лишь часть массива, то при слиянии двух фрагментов ей не остаётся ничего, кроме как выделять временный буфер для результата слияния, а затем копировать данные обратно:
template<class T> void MergeSort(T *const A, int const n)
{ //Отсортировать массив A, содержащий n элементов
if( n < 2 ) return; //Сортировка не нужна
if( n == 2 ) //Два элемента проще поменять местами,
{ // если нужно, чем делать слияние
if( A[0] > A[1] ) { T const t(A[0]); A[0]=A[1]; A[1]=t; }
return;
}
MergeSort(A , n/2 ); //Сортируем первую половину
MergeSort(A+n/2, n-n/2); //Сортируем вторую половину
T *const B( new T[n] ); //Сюда запишем результат слияния
Merge(A,n/2, A+n/2,n-n/2, B); //Слияние половин
//Копирование результата слияния в исходный массив:
for(int i(0); i<n; ++i) A[i]=B[i];
delete[n] B; //Удаляем временный буфер
}
Листинг 2. Реализация сортировки слиянием
Время работы сортировки слиянием составляет . Пример работы процедуры показан на рисунке:
Рис. 2. Пример работы рекурсивного алгоритма сортировки слиянием
Программа, представленная в листинге 2, имеет серьёзные недостатки: она выделяет и освобождает много буферов памяти, и делает копирование результатов слияния в исходный массив вместо того, чтобы вернуть новый массив в качестве результата (она не может вернуть новый массив в качестве результата, т.к. на входе получает зачастую лишь часть большого массива).
Чтобы избавиться от этих недостатков, откажемся от рекурсивной реализации, и сделаем сортировку следующим образом:
Такой алгоритм называется восходящей сортировкой слиянием. Реализация его на языке программирования C++ приведена в листинге 3.
template<class T> void MergeSortIterative(T *&A, int const n)
{ //Отсортировать массив A, содержащий n элементов.
// При работе указатель на A, возможно, меняется.
// (Функция получает ссылку на указатель на A)
T *B( new T[n] ); //Временный буфер памяти
for(int size(1); size<n; size*=2)
{ //Перебираем все размеры кусочков для слияния: 1,2,4,8...
int start(0); //Начало первого кусочка пары
for(; (start+size)<n; start+=size*2)
{ //Перебираем все пары кусочков, и выполняем попарное
// слияние. (start+size)<n означает, что начало
// следующего кусочка лежит внутри массива
Merge(A+start , size,
A+start+size, min(size,n-start-size),
B+start );
}
//Если последний кусочек остался без пары, просто копи-
// руем его из A в B:
for(; start<n; ++start) B[start]=A[start];
T *temp(B); B=A; A=temp; //Меняем местами указатели
}
delete[n] B; //Удаляем временный буфер
}
Листинг 3. Реализация восходящей сортировки слиянием
К сожалению, в этот алгоритм не так просто вписать оптимизацию для случая слияния двух элементов (если нужно, можно вписать эту оптимизацию в процедуру Merge).
Пример работы программы листинга 3 показан на рисунке:
Рис. 3. Пример работы восходящего алгоритма сортировки слиянием
Если требуется выполнять восходящую сортировку для части массива, или в других случаях, когда указатель на массив менять нельзя, то будет полезной модификация программы, которая, если нужно, копирует результат в исходный массив в конце работы:
template<class T> void MergeSortIter2(T *const A, int const n)
{ //Отсортировать массив A, содержащий n элементов.
T *B( A ); //Буфер памяти №1
T *C( new T[n] ); //Буфер памяти №2
for(int size(1); size<n; size*=2)
{ //Перебираем все размеры кусочков для слияния: 1,2,4,8...
int start(0); //Начало первого кусочка пары
for(; (start+size)<n; start+=size*2)
{ //Перебираем все пары кусочков, и выполняем попарное
// слияние. (start+size)<n означает, что начало
// следующего кусочка лежит внутри массива
Merge(B+start , size,
B+start+size, min(size,n-start-size),
C+start );
}
//Если последний кусочек остался без пары, просто копи-
// руем его из B в C:
for(; start<n; ++start) C[start]=B[start];
T *temp(B); B=C; C=temp; //Меняем местами указатели
}
//В данный момент результат работы находится в массиве B.
if( C == A )
{ // Если массив C является массивом A, то нужно
// скопировать результат работы из B в A.
for(int i(0); i<n; ++i) A[i]=B[i];
delete[n] B; //Удаляем временный буфер
} else {
delete[n] C; //Удаляем временный буфер
}
}
Листинг 4. Реализация восходящей сортировки слиянием
с сохранением результата работы в исходном массиве
Измерим быстродействие программы из листинга 3. Условия измерения — те же, что для алгоритма пирамидальной сортировки (см. лекцию 5).
На рис. 4 показан график величины , определяемой выражением:
|
(4) |
где n — количество сортируемых псевдослучайных четырёхбайтовых целых чисел, — время сортировки на моём компьютере.
Рис. 4. Отношение времени сортировки к .
Красный цвет — сортировка слиянием,
серый цвет — пирамидальная сортировка
На графике проявляются две важные особенности алгоритма:
10.Быстрая сортировка.
Быстрая сортировка (англ. quicksort), часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известныйалгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году. Один из самых быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов); из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.
QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов.
Общая идея алгоритма состоит в следующем:
На практике массив обычно делят не на три, а на две части, например, «меньшие опорного» и «равные и большие». Такой подход в общем случае эффективнее, так как упрощает алгоритм разделения (см. ниже).
Хоар разработал этот метод применительно к машинному переводу; словарь хранился на магнитной ленте, и сортировка слов обрабатываемого текста позволяла получить их переводы за один прогон ленты, без перемотки её назад. Алгоритм был придуман Хоаром во время его пребывания в Советском Союзе, где он обучался в Московском университетекомпьютерному переводу и занимался разработкой русско-английского разговорника.
Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:
Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута обязательно и обработка гарантированно завершится.
Ясно, что операция разделения массива на две части относительно опорного элемента занимает время . Поскольку все операции разделения, проделываемые на одной глубине рекурсии, обрабатывают разные части исходного массива, размер которого постоянен, суммарно на каждом уровне рекурсии потребуется также операций. Следовательно, общая сложность алгоритма определяется лишь количеством разделений, то есть глубиной рекурсии. Глубина рекурсии, в свою очередь, зависит от сочетания входных данных и способа определения опорного элемента.
Лучший случай.
В наиболее сбалансированном варианте при каждой операции разделения массив делится на две почти одинаковые части, следовательно, максимальная глубина рекурсии, при которой размеры обрабатываемых подмассивов достигнут 1, составит . В результате количество сравнений, делаемых быстрой сортировкой, было бы равно значению рекурсивного выражения , что даёт общую сложность алгоритма .
Среднее.
Среднюю сложность при случайном распределении входных данных можно оценить лишь вероятностно.
Прежде всего необходимо заметить, что в действительности необязательно, чтобы опорный элемент всякий раз делил массив на две одинаковых части. Например, если на каждом этапе будет происходить разделение на массивы длиной 75 % и 25 % от исходного, глубина рекурсии будет равна , а это по-прежнему даёт сложность . Вообще, при любом фиксированном соотношении между левой и правой частями разделения сложность алгоритма будет той же, только с разными константами.
Будем считать «удачным» разделением такое, при котором опорный элемент окажется среди центральных 50 % элементов разделяемой части массива; ясно, вероятность удачи при случайном распределении элементов составляет 0,5. При удачном разделении размеры выделенных подмассивов составят не менее 25 % и не более 75 % от исходного. Поскольку каждый выделенный подмассив также будет иметь случайное распределение, все эти рассуждения применимы к любому этапу сортировки и любому исходному фрагменту массива.
Удачное разделение даёт глубину рекурсии не более . Поскольку вероятность удачи равна 0,5, для получения удачных разделений в среднем потребуется рекурсивных вызовов, чтобы опорный элемент k раз оказался среди центральных 50 % массива. Применяя эти соображения, можно заключить, что в среднем глубина рекурсии не превысит , что равно А поскольку на каждом уровне рекурсии по-прежнему выполняется не более операций, средняя сложность составит .
Худший случай.
В самом несбалансированном варианте каждое разделение даёт два подмассива размерами 1 и , то есть при каждом рекурсивном вызове больший массив будет на 1 короче, чем в предыдущий раз. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых. При простейшем выборе опорного элемента — первого или последнего в массиве, — такой эффект даст уже отсортированный (в прямом или обратном порядке) массив, для среднего или любого другого фиксированного элемента «массив худшего случая» также может быть специально подобран. В этом случае потребуется операций разделения, а общее время работы составит операций, то есть сортировка будет выполняться за квадратичное время. Но количество обменов и, соответственно, время работы — это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти (переполнению стека) во время работы программы.
Достоинства:
Недостатки:
Улучшения алгоритма направлены, в основном, на устранение или смягчение вышеупомянутых недостатков, вследствие чего все их можно разделить на две группы: придание алгоритму устойчивости и «защита от худшего случая» — устранение деградации производительности и переполнения стека вызовов из-за большой глубины рекурсии при неудачных входных данных.
Что касается первой проблемы, то она элементарно решается путём расширения ключа исходным индексом элемента в массиве. В случае равенства основных ключей сравнение производится по индексу, исключая, таким образом, возможность изменения взаимного положения равных элементов. Эта модификация не бесплатна — она требует дополнительно O(n) памяти и одного полного прохода по массиву для сохранения исходных индексов.
Вторая проблема, в свою очередь, решается по двум разным направлениям: снижение вероятности возникновения худшего случая путём специального выбора опорного элемента и применение различных технических приёмов, обеспечивающих устойчивую работу на неудачных входных данных. Для первого направления:
Недостаток всех усложнённых методов выбора опорного элемента — дополнительные накладные расходы; впрочем, они не так велики.
Во избежание отказа программы из-за большой глубины рекурсии могут применяться следующие методы:
Имеется викиучебник по теме
«Примеры реализации быстрой сортировки»
Множество примеров реализации алгоритма (включая полностью нерекурсивный) можно найти в WikiBooks по приведённой ссылке. В данном разделе приводится лишь пара примеров наиболее типичной реализации на процедурном (Pascal) и функциональном (Erlang) языках.
|
// Реализация на языке pascal // Если раскомментировать строки кода, начинающиеся с "//", // то получится реализация с одной рекурсивной ветвью, в которой // меньшая часть разделённого массива сортируется рекурсивным вызовом, // а бо'льшая - в цикле, что гарантирует глубину рекурсии не более lg(N). procedure qSort(var ar: array of real); // Вложенная функция сортировки для рекурсивного вызова // Нужна, чтобы не передавать в вызов основной функции границы массива procedure sort(var ar: array of real; low, high: integer); var i, j: integer; m, wsp: real; begin // repeat i:=low; j:=high; m:=ar[(i+j) div 2]; // Взятие среднего опорного элемента repeat while ar[i]<m do Inc(i); while ar[j]>m do Dec(j); if i<=j then begin wsp:=ar[i]; ar[i]:=ar[j]; ar[j]:=wsp; Inc(i); Dec(j); end; until i>j; // if (j - low) < (high - i) then begin if low<j then sort(ar, low, j); // low := i; // end // else begin if i<high then sort(ar, i, high); // high := j; // end; //until low = high; end; begin sort(ar, 0, High(ar)); end; |