Алгоритмы сортировки. Основные понятия. Внутренние cортировки.

Алгоритмы сортировки применяются тогда, когда требуется упорядочить данные произвольной, но одной и той же природы в соответствии с заданным отношением порядка. Свойства данных, определяющие порядок их следования после сортировки, называют ключом сортировки (sort key). Чаще всего отношения порядка для сортировки определяют так, чтобы упорядочение выполнялось в восходящем или ненисходящем порядке, не различая эти случаи. Говорят, что сортировка устойчива, если для любой пары сортируемых данных a и b c с идентичными ключами таких, что а предшествуя b до сортировки, а будет предшествовать b и после сортировки. Т.е. устойчивая сортировка сохраняет относительный порядок с идентичными ключами. Сортировку называют сортировкой на месте, если сортируемая совокупность данных до и после сортировки занимает то же самое место хранения, т.е. сортировка на месте не копирует совокупность сортируемых данных. Если сортируемые данные могут быть одновременно размещены в ОП, то для них применяются сортировки в массиве, которые называют внутренними сортировками. Если же все сортируемые данные одновременно разместить в ОП нельзя, то для них применяют методы сортировки в файле, которые называют внешними сортировками. Наиболее часто применяются след.внутренние сортировки: 1) сортировка выбором 2) пузырьковая сортировка 3) сортировка вставками 4) быстрая сортировка

Сортировка выбором: среди сортируемых элементов выбирается максимальный и располагается в подходящем месте, т.е. на месте последнего среди них, затем выбирается максимальный среди оставшихся и располагается на подходящем месте, т.е. на месте последнего среди них и т.д. до тех пор, пока неупорядоченным останется 1 элемент. Выбор максимального элемента выполняется функцией max, которая возвращает указатель на него, а функция swap меняет его местами с последним среди рассматриваемых.

Void delayedssort(int a[ ], unsigned first, unsigned last)

