Анализ трудоемкости рекурсивных алгоритмов
Анализ трудоемкости рекурсивных реализаций алгоритмов связан с количеством операций, выполняемых при одном вызове функции, и количеством таких вызовов. Графическое представление порождаемой конкретным алгоритмом цепочки рекурсивных вызовов называется деревом рекурсивных вызовов. Более детальное рассмотрение приводит к необходимости учета затрат как на организацию вызова функции и передачи параметров, так и на возврат вычисленных значений и передачу управления в точку вызова.
Можно заметить, что некоторая ветвь дерева рекурсивных вызовов обрывается при достижении такого значения передаваемого параметра, при котором функция может быть вычислена непосредственно, на основе базиса индукции. Таким образом, рекурсия эквивалентна конструкции цикла, в котором каждый проход есть выполнение рекурсивной функции с заданным параметром.
Рассмотрим пример для функции вычисления факториала N!=F(N) при N=5 (рис.34).
| Цепочка рекурсивных возвратов (рекурсивный подъем) |  | Цепочка рекурсивных вызовов (рекурсивный спуск) |
Рис.34. Дерево рекурсии при вычислении факториала числа 5
При обращении к рекурсивной подпрограмме в памяти создаётся новая копия подпрограммы со всеми локальными переменными. Такие копии будут порождаться до выхода на граничное условие. Очевидно, в случае отсутствия граничного условия, неограниченный рост числа таких копий приведёт к аварийному завершению программы за счёт переполнения памяти (стека). Порождение все новых копий рекурсивной подпрограммы до выхода на граничное условие называется рекурсивным спуском. Максимальное количество копий рекурсивной подпрограммы, которое одновременно может находиться в памяти компьютера, называется глубиной рекурсии. Завершение работы рекурсивных подпрограмм, вплоть до самой первой, инициировавшей рекурсивные вызовы, называется рекурсивным подъёмом.
Дерево рекурсивных вызовов может иметь и более сложную структуру, если на каждом вызове порождается несколько обращений. Например, дерево рекурсий для чисел Фибоначчи Ф(N) при N=6 представлено на рис.35:
При вычислении значения Ф(6) будут вызваны процедуры вычисления Ф(5) и Ф(4). В свою очередь, для вычисления последних потребуется вычисление двух пар Ф(4), Ф(3) и Ф(3), Ф(2). Можно заметить, что Ф(3) вычисляется три раза, Ф(2) – пять раз. Если рассмотреть вычисление Ф(n) при больших n, то повторных вычислений будет очень много. Это и есть основной недостаток рекурсии – повторные вычисления одних и тех же значений. Кроме того, с рекурсивными функциями может быть связана одна серьезная ошибка: дерево рекурсивных вызовов может оказаться бесконечным и компьютер «зависнет». Важно, чтобы процесс сведения задачи к более простым операциям когда-нибудь заканчивался, т.е. существовало корректное условие выхода из рекурсии.
Следует понимать, что при каждом вызове любой подпрограммы в особую область памяти, выделенной операционной системой программе и называемой стеком, записывается адрес инструкции, которая будет выполнена после завершения работы рекурсивной функции, а также параметры, передаваемые рекурсивной функции. Освобождение этой памяти происходит только при выходе из функции. Поэтому, если при вызове рекурсивной подпрограммы в стек заносится M байт, а размер стека N байт, то после K вызовов, примерно равном N/M – программа прекратит работу. Не смотря на то что, объемы оперативной памяти в настоящее время достаточно большие, существует вероятность переполнения стека при неправильных условиях завершения рекурсии, что грозит зависанием программы и операционной системы.
Чтобы избавиться от проблемы повторных вычислений, нужно запоминать найденные значения, например в массиве, и таким образом не вычислять их каждый раз заново. Для этого придётся активно использовать память, и осуществлять дополнительные проверки – вычислено или нет нужное число. Тогда дерево рекурсий сведется к более простому виду (рис.36):
Например, для оптимизации рекурсивного алгоритма нахождения чисел Фибоначчи необходимо добавить следующие действия:
· создать глобальный массив FCalculated первоначально состоящий из нулей, в котором будут храниться уже найденные числа;
· после вычисления очередного числа Фибоначчи Ф(n) поместить его значение в FCalculated [n];
· в начале рекурсивной процедуры сделать проверку на то, что FCalculated [n] = 0. Если FCalculated [n] <> 0, то вернутся из рекурсивной функции со значением FCalculated [n] в качестве результата, иначе приступить к рекурсивному вычислению Ф (n).
Такая рекурсия с запоминанием результатов промежуточных шагов иногда называется динамическим программированием сверху.
const int NFib = 300; //Максимальный размер массива с числами Фибоначчи
// описываем глобальный массив для запоминания результатов рекурсии
int FCalculated[NFib];
int FibDinam (int n)
{
if (FCalculated[n] != 0) return(FCalculated[n]);
else
{
if ((n == 1) || (n == 2)) return(1);
else
{
FCalculated[n]= FibDinam(n-1)+FibDinam(n-2);
return(FCalculated[n]);
}
}
}
int main()
{
int i,n;
// очищаем массив результатов рекурсии
for(i=1;i<NFib;i++)
{
FCalculated[i] = 0;
}
FCalculated[1] = 1;
FCalculated[2] = 1;
printf("введите N:\n");
scanf("%d", &n);
printf("FibD[%d] = %d\n", n, FibDinam(n));
}
Отметим, что если оценивать сложность рекурсивного алгоритма с запоминанием результатов, то он все равно уступает по скорости обычному алгоритму с итерациями, который был рассмотрен ранее, так как сложность алгоритма с итерациями – линейна, т.е. при использовании этого алгоритма для вычисления n-го числа Фибоначчи потребуется n шагов. Это можно проверить на практике. Например, если на одном и том же компьютере выполнить при N=85 три алгоритма нахождения чисел Фибоначчи:
а) алгоритм с рекурсией (Fib);
б) алгоритм с рекурсией с запоминанием результатов (FibDinam);
с) алгоритм без рекурсии, с итерацией (FibCircle);
то получим следующие временные результаты вычислений (примерно):
а) несколько минут;
б) около секунды;
с) практически мгновенно, т.е. не более секунды.
Эти результаты демонстрируют особенности использования рекурсивных алгоритмов.
Примечание. При выполнении программ и вычислении времени их выполнения использовался компьютер: Intel® Core™ 2 Duo CPU 3 Ghz, 4ГБ ОЗУ.
Пример 32. Необходимо с помощью рекурсивной функции вычислить сумму элементов одномерного массива, который предварительно заполняется случайным образом с помощью стандартных функций генерации случайных чисел.
int Summa(int n, int A[100])
{
if (n = 0) return(0);
else return(A[n] + Summa(n-1,A));
}
int main()
{
int i,n;
int a[100];
printf("Количество элементов в массиве?\n");
scanf("%i", &n); //N<100
for(i=1;i<n;i++)
{
a[i] = -10 + rand();
printf("%d\n",a[i]);
}
printf("Сумма: %d\n", Summa(n,a));
}
Тема 9. Файлы
Файлом называют способ хранения информации на физическом устройстве. Файл - это понятие, которое применимо ко всему - от файла на диске до терминала.
В языке Си отсутствуют операторы для работы с файлами. Все необходимые действия выполняются с помощью функций, включенных в стандартную библиотеку. Они позволяют работать с различными устройствами, такими, как диски, принтер, коммуникационные каналы и т.д. Эти устройства сильно отличаются друг от друга. Однако файловая система преобразует их в единое абстрактное логическое устройство, называемое потоком.
В Си существует два типа потоков: текстовые (text) и двоичные (binary).
Текстовый поток - это последовательность символов. При передаче символов из потока на экран, часть из них не выводится (например, символ возврата каретки, перевода строки).
Двоичный поток - это последовательность байтов, которые однозначно соответствуют тому, что находится на внешнем устройстве.
Прежде чем читать или записывать информацию в файл, он должен быть открыт и тем самым связан с потоком. Это можно сделать с помощью библиотечной функции fopen(). Она берет внешнее представление файла (например, c:\my_file.txt) и связывает его с внутренним логическим именем, которое используется далее в программе. Логическое имя - это указатель на требуемый файл. Его необходимо определить; делается это, например, так:
file *fp;
Здесь file - имя типа, описанное в стандартном заголовочном файле stdio.h, fp - указатель на файл. Обращение к функции fopen() в программе осуществляется выражением:
fp = fopen(<спецификация файла>, <способ использования файла>);
Спецификация файла (т.е. имя файла и путь к нему) может, например, иметь вид: «c:\\my_file.txt» - для файла my_file.txt на диске C.
Способ использования файла задается символами, представленными в таблю13.
Таблица 13.
Способы использования файлов
| Символ | Описание способа использования |
| r | открыть существующий файл для чтения; |
| w | создать новый файл для записи (если файл с указанным именем существует, то он будет переписан); |
| а | дополнить файл (открыть существующий файл для записи информации, начиная с конца файла, или создать файл, если он не существует); |
| r+ | открыть существующий файл для чтения и записи; |
| w+ | создать новый файл для чтения и записи; |
| a+ | дополнить или создать файл с возможностью чтения и записи; |
| rb | открыть двоичный файл для чтения; |
| wb | создать двоичный файл для записи; |
| аb | дополнить двоичный файл; |
| r+b | открыть двоичный файл для чтения и записи; |
| w+b | создать двоичный файл для чтения и записи; |
| а+b | дополнить двоичный файл с предоставлением возможности чтения и записи; |
| rt | открыть текстовой файл для чтения; |
| wt | создать текстовый файл для записи; |
| at | дополнить текстовый файл; |
| r+t | открыть текстовой файл для чтения и записи; |
| w+t | создать текстовый файл для чтения и записи; |
| a+t | дополнить текстовый файл с предоставлением возможности записи и чтения. |
Если режим t или b не задан (например, r, w или а), то он определяется значением глобальной переменной _fmode. Если fmode=0_BINARY, то файлы открываются в двоичном режиме, а если _fmode=0_TEXT - в текстовом режиме. Константы 0_BINARY и 0_ТЕXТ определены в файле fcntl.h.
Строки вида r+b можно записывать и в другой форме: rb+.
Если в результате обращения к функции fopen() возникает ошибка, то она возвращает константу NULL.
Рекомендуется использовать следующий способ открытия файла:
if ((fp = fopen("c:\\my_file.txt", "rt")) == NULL)
{
puts("Открыть файл не удалось\n");
exit(1);
}
После окончания работы с файлом он должен быть закрыт. Это делается с помощью библиотечной функции fclose(). Она имеет следующий прототип:
int fclose(FILE *fp);
При успешном завершении операции функция fclose() возвращает значение нуль. Любое другое значение свидетельствует об ошибке.
Рассмотрим другие библиотечные функции, используемые для работы с файлами (все они описаны в файле stdio.h):
1. Функция putc() записывает символ в файл и имеет следующий прототип:
int putc(int с, FILE *fp);
Здесь fp - указатель на файл, возвращенный функцией fopen(), с - символ для записи (переменная с имеет тип int, но используется только младший байт). При успешном завершении putc() возвращает записанный символ, в противном случае возвращается константа EOF. Она определена в файле stdio.h и имеет значение -1.
2. Функция getc() читает символ из файла и имеет следующий прототип:
int getc(FILE *fp);
Здесь fp - указатель на файл, возвращенный функцией fopen(). Эта функция возвращает прочитанный символ. Соответствующее значение имеет тип int, но старший байт равен нулю. Если достигнут конец файла, то getc() возвращает значение ЕОF.
3. Функция feof() определяет конец файла при чтении двоичных данных и имеет следующий прототип:
int feof(FILE *fp);
Здесь fp - указатель на файл, возвращенный функцией fopen(). При достижении конца файла возвращается ненулевое значение, в противном случае возвращается 0.
4. Функция fputs() записывает строку символов в файл. Она отличается от функции puts() только тем, что в качестве второго параметра должен быть записан указатель на переменную файлового типа.
fputs("Ехаmple", fp);
При возникновении ошибки возвращается значение EOF.
5. Функция fgets() читает строку символов из файла. Она отличается от функции gets() тем, что в качестве второго параметра должно быть указано максимальное число вводимых символов плюс единица, а в качестве третьего - указатель на переменную файлового типа. Строка считывается целиком, если ее длина не превышает указанного числа символов, в противном случае функция возвращает только заданное число символов.
fgets(string, n, fp);
Функция возвращает указатель на строку string при успешном завершении и константу NULL в случае ошибки либо достижения конца файла.
6. Функция fprintf() выполняет те же действия, что и функция printf(), но работает с файлом. Ее отличием является то, что в качестве первого параметра задается указатель на переменную файлового типа.
fprintf(fp, "%х",а);
7. Функция fscanf() выполняет те же действия, что и функция scanf(), но работает с файлом. Ее отличием является то, что в качестве первого параметра задается указатель на переменную файлового типа.
fscanf(fp, "%х", &a);
При достижении конца файла возвращается значение EOF.
8. Функция fseek() позволяет выполнять чтение и запись с произвольным доступом и имеет следующий прототип:
int fseek(FILE *fp, long count, int access);
Здесь fp - указатель на файл, возвращенный функцией fopen(), count - номер байта относительно заданной начальной позиции, начиная с которого будет выполняться операция, access - способ задания начальной позиции.
Переменная access может принимать следующие значения:
0 - начальная позиция задана в начале файла;
1 - начальная позиция считается текущей;
2 - начальная позиция задана в конце файла.
При успешном завершении возвращается нуль, при ошибке - ненулевое значение.
9. Функция ferror() позволяет проверить правильность выполнения последней операции при работе с файлами. Имеет следующий прототип:
int ferror(FILE *fp);
В случае ошибки возвращается ненулевое значение, в противном случае возвращается нуль.
10. Функция remove() удаляет файл и имеет следующий прототип:
int remove(char *file_name);
Здесь file_name - указатель на строку со спецификацией файла. При успешном завершении возвращается нуль, в противном случае возвращается ненулевое значение.
11. Функция rewind() устанавливает указатель текущей позиции в начало файла и имеет следующий прототип:
void rewind(FILE *fp);
12. Функция fread() предназначена для чтения блоков данных из потока.
unsigned fread(void *ptr, unsigned size, unsigned n, FILE *fp);
Она читает n элементов данных, длиной size байт каждый, из заданного входного потока fp в блок, на который указывает указатель ptr. Общее число прочитанных байтов равно произведению n*size. При успешном завершении функция fread() возвращает число прочитанных элементов данных, при ошибке - 0.
13. Функция fwrite() предназначена для записи в файл блоков данных.
unsigned fwrite(void *ptr, unsigned size, unsigned n, FILE *fp);
Она добавляет n элементов данных, длиной size байт каждый, в заданный выходной файл fp. Данные записываются с позиции, на которую указывает указатель ptr. При успешном завершении операции функция fwrite() возвращает число записанных элементов данных, при ошибке - неверное число элементов данных.
В языке Си имеются пять стандартных файлов. Их логические имена представлены в табл.14.
Таблица 14.
Логические имена стандартных файлов языка Си
| Имя | Область применения |
| stdin | для ввода данных из стандартного входного потока (по умолчанию - c клавиатуры); |
| stdout | для вывода данных в стандартный выходной поток (по умолчанию - на экран дисплея); |
| stder | файл для вывода сообщений об ошибках (всегда связан с экраном дисплея); |
| stdprn | для вывода данных на принтер; |
| stdaus | для ввода и вывода данных в коммуникационный канал. |
В языке Си имеется также система низкоуровневого ввода/вывода (без буферизации и форматирования данных), соответствующая стандарту системы UNIX. Прототипы составляющих ее функций находятся в файле io.h. К этим функциям относятся:
open() - открыть файл;
close() - закрыть файл;
read() - читать данные;
write() - записать данные;
lseek() - поиск определенного байта в файле;
unlink() - уничтожить файл.
Пример 33. Пусть необходимо ввести целые числа с клавиатуры, записать их в текстовый файл и закрыть его. Затем открыть этот файл для чтения, прочитать данные, просуммировать их и закрыть файл. В конце нужно открыть этот же файл и дописать в него строку «Сумма чисел равна» и вывести подсчитанную сумму.
#include <stdio.h>
#include <stdlib.h>
int main()
{
FILE *file;
char* file_name = "file.txt";
char s[128];
int i, n;
int fnumber, fsum=0;
signed sim;
printf ("Сколько чисел будем вводить : ");
scanf ("%d", &n);
file = fopen( file_name, "w" ); // Открываем файл для записи
for(i=1;i<=n;i++)
{
printf ("Введите число %d : ", i);
scanf ("%d", &fnumber); // Читаем с клавиатуры число
fputs ((char *) &fnumber, file); // Записываем число в файл
}
fclose (file); // Закрыли файл
file = fopen( file_name, "r" ); // Открываем файл для чтения
printf("\n ");
puts ("Читаем из файла");
while ((fnumber = fgetc(file))!= EOF) // Пока не конец файла читаем число
//из файла
{
printf ("%x\t",fnumber); // Выводим его на экран
fsum = fsum + fnumber; // Считаем сумму чисел
}
fclose (file); // Закрыли файл
file = fopen( file_name, "a" ); // Открываем файл для дополнения
fputs("Сумма значений равна \n", file); // Выводим в конец файла
fprintf(file, "%s\n", &fsum);
printf("\n ");
fclose (file); // Закрыли файл
puts("Готово");
system("pause");
}
На экране будет отображен следующий диалог:
Сколько чисел будем вводить : 5
Введите число 1 : 5
Введите число 2 : 4
Введите число 3 : 3
Введите число 4 : 2
Введите число 5 : 1
Читаем из файла
5 4 3 2 1
Готово!
При этом файл a.txt будет сожержать следующие строки:
Сумма значений равна
В зависимости от компилятора символы, записанные в файл могут не отображаться в привычной числовой форме.
Тема 10. Приемы программирования. Примеры алгоритмов
Алгоритмы сортировки
Задача сортировки ставится следующим способом. Пусть имеется массив целых или вещественных чисел a1,...,an. Требуется переставить элементы этого массива так, чтобы после перестановки они были упорядочены по неубыванию: а1 ≤ a2 ≤ ... ≤an или невозрастанию: а1 ≥ a2 ≥ ... ≥an. Если числа попарно различны, то говорят об упорядочении по возрастанию или убыванию. В дальнейшем будем рассматривать задачу упорядочения по неубыванию, т.к. остальные задачи решаются аналогично. Существует множество алгоритмов сортировки, каждый из которых имеет свои характеристики по скорости. Рассмотрим самые простые алгоритмы, в порядке увеличения скорости их работы.
Сортировка обменами (пузырьком) 
Этот алгоритм считается самым простым и самым медленным. Шаг сортировки состоит в проходе снизу вверх по массиву. При этом просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то они меняются местами.
После первого прохода по массиву "вверху" (в начале массива) оказывается самый "легкий" (минимальный) элемент – отсюда аналогия с пузырьком, который всплывает (рис.37). Следующий проход делается до второго сверху элемента, таким образом, второй по величине элемент поднимается на правильную позицию и так далее.
Исходный массив
0 15 8 10 19 20 6 16 5 19
| |||
 | |||
