Сортировка расческой (Comb sort)
Сортировка расческой [9] близка к сортировке пузырьком [1]. Она также основана на проверке пар элементов и их перестановке при необходимости.
В сортировке расческой на первом этапе сравниваются пары элементов, отстоящие друг от друга на расстояние K. Как правило, выбирается K = N/1.3, т.е. немногим меньше длины массива. После того, как не останется элементов, отстоящих друг от друга на расстояние K и нарушающих порядок, величина уменьшается в фиксированное количество раз (чаще всего 1.3). Так мы продолжаем, пока K не станет равно 1. Если K=1 и при очередном проходе мы не нашли нарушений порядка – сортировка окончена.
Последний этап сортировки расческой повторяет сортировку пузырьком. Но, благодаря предыдущим этапам, оказывается достаточным очень небольшое количество проходов на последнем этапе.
Сортировка расческой по отношению к сортировке пузырьком играет примерно ту же роль, что и сортировка Шелла по отношению к сортировке вставками.
Плавная сортировка (Smooth sort)
Метод плавной сортировки [10] основан на пирамидальной сортировке. Его единственное отличие заключается в том, что он стремится минимизировать время работы в случае почти отсортированного массива.
В первую очередь метод плавной сортировки пробегает по началу массива и находит (за время O(N)) возрастающую часть массива (см. рис. 2.)
Рис. 2. Плавная сортировка.
Далее, также за время O(N), в оставшейся части массива находится ее минимум.
После этого методом бинарного поиска, за время O(logN), в возрастающей части выделяется та часть, которая должна остаться на своих местах. Это элементы, меньшие либо равные минимуму правой части. Минимум правой части должен встать сразу же за ними, поменявшись местами со следующим элементом.
После этого к оставшейся части массива применяется пирамидальная сортировка [5, гл. 6].
Метод Patience sorting
Метод сортировки Patience sorting [11] работает подобно пасьянсу. Предположим, у нас есть колода случайно перемешанных карт, и нам нужно разложить ее в заданном порядке. При этом карту мы можем класть либо в новую стопку, либо поверх существующей стопки карт, но не в середину.
Мы можем сортировать их следующим образом. Создадим набор дополнительных массивов (стопок карт). Будем перебирать элементы массива (карты) поочередно. Если карту можно положить в какую-либо стопку (порядок будет правильным, данное число больше верхнего элемента дополнительного массива) – положим карту в стопку. Если ни в одну стопку карту положить нельзя – создадим для нее новую стопку.
В результате работы этого алгоритма мы получим несколько стопок карт. Возьмем первую из них и будем по этим же правилам раскладывать по остальным стопкам. Можно доказать, что в итоге возникнет одна стопка, в которую попадут все элементы, и сортировка будет закончена.
Intro sort
Метод сортировки Intro Sort [12] является комбинацией пирамидальной сортировки ([1, разд. 3.3], [5, гл. 6]) и быстрой сортировки QuickSort [5, стр. 198]. QuickSort – наиболее быстрая из O(NlogN) сортировок в среднем случае, но в наихудшем случае этот алгоритм работает за время O(N2). В то же время пирамидальная сортировка в среднем случае несколько медленнее, но гарантированно работает за время O(NlogN). Комбинированный алгоритм должен сочетать преимущества обоих методов.
Известно, что QuickSort – рекурсивный алгоритм. На каждом шаге массив делится на две (возможно, неравные) части, после чего эти части сортируются тем же способом. Ясно, что в худшем случае глубина рекурсии – O(N) вызовов (если от массива на каждом шаге отделяется один элемент), в лучшем (и среднем, как можно доказать) – O(logN) вызовов (если массив на каждом шаге делится пополам).
Идея IntroSort заключается в том, чтобы установить максимальную допустимую глубину рекурсии (например, на уровне T=2logN). Если мы достигли этой глубины – мы делаем вывод, что массив не подходит для использования QuickSort, отказываемся от него и сортируем массив пирамидальной сортировкой.
В результате в наихудшем случае длительность QuickSort ограничивается величиной TN= O(NlogN) и длительность HeapSort также равна O(NlogN). В большинстве случаев оказывается достаточно QuickSort и до HeapSort дело не доходит.
Описание работы с массивами в языке программирования C++
Массивом [1, 2] называется совокупность пронумерованных данных, размещаемых в памяти подряд, одно значение за другим. В массиве можно обеспечить быстрое обращение к элементу по номеру, т.к.
Ai=A+i*S, [1.1]
где Ai - адрес элемента i, A – адрес начала массива, S – размер элемента.
Массив иллюстрируется на рис. 3.
Рис. 3. Размещение массива в памяти.
В языке программирования C++ [2] массив – один из составных типов данных. Массив объявляется в виде
TYPE NAME[ SIZE ];
где TYPE – тип элемента массива (должен быть корректным типом данных), NAME – имя массива, SIZE – размер массива (должен быть константой). Например:
double Arr[ 10 ];
const int TextSize=4096;
char Text[ TextSize ];
Для того, чтобы обратиться к элементу массива, мы пишем NAME[ INDEX ], где NAME – имя массива, INDEX – номер элемента. Например: Arr[0]=Arr[1]+Arr[2];
Описание работы с указателями в языке программирования C++
Указателем [2] называют переменную, хранящую адрес в памяти. В языке программирования C++ тип переменной-указателя определяется типом данных, на которые он указывает. Например:
int* ptr_a; //указатель на переменную типа int
double* pointer; //указатель на переменную типа double
Если мы выполним строчку кода:
printf( “%d” , *ptr_a );,
то четыре (размер типа int) байта, лежащие по адресу ptr_a, будут восприняты как целое число и напечатаны на экране.
Рис. 4. Указатели.
Если мы хотим получить значение переменной, лежащей по данному адресу, мы применяем разыменование – пишем *POINTER_NAME, где POINTER_NAME – имя указателя.
Чтобы получить по переменной указатель на нее, мы пишем &VARIABLE_NAME, где VARIABLE_NAME – имя переменной.
Мы можем воспринимать имя массива как указатель, например:
double a[10];
*a=5.5;
Этот код присвоит значение 5.5 элементу массива с индексом 0.
Аналогично мы можем работать с указателем как с массивом. Если в памяти лежат несколько значений подряд, и у нас есть указатель на одно из них, можно написать
ptr_a[i] = value;
В результате значение value будет присвоено i-ому по порядку значению (нулевым считается то, на которое указывает ptr_val).
Циклы в C++
В случае, если одна и та же операция (например, ввод данных пользователем, их обработка моделируемым устройством и вывод данных) должна быть выполнена в ходе программы многократно, используются циклы.
В C++ существуют три вида цикла:
1. Цикл while (с предусловием).
while ( <условие> )
<операция>
Пока выполнено условие – выполнять операцию.
Пример:
char a[200];
…. //заполнение строки чем-нибудь
int i = 0;
while ( i < 200 && a[i] !=’A’ )
i++;
Этот код бежит по строке либо до конца строки, либо пока не встретит букву ‘A’. Так мы можем узнать, где в строке первая буква ‘A’.
2. Цикл do-while (с постусловием).
do
<операция>
while ( <условие> );
Повторяет операцию, пока выполнено условие. Хотя бы один раз операция точно будет выполнена (условие проверяется после выполнения операции и определяет, идти ли на следующий шаг).
Пример:
char res=0;
do
{
printf( ”Если устали – введите Y\n” );
scanf( “%c” , &res );
}
while ( res != ‘Y’ );
Этот код спрашивает у пользователя, не устал ли он. Если пользователь ввел Y (Yes) – программа выходит из цикла и идет дальше, иначе спрашивает еще раз.
3. Цикл for.
for ( <инициализация> ; <условие> ; <переход> )
<операция>
Вначале выполняется операция инициализации. После этого, если выполнено условие – выполняется операция и переход.
Пример:
for ( i = 0; i < 200 ; i = i + 2 )
A[i] = 0;
Этот код заполняет нулями четные элементы массива A с номером меньше 200.
Операцией может быть любая инструкция языка или составной оператор (несколько инструкций, объединенных в фигурные скобки).
Описание работы с функциями в языке программирования C++
Функция в C++ используется для выделения логически единого фрагмента программы, который может многократно вызываться из разных мест программы.
Функция получает на вход параметры и возвращает значение.
Описание функции имеет вид
<ReturnType> <FunctionName>( <ParType1> <ParName1>,
<ParType2> <ParName2>… )
{
<Operations>
},
где <ReturnType> - тип возвращаемого значения, <FunctionName> - имя функции, <ParType1> - тип первого параметра, <ParName1> - имя первого параметра.
Вызов функции имеет вид
<FunctionName> ( <ParValue1>, <ParValue2>, … )
где <ParValue1> - значение первого параметра.
Пример объявления функции:
int Sum( int a , int b )
{
return a + b; //return означает «вернуть из функции значение»
}
Пример использования функции:
c = Sum(3 , 5 );
d = Sum(3 , c );
После выполнения этого кода с=8, d=11.
Если функция не должна возвращать значение, она может иметь тип возвращаемого значения void.
Если функция должна передать наружу несколько результатов – она может принимать в качестве параметра указатель или ссылку на данные (т.е. адрес данных в памяти), например:
void AddAndMutiply( int first , int second, int& sum , int& mult )
{
mult = first * second;
sum = first + second;
}
…
a=0;
b=0;
AddAndMultiply( 3 , 4 , a , b );
После выполнения этого кода a=7, b=12 (адреса переменных a и b были переданы в функцию и там по этим адресам записали сумму и произведение соответственно).
Описание ввода-вывода «в стиле С» в языке программирования C++
Языки C и C++ не имеют команд ввода-вывода, поскольку эти операции не могут быть реализованы независимо от конкретного компьютера. Существуют функции и классы в составе стандартной библиотеки языка, решающие задачи ввода-вывода.
Сейчас мы рассмотрим функции ввода и вывода «в стиле C».
Для ввода данных используется функция scanf [3]. При вызове ей передается строка формата (она говорит о том, данные какого типа сейчас вводятся) и указатели на переменные, которые должны получить данные.
Например, для ввода одного целого и одного вещественного числа мы пишем:
int a;
double b;
scanf( “%d%f” , &a , &b );
Строка формата “%d%f” означает ввод одного вещественного числа в десятичной форме (d – decimal) и одного вещественного числа (f – floating point, плавающая точка). Первое (целое) число попадает по первому указанному адресу, т.е. в переменную a. Второе (вещественное) число попадает по второму указанному адресу в переменную b.
Рассмотрим случай передачи функции scanf ошибочных параметров. Если мы напишем:
double b;
scanf( “%d” , &b );
то введенное пользователем число будет воспринято как целое и помещено в первые 4 байта переменной b. Сама переменная b при этом получит какое-то очень странное значение.
Если же мы напишем:
int b;
scanf( “%f” , &b );
то введенное пользователем число будет воспринято как вещественное и размещено в 8 байтах, начиная с адреса переменной b. Это приведет либо к затиранию каких-то других переменных (созданных после b), либо к ошибке (например, Stack overrun – подробнее о размещении переменных см. [1]).
Для вывода данных на экран используется функция printf [3]. Ее параметры – строка формата и данные для вывода. Например, если мы хотим вывести дату рождения и возраст человека, мы напишем
char date[ 15 ]; //строка – массив символов
int age;
… //Заполняем эти переменные
printf( “Birthday=%s, Age=%d\n” , date , age );
Будет напечатана строка “Birthday=”, затем строка date, строка “, Age= ” и число age.
Описание механизмов файлового ввода-вывода в текстовом режиме в C++
Механизмы файлового ввода-вывода в текстовом режиме аналогичны механизмам экранного ввода-вывода, рассмотренным выше.
Для того, чтобы вывести данные в файл, необходимо предварительно открыть файл с помощью функции fopen. В качестве параметра функции передается имя файла и режим доступа к файлу (чтение, запись, дозапись в конец). Результатом функции является указатель на открытый файл, который может быть использован для вывода в него данных. Например, код может иметь вид:
FILE* ptr_file = fopen( “in.txt” , “w” );
Мы открываем файл in.txt на запись (“w”) в текстовом режиме (режим текстовый по умолчанию).
После этого для вывода данных в файл можно использовать функцию fprintf. Она аналогична printf, но добавляется первый параметр – указатель на открытый файл, в который мы хотим вывести данные. Пример:
fprintf( ptr_file , “%d” , a );
Этот код выводит в файл целочисленное значение, которое берет из переменной a.
После окончания работы с файлом он закрывается с помощью функции fclose. Например:
fclose( ptr_file );
Ввод данных из файла требует его открытия функцией fopen (с параметром “r” – read) и последующего закрытия функцией fclose. Для ввода данных используется функция fscanf, аналогичная scanf, но получающая в качестве первого параметра указатель на файл, например:
fscanf( ptr_file , “%lf” , &b );
Этот вызов читает из файла вещественное число и записывает его в переменную b.