{ unsigned int k;

For (k=last; k>first; k--)

Swap (max (a,first,k)a+k);

Выбор элемента, который в соответствии с заданным отношением порядка, должен быть последним(первым) в рассматриваемой части массива можно выполнить разными способами. Так в методе delayedssort для этого используется алгоритм поиска максимального(минимального) и найденный элемент обменивается значениями с последним(первым) из рассматриваемых. Но можно поступить и так: поочерёдно сравнить сортируемые элементы с последним(первым) из них и если он должен предшествовать (следовать за) рассматриваемому(ым), то обменять их значениями. Метод в этом случае называют сортировкой простым выбором(simple selection sort)

Пузырьковая сортировка (Bubble Sort): последовательно сравниваются пары соседних элементов сортируемой части массива, начиная с 2-х последних (первых) и если порядок для них нарушен, то они меняются местами. После просмотра всех пар наименьший (наибольший) элемент окажется на своём месте, т.е. первым (последним) по порядку среди рассматриваемых. Процесс повторяется для остальных элементов, в результате 2-ой (предпоследний) по порядку элемент окажется на своём месте и так до тех пор, пока неотсортированным в рассматриваемой части массива останется 1 элемент.

Сортировка вставками(Insertion Sort): поочерёдно просматриваются элементы сортируемой части массива, начиная со 2-го(предпоследнего) и каждый из их вставляется на подходящее место среди уже упорядоченных в соответствии с заданным отношением порядка предшествующих ему (следующих за ним) элементов массива. Поиск подходящего места может осуществляться методом линейного или двоичного поиска. В 1-ом случае метод называют сортировкой линейными вставками (Linear Insertion Sort), во 2-ом – сортировкой двоичными вставками (Binary Insertion Sort).

Быстрая сортировка (Quick Sort) Этот метод сортировки был разработан Хоаром и при сортировке больших объёмов данных является самым эффективным из рассматриваемых. Он состоит в след.: значение 1-го из рассматриваемых элементов массива принимается за эталонное и элементы рассматриваемой части массива распределяются в ней так, что в начале оказываются все элементы , которые в соответствии с заданным отношением порядка не должны следовать за эталоном, а за ними все элементы, которые не должны предшествовать эталону. Затем этот же процесс повторяют для каждой из этих частей и так до тех пор, пока в рассматриваемых частях последовательности останется не более 1 элемента.

7. Программа на СИ и СИ++. Общая структура программы.

В общем случае СИ-программа как алгоритм представляет собой сов-ть вызывающих друг друга функций, среди которых обязательно должна быть ф-я main ( ), с которой начинается её выполнение. Простая СИ-программа может состоять только из этой ф-ии, начинающейся с заголовка вида main ( ), за которым идёт описание алгоритма, реализуемого программой. В соответствии с принципами структурного программирования представляет собой структуру следования, т.е. описывается составным оператором (посл-ть объявлений и операторов, заключенные в фигурные скобки. Каждое объявление и оператор заканчивается ; ).

Для ввода данных с клавиатуры в Си используется функция scanf, а для вывода на экран - printf.

Структура следования: { <s1>; - объявления и операторы

<s2>; …

<s3>; }

Структура ветвления реализуется уловным оператором: if (<p>) <s1>; - <p> условие

Else <s2>; - операторы

Оператор цикла с предусловием: while (<p>) <s>; - <p>-оператор, описывающий условие продолжения цикла, <s> - оператор, описывающий тело цикла.

Оператор цикла с постусловием: do <s> while (<p>);

Лексическая структура СИ и СИ++.

Текст программы формируется из конечного набора символов, образующих алфавит языка. Алфавит – сов-ть символов, которые можно использовать в тексте программы. Алфавит СИ образуют буквы лат алфавита (прописные и строчные), цифры, спец символы (+ - , . ;)

Символы алфавита используются для построения лексем. Лексема – мин единица языка, имеющая самостоятельный смысл.

Лексемы: служебные (ключевые, зарезервированные) слова составляют основу языка и имеют строго фиксированное написание и смысл; идентификаторы используют для образования имен и формируются по строго определенному правилу. Служебные слова не могут использоваться как идентиф-ры!

Идентификаторы в СИ – посл-ть прописных и строчных букв, цифр, символа подчёркивания, неначинающиеся с цифр. Они различаются по первым 8 символам, хотя исп-ть можно и больше.

Литералы исп-ся для задания буквальных констант (целые, вещ-е числа, символьные, строковые константы).

Знаки операций определяют действие, выполняемое над данными.

Разделители определяют структуру, внешний вид, читабельность программы, как текста, опис-го алгоритмом.

Комментарии – фрагменты поясняющего текста, невлияющие на ход выполнения программы. В СИ-программе комменты начинаются символами /* */ и не могут быть вложенными.

Правила составления текста программы из лексем опред-ся синтаксисом языка.

Синтаксис языка программирования – сов-ть формальных правил записи конструкций языка. Смысловое значение синтаксич конструкций языка, т.е. определяемая ими посл-ть действий, описываемого алгоритма, определяется семантикой языка программирования.

СИ++. Комментарии начинаются // и заканчиваются в конце строки. Частично решена проблема вложения комментариев.

9. Концепция данных в СИ и СИ++. Данные. Тип данных. Понятие класса в СИ++

Данные в программе играют роль величин, над которыми производятся определённые операции. Например, над целыми числами может быть операция умножения, а для символов она смысла не имеет. Так, не над всеми величинами (объектами данных) можно выполнить ту или иную операцию. Множество величин, для которых естественным образом определено некоторое количество операций, наз. типом данных. Итак, операции, которые можно производить над данными, определяются тем, к какому типу оно принадлежит. В комп-ре данные размещаются так, чтобы определенных для них операции выполнялись, как можно, эффективнее. В каждый язык программирования встроены типы, для которых определены операции и способ представления в комп-ре. В СИ они указываются служебными словами: char, int, float, double. Например, int x;

В СИ++ сущ логический тип bool, который предполагает представление значений истинности: истина и ложь, которые рассматриваются как константы данного типа. В СИ, чтобы использовать этот тип, его надо описать как перечисляемый: enum bool{false, true};

В СИ можно присваивать значение типа void* переменной-указателю любого типа. В СИ++ для такого преобразования необходимо явное преобразование типов.

В СИ для представления символьных констант, например ‘A’, используется тип int. В СИ++ символьная константа имеет тип char.

Понятие класса – основа ООП и является развитием понятия типа данных. Тип данных – мн-во значений с определёнными над ними операциями. Класс – сов-ть объектов данных с определенными для них методами обработки. Описание класса в СИ++ похоже на описание структурного типа, но начинается со служебного слова class вместо struct. Но вместе с описанием компонент переменных класс содержит описание компонент функции. Сов-ть переменных класса описывает структуру обрабатываемых данных, а сов-ть функций – метод их обработки. Компоненты класса делятся на элементы-данные и элементы-функции. При описании класса элемент-функция может полностью определена или только объявлена, а определить её можно вне класса. Элемент-функция, определенная в пределах описания класса, наз встроенной. В классе допустимо использование перегружаемых элементов-функций. Используется класс путём определения переменных, типом которого он является. Такая переменная наз экземпляром класса или объектом класса.

Понятие константы в СИ и С++. Типы констант

Все обрабатываемые программой данные рассматриваются как константы и переменные. Константа – это данное, которое не может изменять своего значения в процессе выполнения программы. Пример: числа, для записи которых в СИ-программе используются литералы.

Все языки программирования высокого уровня позволяют использовать 10ю запись. Для разделения целой и дробной части исп-ся точка. Экспоненциальная форма исп-ся для записи больших или мылых по модулю вещ-х чисел. Например, 5,021587 -10⁵⁵. В программировании такая запись наз форма с плавающей точкой. Обычная запись чисел наз с фиксированной точкой. Например, 5,04545е55, где 5,04545-мантисса, 55-порядок, е – отделяет мантиссу от порядка и обозначает «на 10 в степени».

В СИ целые числа могут быть записаны в 8 и 16чной системе счисления. Запись 8го целого числа нач-ся с 0 и может содержать цифры от 0до 7. Запись 16го целого числа начинается 0х или ОХ и может содержать цифры от 0 до 9 и буквы А(а) до F(f), допустимо смешение больших и малых букв. 10я записб числа не может начинаться с 0. Целые числа могут иметь значения от 0 и до макс значения типа unsigned long int и не могут быть отриц. Вещ-е числа могут быть любыми. Если число имеет непредставимое значение, то оно заменяется представимым.

Каждая константа в программе имеет тип, которые определяет её значение в компьютере и операции, производимые над ней. Тип числовой константы, записанный литералом, - буквальной константы – определяется её записью и значением. Если в записи нет точки или буквы е (Е), то константа целая, иначе – вещ-я. В программе часто исп-т константы, представляющие текст – строковые константы – это посл-ть символов в кавычках. Символы могут быть любыми. Стр-я константа должна быть записана в 1 строке текста программы.

Переменные – это основные элементы языка, используемые для размещения данных в памяти. Они определяют область в памяти (ячейку), где размещается данное, являющееся значением этой переменной. Обращение к этой ячейке производится по имени переменной. Переменные именуются идентификаторами. Значение переменной можно изменять. Для того, чтобы исп-ть переменную в программе, её надо объявить (описать). В простейшей СИ-программе объявление выглядит так: <тип>< имя переменной>; Смысл данной конструкции: в памяти под переменную зарезервирована ячейка, куда в ходе выполнения программы записывается её значение в формате соотв-го типа. Процесс выделения памяти под переменную наз размещением переменной.

В СИ для представления символьных констант, например ‘A’, используется тип int. В СИ++ символьная константа имеет тип char.

В СИ использование модификатора const при определении переменной обозначает, что её значение не может быть изменено после инициации. В СИ++ так определяется константа. Поэтому в отличии от СИ в СИ++ её применяют для указания размера при определении массива, т.е. вместо #define NMAX=10; рекоменд-ся исп-ть определение константы: Static const unsigned nmax-10;

В СИ внешняя переменна, определённая как константа, доступна во всей программе. В СИ++ для этого определения перед такой переменной должно быть слово extern.