1: 0 15 8 10 19 20 6 5 16 19
1: 0 15 8 10 19 20 5 6 16 19
1: 0 15 8 10 19 5 20 6 16 19
1: 0 15 8 10 5 19 20 6 16 19
1: 0 15 8 5 10 19 20 6 16 19
1: 0 15 5 8 10 19 20 6 16 19
1: 0 5 15 8 10 19 20 6 16 19
2: 0 5 15 8 10 19 6 20 16 19
2: 0 5 15 8 10 6 19 20 16 19
2: 0 5 15 8 6 10 19 20 16 19
2: 0 5 15 6 8 10 19 20 16 19
2: 0 5 6 15 8 10 19 20 16 19
3: 0 5 6 15 8 10 19 16 20 19
3: 0 5 6 15 8 10 16 19 20 19
3: 0 5 6 8 15 10 16 19 20 19
4: 0 5 6 8 15 10 16 19 19 20
4: 0 5 6 8 10 15 16 19 19 20
Результат
0 5 6 8 10 15 16 19 19 20
Рис. 37. Сортировка массива методом «пузырька»
Проходы делаются по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию.
//процедура сортировки обменами (пузырьком)
void SortBubble (int count, int* pArr)
{
int trash = 0;
for (int i = 0; i < count; i++) // i - номер прохода
{
for (int j=0; j < count-i-1; j++) // внутренний цикл прохода
{
if (pArr[j] > pArr[j+1]) //если "левый" больше "правого"
{
trash = pArr[j]; //меняем местами элементы
pArr[j] = pArr[j+1];
pArr[j+1] = trash;
}
}
}
}
Сортировка выбором
Сортировка выбором выполняется несколько быстрее, чем сортировка методом пузырька. Алгоритм заключается в следующем: нужно найти элемент массива, имеющий наименьшее значение, переставить его с первым элементом, затем проделать тоже самое, начав со второго элемента и т.д. Таким образом, создается отсортированная последовательность путем присоединения к ней одного элемента за другим в правильном порядке. На i-м шаге выбирается наименьший из элементов a[i] ... a[n] и меняем его местами с a[i]. Последовательность шагов изображена на рис.38.
Исходный массив
16 6 6 20 2 19 13 6 3 3
 | |||||
| |||||
 | |||||
1: 2 6 6 20 16 19 13 6 3 3
 | |||
 | |||
2: 2 3 6 20 16 19 13 6 6 3
 |
3: 2 3 3 20 16 19 13 6 6 6
4: 2 3 3 6 16 19 13 20 6 6
5: 2 3 3 6 6 19 13 20 16 6
6: 2 3 3 6 6 6 13 20 16 19
7: 2 3 3 6 6 6 13 20 16 19
8: 2 3 3 6 6 6 13 16 20 19
9: 2 3 3 6 6 6 13 16 19 20
10: 2 3 3 6 6 6 13 16 19 20
Результат
2 3 3 6 6 6 13 16 19 20
Рис. 38. Результат сортировки выбором
Вне зависимости от номера текущего шага i, последовательность a[0]...a[i] является упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево.
//процедура сортировки выбором
void SortSelect(int count, int* pArr)
{
int i1,temp;
int jmax;
for (int i = count - 1; i > 0; i--) // i - номер текущего шага
{
jmax = 0;
for (int j = 0; j <= i; j++)
{
if (pArr [jmax] < pArr [j]) i1 = j;
}
temp = pArr [i1];
pArr [i1] = pArr [i];
pArr [i] = temp;
}}
Сортировка простыми вставками
Просматривается массив и каждый новый элемент a[i] вставляется на подходящее место в уже упорядоченную совокупность a[1],...,a[i-1]. Это место определяется последовательным сравнением a[i] с упорядоченными элементами a[1],...,a[i-1]. Таким образом в начале массива "вырастает" отсортированная последовательность.
Однако в сортировке пузырьком или выбором можно было четко заявить, что на i-м шаге элементы a[1]...a[i-1]стоят на правильных местах и никуда более не переместятся. Здесь же подобное утверждение будет более слабым: последовательность a[1]...a[i-1] упорядочена. При этом по ходу алгоритма в нее будут вставляться (см. название метода) все новые элементы.
Рассмотрим действия алгоритма на i-м шаге. Как говорилось выше, последовательность к этому моменту разделена на две части: готовую a[1]...a[i-1] и неупорядоченную a[i]...a[n].
На следующем, i-м каждом шаге алгоритма берем a[i] и вставляем на нужное место в готовую часть массива. Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним. В зависимости от результата сравнения элемент либо остается на текущем месте (вставка завершена), либо они меняются местами и процесс повторяется (рис.39).
Таким образом, в процессе вставки мы "просеиваем" элемент X к началу массива, останавливаясь в случае, когда
1. Hайден элемент, меньший X.
2. Достигнуто начало последовательности.
Исходный массив
|
 | |||
 | |||
2: 12 16 10 9 10 9 9 11 10 11
3: 10 12 16 9 10 9 9 11 10 11
4: 9 10 12 16 10 9 9 11 10 11
5: 9 10 10 12 16 9 9 11 10 11
6: 9 9 10 10 12 16 9 11 10 11
7: 9 9 9 10 10 12 16 11 10 11
8: 9 9 9 10 10 11 12 16 10 11
9: 9 9 9 10 10 10 11 12 16 11
10: 9 9 9 10 10 10 11 11 12 16
Результат
9 9 9 10 10 10 11 11 12 16
Рис. 39. Сортировка массива простыми вставками
//процедура сортировки простыми вставками
void SortInsert (int count, int* pArr)
{
int temp, j;
for (int i = 1; i < n; i++) // цикл проходов, i - номер прохода
{
temp = pArr[i];
j = i-1; // поиск места элемента в готовой последовательности
while (j >= 0 && pArr[j] > temp)
{
pArr[j+1] = pArr[j]; // сдвигаем элемент направо, пока не дошли
--j;
}
// место найдено, вставить элемент
pArr[j+1] = temp;
}
}
Сортировка простыми вставками является наиболее быстрой из рассмотренных. На практике очень часто используются оптимизированные (улучшенные) алгоритмы сортировки на основе алгоритма простых вставок, например, алгоритм простых вставок со «сторожевым» элементом или алгоритм Шелла.
Алгоритмы поиска
Поиск является одной из основных задач в программировании. Несмотря на кажущуюся простоту задачи, существует множество алгоритмов для ее решения. В общем виде задача поиска ставится следующим образом: найти элемент и его координаты с указанным значением в массиве. Это тривиальная задача решается алгоритмом линейного поиска, когда последовательно проходится весь массив и текущий элемент массива сравнивается с искомым элементом. В случае совпадения запоминается индекс(ы) найденного элемента.
Однако в задаче поиска может быть множество дополнительных условий. Например, поиск минимального и максимального элемента, поиск подстроки в строке, поиск в массиве, который уже отсортирован, поиск с целью узнать есть или нет нужного элемента без указания индекса и т.д. Рассмотрим некоторые типовые задачи поиска.