Объясните зачем нужен вложенный цикл в описанных методах сортировки

В мире алгоритмов: Сортировка Вставками

От автора
Данная статья рассматривает один из алгоритмов сортировки массивов. Она предназначена для новичков или же для тех кто по каким-то причинам не знаком с данным алгоритмом. Исправления и поправки только приветствуются:)

Теория
Сортировка вставками (Insertion Sort) — это простой алгоритм сортировки. Суть его заключается в том что, на каждом шаге алгоритма мы берем один из элементов массива, находим позицию для вставки и вставляем. Стоит отметить что массив из 1-го элемента считается отсортированным.

Словесное описание алгоритма звучит довольно сложно, но на деле это самая простая в реализации сортировка. Каждый из нас, не зависимо от рода деятельности, применял алгоритм сортировки, просто не осознавал это:) Например когда сортировали купюры в кошельке — берем 100 рублей и смотрим — идут 10, 50 и 500 рублёвые купюры. Вот как раз между 50 и 500 и вставляем нашу сотню:) Или приведу пример из всех книжек — игра в карточного «Дурака». Когда мы тянем карту из колоды, смотрим на наши разложенные по возрастанию карты и в зависимости от достоинства вытянутой карты помещаем карту в соответствующее место. Для большей наглядности приведу анимацию из википедии.

Реализация
Прежде чем приступить к реализации определимся с форматом входных данных — для примера это будет массив целочисленных (int) значений. Нумерация элементов массива начинается с 0 и заканчивается n-1. Сам алгоритм реализуем на языке C++. Итак приступим…
Основной цикл алгоритма начинается не с 0-го элемента а с 1-го, потому что элемент до 1-го элемента будет нашей отсортированной последовательностью (помним что массив состоящий из одного элемента является отсортированным) и уже относительно этого элемента с номером 0 мы будем вставлять все остальные. Собственно код:

for(int i=1;i0 && x[j-1]>x[j];j--) // пока j>0 и элемент j-1 > j, x-массив int swap(x[j-1],x[j]); // меняем местами элементы j и j-1 

Реализация сортировки очень проста, всего 3 строчки. Функция swap меняет местами элементы x[j-1] и x[j]. Вложенный цикл ищет место для вставки. Рекомендую запомнить этот алгоритм, чтобы в случае необходимости написать сортировку не позориться сортировкой пузырьком:)

Анализ производительности
Сортировка вставками имеет сложность n 2 , количество сравнений вычисляется по формуле n*(n-1)/2. Для доказательства был написан следующий код:

void Sort(int* arr,int n)< int counter=0; for(int i=1;i0 && arr[j-1]>arr[j];j--) < counter++; int tmp=arr[j-1]; arr[j-1]=arr[j]; arr[j]=tmp; >> cout

Количество перестановок для 100 элементов:

Итак при n=100 количество перестановок равно 4950, а не 10000 если бы мы высчитывали по формуле n 2 . Имейте это ввиду при выборе алгоритма сортировки.

Эффективность
Сортировка вставками наиболее эффективна когда массив уже частично отсортирован и когда элементов массива не много. Если же элементов меньше 10 то данный алгоритм является лучшим. Не зря в быстрой сортировке (оптимизация Боба Седжвика) используется алгоритм сортировки вставками как вспомогательный, но об этом алгоритме мы поговорим позже…

• алгоритм сортировки
• сортировка вставками
• C++

Зачем два цикла в пузырьковом методе

Пузырьковый метод сортировки – один из самых простых способов упорядочить элементы в массиве или списке. Его принцип работы основан на сравнении пар соседних элементов и перестановке их местами в случае, если они находятся в неправильном порядке. Главная идея пузырьковой сортировки заключается в том, что после каждого прохода самый большой элемент «всплывает» на правильную позицию.

Пузырьковый метод сортировки состоит из двух вложенных циклов. Внешний цикл отвечает за количество проходов по массиву, а внутренний цикл – за сравнение и перестановку элементов. При каждом проходе по массиву внутренний цикл сравнивает пары соседних элементов и меняет их местами, если они находятся в неправильном порядке. После каждого прохода «всплывает» самый большой элемент и он оказывается на своем месте.

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

Основные принципы сортировки

Сортировка – это процесс упорядочивания элементов некоторого множества в определенном порядке. В информатике и программировании сортировка широко используется для упорядочивания данных по определенному критерию.

Одним из наиболее распространенных алгоритмов сортировки является пузырьковая сортировка. Ее основная идея состоит в поочередном сравнении соседних элементов и их обмене при необходимости. Этот процесс повторяется несколько раз, пока все элементы не будут упорядочены.

Пузырьковая сортировка работает по следующим принципам:

1. Создание внешнего цикла, который выполняется для всех элементов массива.
2. Создание внутреннего цикла, который выполняется для сравнения и обмена элементов.
3. Проверка, нужно ли менять местами два соседних элемента. Если да, то они меняются местами.
4. Повторение второго и третьего шагов, пока все элементы не будут упорядочены.

Основные преимущества пузырьковой сортировки заключаются в ее простоте и понятности алгоритма, что делает его отличным выбором для начинающих программистов. Однако пузырьковая сортировка имеет низкую эффективность и эффективность алгоритма существенно снижается при обработке больших объемов данных.

Цель сортировки

Одной из основных задач программирования является сортировка данных. Она позволяет упорядочить элементы массива или другой структуры данных по определенному критерию. Для этого существует множество алгоритмов сортировки, одним из которых является пузырьковый метод.

Целью сортировки является приведение данных в нужный порядок, чтобы упростить последующую обработку или поиск нужного элемента в массиве. Отсортированный массив позволяет легко производить бинарный поиск, сравнивать элементы и выполнять другие операции с данными.

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

Основная идея алгоритма заключается в том, чтобы на каждой итерации просматривать соседние пары элементов и, если они находятся в неправильном порядке, менять их местами.

Внешний цикл позволяет пройти по всем элементам массива, а внутренний цикл выполняет проверку значений и их обмен. После каждой итерации внутреннего цикла, наибольший (или наименьший) элемент «всплывает» на свою позицию. Таким образом, за каждую итерацию внешнего цикла один элемент ставится на свое место.

Применение двух циклов позволяет выполнять сравнение и обмен между соседними элементами до тех пор, пока все элементы массива не будут упорядочены.

Алгоритмы сортировки

Алгоритмы сортировки являются одним из важнейших компонентов в области компьютерных наук. Они используются для упорядочивания элементов в определенном порядке, что может быть полезно при поиске, анализе данных или оптимизации работы программного кода.

Одним из наиболее известных алгоритмов сортировки является пузырьковый метод сортировки. Он получил свое название из-за особенности своей работы: на каждом проходе элементы сравниваются и меняются местами, как будто «всплывают» на свои места, а наименьший элемент «поднимается» к верху списка.

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

Временная сложность пузырькового метода сортировки составляет O(n^2), что означает, что время его выполнения увеличивается квадратично с ростом размера списка. Это делает его неэффективным для работы со списками большого размера.

Помимо пузырькового метода сортировки, существует множество других алгоритмов сортировки, каждый из которых имеет свои особенности и преимущества. Некоторые из них, например, сортировка вставками или быстрая сортировка, имеют лучшую временную сложность и работают более эффективно.

Выбор определенного алгоритма сортировки зависит от требований к времени выполнения, объему данных и особенностей конкретной задачи. Знание различных алгоритмов сортировки позволяет программистам выбирать наиболее подходящий метод для решения конкретной задачи и оптимизировать работу своих программ.

Пузырьковый метод сортировки

Пузырьковый метод сортировки является одним из самых простых и понятных алгоритмов сортировки. Его основной идеей является сравнение и перестановка соседних элементов в массиве до тех пор, пока массив не будет отсортирован.

Алгоритм пузырьковой сортировки состоит из двух вложенных циклов. Внешний цикл выполняется столько раз, сколько элементов находится в массиве. Внутренний цикл проходит по всем элементам массива, сравнивает каждую пару соседних элементов и меняет их местами, если они находятся в неправильном порядке.

Первая итерация внутреннего цикла сравнивает первый и второй элементы, вторая итерация — второй и третий элементы и так далее. После каждой итерации внутреннего цикла самый большой элемент «всплывает» на последнюю позицию в массиве.

Для повышения эффективности работы пузырькового метода сортировки можно использовать флаг, который позволяет остановить сортировку, если внутреннего цикла не происходит ни одной перестановки элементов. Это позволяет исключить необходимость проводить дополнительные итерации и ускоряет процесс сортировки.

Однако пузырьковый метод сортировки имеет свои недостатки. На средних и больших размерах массива он работает очень медленно. Его сложность составляет O(n^2), что означает, что время выполнения алгоритма увеличивается квадратично с увеличением размера массива. Для больших массивов предпочтительнее использовать другие алгоритмы сортировки с более низкой сложностью.

Тем не менее, пузырьковый метод сортировки все же остается полезным для небольших массивов или в качестве учебного примера для понимания основных принципов сортировки.

Принцип работы

Пузырьковый метод сортировки основан на принципе сравнения и перестановки элементов массива. Он получил свое название благодаря тому, что во время выполнения сортировки бóльшие элементы «всплывают» вверх, как пузырьки в воде.

Алгоритм работы пузырьковой сортировки состоит из двух вложенных циклов. Внешний цикл проходит по всем элементам массива и выполняет перестановку элементов на каждой итерации. Внутренний же цикл сравнивает текущий элемент с последующим и, при необходимости, меняет их местами.

На каждой итерации внутреннего цикла самый большой элемент сдвигается к концу массива. Поэтому после первой итерации на последнем месте будет находиться наибольший элемент, после второй итерации — второй по величине, и так далее.

После выполнения всех итераций внешнего цикла массив будет отсортирован в порядке возрастания.

Плюсы и минусы

Пузырьковая сортировка, хоть и является одним из самых простых алгоритмов сортировки, имеет как свои плюсы, так и минусы.

Плюсы:

• Простота реализации. Алгоритм пузырьковой сортировки не требует сложной логики и небольшой кодовой базы, поэтому его легко понять и реализовать.
• Понятность. Пузырьковая сортировка легко объяснить и понять даже новичкам в программировании.
• Универсальность. Алгоритм пузырьковой сортировки может быть применен для сортировки различных типов данных.
• Небольшое потребление памяти. Пузырьковая сортировка работает непосредственно с исходным массивом, минимизируя использование дополнительной памяти.

Минусы:

• Высокая временная сложность. В худшем случае время выполнения пузырьковой сортировки составляет O(n^2), что делает ее неэффективной для больших массивов данных.
• Низкая производительность. Из-за высокой временной сложности пузырьковая сортировка медленно работает с большими объемами данных.
• Относительная неустойчивость. Пузырьковая сортировка менее устойчива к возможным ошибкам и нежелательным условиям, таким как отсутствие элементов для сортировки.

В целом, пузырьковая сортировка применяется там, где требуется простой и надежный алгоритм сортировки для относительно небольших объемов данных, но не рекомендуется использовать ее для сортировки больших массивов или в условиях высоких требований к производительности.

Использование двух циклов

В пузырьковом методе сортировки используются два вложенных цикла: внешний цикл и внутренний цикл. Каждый цикл выполняет свою задачу в процессе сортировки.

Внешний цикл повторяется n — 1 раз, где n — количество элементов в массиве. Этот цикл отвечает за проходы по массиву и сравнение соседних элементов.

Внутренний цикл также повторяется n — 1 раз на каждом проходе внешнего цикла. Он отвечает за сравнение и перестановку элементов, если они находятся в неправильном порядке.

Пузырьковый метод сортировки работает следующим образом:

1. Внешний цикл выполняет проходы по массиву. На каждом проходе внешнего цикла самый большой элемент «всплывает» на последнюю позицию.
2. Внутренний цикл сравнивает соседние элементы и, если они находятся в неправильном порядке, меняет их местами.
3. После выполнения каждого прохода внутреннего цикла, самый большой элемент оказывается на своей правильной позиции в конце массива.
4. После завершения всех проходов внешнего и внутреннего циклов, массив оказывается отсортированным в возрастающем порядке.

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

Хотя пузырьковый метод сортировки является простым и понятным, он не является эффективным для больших массивов из-за своей квадратичной сложности. Однако он может быть полезен для небольших массивов или частично отсортированных массивов.

Вопрос-ответ

Как работает пузырьковый метод сортировки?

Пузырьковый метод сортировки работает путем сравнения пар соседних элементов и перестановки их местами, если они стоят в неправильном порядке. Этот процесс повторяется до тех пор, пока весь список не будет отсортирован.

Зачем используются два цикла в пузырьковом методе сортировки?

Два цикла используются в пузырьковом методе сортировки для обеспечения полной сортировки списка. Внешний цикл проходит по всем элементам списка, а внутренний цикл проходит по парам элементов, сравнивая их и переставляя их местами при необходимости. Это позволяет обеспечить, что самый большой элемент «всплывет» к верхушке списка после каждого прохода внутреннего цикла.

Могут ли использоваться более двух циклов в пузырьковом методе сортировки?

В теории, пузырьковый метод сортировки может быть реализован с использование любого количества циклов. Однако, традиционно применяются два цикла, так как это обеспечивает оптимальное выполнение сортировки. Более сложные алгоритмы с использованием трех и более циклов могут быть более сложны для понимания и исполнения.

В каких случаях пузырьковый метод сортировки может быть неэффективным?

Пузырьковый метод сортировки может быть неэффективным в случаях, когда список имеет большое количество элементов или список уже почти отсортирован. В таких случаях, метод может потребовать значительное количество проходов по всем элементам списка, что занимает много времени.

Объясните зачем нужен вложенный цикл в описанных методах сортировки

39. Организация вложенных циклов. Сортировка элементов массива методом вставки.

Организация вложенных циклов.

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

Сортировка элементов массива методом вставки.

Сортировку вставками можно описать следующим образом. В исходном состоянии считают, что сортируемая последовательность состоит из двух последовательностей: уже сортированной (она на первом шаге состоит из единственного — первого элемента) и последовательности элементов, которые еще необходимо сортировать. На каждом шаге из сортируемой последовательности извлекается элемент и вставляется в первую последовательность так, чтобы она оставалась сортированной. Поиск места вставки осуществляют с конца, сравнивая вставляемый элемент аi с очередным элементом сортированной последовательности аj. Если элемент ai больше аj, его вставляют вместо aj+1, иначе сдвигают аj вправо и уменьшают j на единицу. Поиск места вставки завершают, если элемент вставлен или достигнут левый конец массива. В последнем случае элемент ai вставляют на первое место.

По возрастанию:

program sort_voz_vstav;

uses
SysUtils,
Math;
const nn=20;
var a:array[1..nn] of real;
b:real;
n,i,j:integer;
begin
writeln(‘Vvedite kolichestvo elementov’);
readln(n);
writeln(‘Vvedite elementi massiva’);
for i:=1 to n do
read(a[i]);
readln;
for i:=1 to n-1 do
begin
j:=i+1;
while (j>=2)and (a[j] begin
b:=a[j];
a[j]:=a[j-1];
a[j-1]:=b;
j:=j-1;
end;
end;
for i:=1 to n do
write (a[i]:6:1,’ ‘);
writeln;
readln;
end.

По убыванию:

program sort_yb_vstav;

uses
SysUtils,
Math;
const nn=20;
var a:array[1..nn] of real;
b:real;
n,i,j:integer;
begin
writeln(‘Vvedite kolichestvo elementov’);
readln(n);
writeln(‘Vvedite elementi massiva’);
for i:=1 to n do
read(a[i]);
readln;
for i:=1 to n-1 do
begin
j:=i+1;
while (j>=2)and (a[j]>a[j-1]) do
begin
b:=a[j];
a[j]:=a[j-1];
a[j-1]:=b;
j:=j-1;
end;
end;
for i:=1 to n do
write (a[i]:6:1,’ ‘);
writeln;
readln;
end.

К.Ю. Поляков, Е.А. Еремин — Язык Си и Си++

Только сегодня: скидка до 20% в подарок на первый заказ.
Какую работу нужно написать?

Другую работу

Помощник Анна

08.11.2014
Информатика, 10 класс	К.Ю. Поляков, Е.А. Еремин 41

Задачи и задания 1. Напишите программу, которая находит максимальный и минимальный из чётных положи тельных элементов массива. Если в массиве нет чётных положительных элементов, нужно вывести сообщение об этом. 2. Введите массив с клавиатуры и найдите (за один проход) количество элементов, имеющих максимальное значение. 3. Найдите за один проход по массиву три его различных элемента, которые меньше всех ос тальных («три минимума»). 4. *Заполните массив случайными числами в диапазоне 10..12 и найдите длину самой длин ной последовательности стоящих рядом одинаковых элементов. 5. Заполните массив случайными числами в диапазоне 0..4 и выведите на экран номера всех элементов, равных значению X (оно вводится с клавиатуры). 6. Заполните массив случайными числами и переставьте соседние элементы, поменяв 1 ый элемент со 2 м, 3 й – с 4 м и т.д. 7. Заполните массив из чётного количество элементов случайными числами и выполните ре верс отдельно для 1 ой и 2 ой половин массива. 8. Заполните массив случайными числами и выполните реверс для части массива между эле ментами с индексами K и M (включая эти элементы). 9. Напишите программу для выполнения циклического сдвига массива вправо на 4 элемента. 10. Найдите в массиве все простые числа и скопируйте их в новый массив. 11. *Найдите в массиве все числа Фибоначчи и скопируйте их в новый массив. § 64. Сортировка Введение Сортировка – это расстановка элементов массива в заданном порядке. Порядок сортировки может быть любым; для чисел обычно рассматривают сортировку по возрастанию (или убыванию) значений. Возникает естественный вопрос: «зачем сортировать данные?». На него легко ответить, вспомнив, например, работу со словарями: сортировка слов по алфавиту облегчает поиск нужной информации. Программисты изобрели множество способов сортировки. В целом их можно разделить на две группы: 1) простые, но медленно работающие (на больших массивах) и 2) сложные, но быст рые. Мы изучим два классических метода из первой группы и один метод из второй – знаменитую «быструю сортировку», предложенную Ч. Хоаром. Далее мы будем, как принято в учебниках, рассматривать алгоритмы сортировки эле ментов массива по возрастанию (или убыванию) значений. Для массивов, в которых есть одина ковые элементы, используются понятия «сортировка по неубыванию» и «сортировка по невозрас танию». Метод пузырька ( сортировка обменами ) Название этого метода произошло от известного физического явления – пузырёк воздуха в воде поднимается вверх. Если говорить о сортировке массива, сначала поднимается «наверх» (к началу массива) самый «лёгкий» (минимальный) элемент, затем следующий и т.д. Сначала сравниваем последний элемент с предпоследним. Если они стоят неправильно (меньший элемент «ниже»), то меняем их местами. Далее так же рассматриваем следующую пару элементов и т.д. (см. рисунок).

http://kpolyakov.spb.ru

08.11.2014
Информатика, 10 класс		К.Ю. Поляков, Е.А. Еремин 42
4	4	4	4	1
5	5	5	1	4
2	2	1	5	5
1	1	2	2	2
3	3	3	3	3

Когда мы обработали пару ( A[0] , A[1] ), минимальный элемент стоит на месте A[0] . Это значит, что на следующих этапах его можно не рассматривать. Первый цикл, устанавливающий на свое место первый (минимальный) элемент, можно на псевдокоде записать так: для j от N- 2 до 0 шаг -1 если A[j+ 1 ]< A[j] то поменять местами A[j] и A[j+ 1 ] Здесь j – целочисленная переменная. Обратите внимание, что на очередном шаге сравниваются элементы A[j] и A[j+1] , поэтому цикл начинается с j=N-2 . Если начать с j=N-1 , то на первом же шаге получаем выход за границы массива – обращение к элементу A[N] . За один проход такой цикл ставит на место один элемент. Чтобы «подтянуть» второй эле мент, нужно написать еще один почти такой же цикл, который будет отличаться только конечным значением j в заголовке цикла. Так как верхний элемент уже стоит на месте, его не нужно трогать: сделать для j от N- 2 до 1 шаг -1 если A[j+ 1 ]< A[j] то поменять местами A[j] и A[j+ 1 ] При установке 3 го элемента конечное значение для j будет равно 2 и т.д. Таких циклов нужно сделать N-1 – на 1 меньше, чем количество элементов массива. По чему не N ? Дело в том, что если N-1 элементов поставлены на свои места, то оставшийся автома тически встает на своё место – другого места для него нет. Поэтому полный алгоритм сортировки представляет собой такой вложенный цикл: for ( i = 0 ; i < N- 1 ; i++ ) for ( j = N- 2 ; j >= i; j— ) if ( A[j] > A[j+ 1 ] ) < // поменять местами A[j] и A[j+1] >Записать полную программу вы можете самостоятельно. Методвыбора Еще один популярный простой метод сортировки – метод выбора, при котором на каждом этапе выбирается минимальный элемент (из оставшихся) и ставится на свое место. Алгоритм в общем виде можно записать так: для i от 1 до N- 1 найти номер nMin минимального элемента из A[i]..A[N] если i != nMin то поменять местами A[i] и A[nMin] Здесь перестановка происходит только тогда, когда найденный минимальный элемент стоит не на своём месте, то есть i != nMin . Поскольку поиск минимального элемента выполняется в цикле, этот алгоритм сортировки также представляет собой вложенный цикл: for ( i = 0 ; i < N- 1 ; i++ ) < nMin = i; for ( j = i+ 1 ; j < N; j++ ) if ( A[j] < A[nMin] ) nMin = j; if ( i != nMin ) < // поменять местами A[i] и A[nMin] >>

http://kpolyakov.spb.ru

Ч.Э. Хоар (р. 1934) (en .wikipedia.org )

08.11.2014
Информатика, 10 класс	К.Ю. Поляков, Е.А. Еремин 43

« Быстраясортировка » Методы сортировки, описанные в предыдущем параграфе, работают медленно для больших массивов данных (более 1000 элементов). Поэтому в середине XX века математики и программисты серьезно занимались разработкой более эффективных алгоритмов сортировки. Один из самых популярных «быстрых» алгоритмов, разработанный в 1960 году англий ским учёным Ч. Хоаром, так и называется – «быстрая сортировка» (англ. quicksort ). Будем исходить из того, что сначала лучше делать перестановки элементов массива на большом расстоянии. Предположим, что у нас есть N элементов и известно, что они уже отсортированы в обратном порядке. Тогда за N/2 обменов можно отсортировать их как нужно – сначала поме нять местами первый и последний, а затем последовательно двигаться с двух сторон к центру. Хотя это справедливо только тогда, когда порядок элементов обратный, по добная идея положена в основу алгоритма Quicksort . Пусть дан массив A из N элементов. Выберем сначала наугад любой элемент массива (назо вем его X ). На первом этапе мы расставим элементы так, что слева от некоторой границы (в пер вой группе) находятся все числа, меньшие или равные X , а справа (во второй группе) – большие или равные X . Заметим, что элементы, равные X , могут находиться в обеих частях.

A[i] ≤ X

A[i]≥ X

Теперь элементы расположены так, что ни один элемент из первой группы при сортировке не окажется во второй и наоборот. Поэтому далее достаточно отсортировать отдельно каждую часть массива. Такой подход называют «разделяй и властвуй» (англ. divide and conquer ). Лучше всего выбирать X так, чтобы в обеих частях было равное количество элементов. Такое значение X называется медианой массива. Однако для того, чтобы найти медиану, надо сначала отсортировать массив 11 , то есть заранее решить ту самую задачу, которую мы собираемся решить этим способом. Поэтому обычно в качестве X выбирают средний элемент массива или элемент со случайным номером. Сначала будем просматривать массив слева до тех пор, пока не обнаружим элемент, кото рый больше X (и, следовательно, должен стоять справа от X ). Затем просматриваем массив справа до тех пор, пока не обнаружим элемент меньше X (он должен стоять слева от X ). Теперь поменя ем местами эти два элемента и продолжим просмотр до тех пор, пока два «просмотра» не встре тятся где то в середине массива. В результате массив окажется разбитым на 2 части: левую со зна чениями меньшими или равными X , и правую со значениями большими или равными X . На этом первый этап («разделение») закончен. Затем такая же процедура применяется к обеим частям массива до тех пор, пока в каждой части не останется один элемент (и таким образом, массив бу дет отсортирован). Чтобы понять сущность метода, рассмотрим пример. Пусть задан массив

78

6

82

67

55

44

34

X Выберем в качестве X средний элемент массива, равный 67. Найдем первый слева элемент мас сива, который больше или равен X и должен стоять во второй части. Это число 78. Обозначим ин декс этого элемента через L . Теперь находим самый правый элемент, который меньше X и дол жен стоять в первой части. Это число 34. Обозначим его индекс через R .

78	6	82	67	55	44	34
L	R

Теперь поменяем местами два этих элемента. Сдвигая переменную L вправо, а R – влево, нахо дим следующую пару, которую надо переставить. Это числа 82 и 44. 11 Хотя есть и другие, тоже достаточно непростые алгоритмы.

http://kpolyakov.spb.ru

08.11.2014
Информатика, 10 класс		К.Ю. Поляков, Е.А. Еремин 44
34	6	82	67	55	44	78
L	R
Следующая пара элементов для перестановки – числа 67 и 55.
34	6	44	67	55	82	78

L R После этой перестановки дальнейший поиск приводит к тому, что переменная L становится боль ше R , то есть массив разбит на две части. В результате все элементы массива, расположенные ле вее A[L] , меньше или равны X , а все правее A[R] – больше или равны X .

34

6

44

55

67

82

78

R L Таким образом, сортировка исходного массива свелась к двум сортировкам частей массива, то есть к двум задачам того же типа, но меньшего размера. Теперь нужно применить тот же алго ритм к двум полученным частям массива: первая часть – с 1 ого до R ого элемента, вторая часть – с L ого до последнего элемента. Как вы знаете, такой прием называется рекурсией . Сначала предположим, что в нашей программе один глобальный массив A индексами от 0 до N-1 , который нужно сортировать. Это значит, что массив доступен всем процедурам и функци ям, в том числе и нашей процедуре сортировки. Глобальные данные объявляются выше основной программы: const int N = 7 ; int A[N]; Тогда процедура сортировки принимает только два параметра, ограничивающие её «рабочую зо ну»: nStart – номер первого элемента, и nEnd – номер последнего элемента. Если nStart = nEnd , то в «рабочей зоне» один элемент и сортировка не требуется, то есть нужно выйти из про цедуры. В этом случае рекурсивные вызовы заканчиваются. Приведем полностью процедуру быстрой сортировки: void qSort( int nStart, int nEnd ) < int L, R, c, X; if ( nStart >= nEnd ) return ; // массив отсортирован

L = nStart; R = nEnd;
X = A[(L+R)/ 2 ];		// разделение
while ( L
while (	A[L] < X ) L ++;
while (	A[R] > X ) R —;

if ( L

c = A[L]; A[L] = A[R]; A[R] = c; L ++; R —; > > // рекурсивные вызовы qSort ( nStart, R ); qSort ( L, nEnd );

> Для того, чтобы отсортировать весь массив, нужно вызвать эту процедуру так: qSort( 0 , N- 1 ); К сожалению, эта процедура сортирует только глобальный массив A, чтобы использовать её для сортировки других массивов, добавим в заголовок еще один параметр – целочисленный мас сив: void qSort( int A[] , int nStart, int nEnd ) < . >

http://kpolyakov.spb.ru

08.11.2014
Информатика, 10 класс	К.Ю. Поляков, Е.А. Еремин 45

Размер массива указывать не обязательно, такая процедура будет работать с массивами любого размера. Изменятся также и рекурсивные вызовы (на первом месте в списке аргументов нужно указать имя массива): void qSort( int A[], int nStart, int nEnd ) < . qSort ( A, nStart, R ); // рекурсивные вызовы qSort ( A, L, nEnd ); >а также вызов процедуры из основной программы: qSort ( A, 0 , N- 1 ); Скорость работы быстрой сортировки зависит от того, насколько удачно выбирается вспомо гательный элемент X . Самый лучший случай – когда на каждом этапе массив делится на две рав ные части. Худший случай – когда в одной части оказывается только один элемент, а в другой – все остальные. При этом глубина рекурсии достигает N , что может привести к переполнению стека (нехватке стековой памяти). Для того, чтобы уменьшить вероятность худшего случая, в алгоритм вводят случайность: в качестве X на каждом шаге выбирают не середину рабочей части массива, а элемент со случай ным номером: X = A[irand(L,R)]; Здесь используется написанная нами ранее (см. § 62) функция irand , которая возвращает слу чайное целое число на отрезке [L,R] . В таблице сравнивается время сортировки (в секундах) массивов разного размера, запол ненных случайными значениями, с использованием трёх изученных алгоритмов.

N	метод	метод	быстрая
				пузырька	выбора	сортировка
	1000		0,24 с		0,12 с		0,004 с
5000		5,3 с		2,9 с		0,024 с
15000		45 с		34 с		0,068 с

Как показывают эти данные, преимущество быстрой сортировки становится подавляющим при увеличении N . ? Контрольные вопросы 1. Что такое сортировка? 2. На какой идее основан метод пузырька? метод выбора? 3. Объясните, зачем нужен вложенный цикл в описанных методах сортировки. 4. Сравните метод пузырька и метод выбора. Какой из них требует меньше перестановок? 5. Расскажите про основные идеи метода «быстрой сортировки». 6. Как вы думаете, можно ли использовать метод «быстрой сортировки» для нечисловых дан ных, например, для символьных строк? 7. От чего зависит скорость «быстрой сортировки»? Какой самый лучший и самый худший слу чай? 8. Как вы думаете, может ли метод «быстрой сортировки» работать дольше, чем метод выбо ра (или другой «простой» метод)? Если да, то при каких условиях? 9. Как нужно изменить приведенные алгоритмы, чтобы элементы массива были отсортирова ны по убыванию? Задачи и задания 1. Отсортировать массив и найти количество различных чисел в нём. 2. Напишите программу, в которой сортировка выполняется «методом камня» – самый тяжё лый» элемент опускается в конец массива.

http://kpolyakov.spb.ru

08.11.2014
Информатика, 10 класс	К.Ю. Поляков, Е.А. Еремин 46

3. Напишите программу, которая выполняет неполную сортировку массива: ставит в начало массива три самых меньших по величине элемента в порядке возрастания (неубывания). Положение остальных элементов не важно. 4. Напишите вариант метода пузырька, который заканчивает работу, если на очередном шаге внешнего цикла не было перестановок. 5. Напишите программу, которая сортирует массив по возрастанию последней цифры числа. 6. Напишите программу, которая сортирует массив по убыванию суммы цифр числа. 7. Напишите программу, которая сортирует первую половину массива по возрастанию, а вто рую – по убыванию (элементы из первой половины не должны попадать во вторую и наобо рот). 8. Напишите программу, которая сортирует массив, а затем находит максимальное из чисел, встречающихся в массиве несколько раз. 9. *Напишите программу, которая сравнивает количество перестановок при сортировке одно го и того же массива разными методами. Проведите эксперименты для возрастающей по следовательности (уже отсортированной), убывающей (отсортированной в обратном поряд ке) и случайной. § 65. Двоичный поиск Ранее мы уже рассматривали задачу поиска элемента в массиве и привели алгоритм, кото рый сводится к просмотру всех элементов массива. Такой поиск называют линейным . Для массива из 1000 элементов нужно сделать 1000 сравнений, чтобы убедиться, что заданного элемента в массиве нет. Если число элементов (например, записей в базе данных) очень велико, время поис ка может оказаться недопустимым, потому что пользователь не дождется ответа. Как вы помните, основная задача сортировки – облегчить последующий поиск данных. Вспомним, как мы ищем нужное слово (например, слово «гравицапа») в словаре. Сначала откры ваем словарь примерно в середине и смотрим, какие там слова. Если они начинаются на букву «Л», то слово «гравицапа» явно находится на предыдущих страницах, и вторую часть словаря можно не смотреть. Теперь так же проверяем страницу в середине первой половины, и т.д. Такой поиск называется двоичным . Понятно, что он возможен только тогда, когда данные предвари тельно отсортированы. Для примера на рисунке показан поиск числа X = 44 в отсортированном массиве:

A[0]	с	A[N]
6	34	44	55	67	78	82	R
L	с
6		34	44	55	67	78	82
L	с	R
6		34	44	55	67	78	82
L	R
6	34	44	55	67	78	82

L R Серым фоном выделены ячейки, которые уже не рассматриваются, потому что в них не может быть заданного числа. Переменные L и R ограничивают «рабочую зону» массива: L содержит но мер первого элемента, а R – номер элемента, следующего за последним. Таким образом, нужный элемент (если он есть) находится в части массива, которая начинается с элемента A[L] и заканчи вается элементом A[R-1] . На каждом шаге вычисляется номер среднего элемента «рабочей зоны», он записывается в переменную c . Если X < A[c] , то этот элемент может находиться только левее A[c] , и правая

http://kpolyakov.spb.ru

08.11.2014
Информатика, 10 класс	К.Ю. Поляков, Е.А. Еремин 47

граница R перемещается в c . В противном случае нужный элемент находится правее середины или совпадает с A[c] ; при этом левая граница L перемещается в c . Поиск заканчивается при выполнении условия L = R-1 , когда в рабочей зоне остался один элемент. Если при этом A[L]=X , то в результате найден элемент, равный X , иначе такого элемен та нет. int X, L, R, c; L = 0 ; R = N; while ( L < R-1 ) < c = (L+R) / 2 ; if ( X < A[c] ) R = c; else L = c; >if ( A[L] == X ) printf ( «A[%d]=%d» , L, X ); else printf ( «Не нашли!» ); Двоичный поиск работает значительно быстрее, чем линейный. В нашем примере (для мас сива из 8 элементов) удается решить задачу за 3 шага вместо 8 при линейном поиске. При увели чении размера массива эта разница становится впечатляющей. В таблице сравнивается количест во шагов для двух методов при разных значениях N :

N	линейный поиск	двоичный поиск
			2	2		2
16	16		5
1024	1024		11
1048576	1048576		21

Однако при этом нельзя сказать, что двоичный поиск лучше линейного. Нужно помнить, что данные необходимо предварительно отсортировать, а это может занять значительно больше времени, чем сам поиск. Поэтому такой подход эффективен, если данные меняются (и сортируют ся) редко, а поиск выполняется часто. Такая ситуация характерна, например, для баз данных. ? Контрольные вопросы 1. Почему этот алгоритм поиска называется «двоичным»? 2. Приведите примеры использования двоичного поиска в обычной жизни. 3. Как можно примерно подсчитать количество шагов при двоичном поиске? 4. Сравните достоинства и недостатки линейного и двоичного поиска. Задачи и задания 1. Напишите программу, которая сортирует массив по убыванию и ищет в нем все значения, равные введенному числу. 2. Напишите программу, которая считает среднее число шагов при двоичном поиске для мас сива из 32 элементов в диапазоне 0..100. Для поиска используйте 1000 случайных чисел в этом же диапазоне. § 66. Символьные строки Что такое символьная строка ? Если в середине XX века первые компьютеры использовались, главным образом, для вы полнения сложных математических расчётов, сейчас их основная работа – обработка текстовой (символьной) информации. Символьная строка – это последовательность символов, расположенных в памяти рядом (в соседних ячейках). Для работы с символами во многих языках программирования есть перемен

http://kpolyakov.spb.ru

08.11.2014
Информатика, 10 класс	К.Ю. Поляков, Е.А. Еремин 48

ные специального типа: символы и символьные массивы. Казалось бы, массив символов – это и есть символьная строка, однако здесь есть некоторые особенности. Дело в том, что массив – это группа символов, каждый из которых независим от других. Это значит, что вводить символьный массив нужно посимвольно , в цикле. Более того, размер массива задается при объявлении, и не очень ясно, как использовать массивы для работы со строками пе ременной длины. Таким образом, нужно • работать с целой символьной строкой как с единым объектом; • использовать строки переменной длины. В языках C и C++ работа с символьными строками происходит по разному. Сначала мы рас смотрим язык C (заметим, что все эти возможности работают и в C++). В языке C строка объявляется как массив символов, то есть массив элементов типа char (от англ. character – символ): char s[ 10 ]; Чем же отличается строка от массива? Только тем, что внутри этого массива есть символ с кодом 0, который обозначается как ‘\0’ . Этот невидимый символ (для него нет никакого изображения) обозначает окончание символьной строки. Не нужно путать его с символом ‘0’ (цифрой 0), кото рый имеет код 48. Таким образом, в символьный массив из 10 символов можно записать строку длиной 9 символов: ещё один символ нужно оставить на признак окончания строки. Рассмотрим такой массив:

0

1

2

3

4

5

6

7

8

9

s П р и в е т ! \ 0 ? ?

Символ ‘\0’ в элементе массива s[7] говорит о том, что здесь заканчивается символьная стро ка, состоящая в данном случае из 7 символов. Для вывода строки на экран можно использовать функцию printf с форматом %s (от англ. string – строка): printf ( «%s» , s ); Для массива, показанного выше, будет выведено Привет! Символы с индексами 8 и 9 хранятся в памяти, но не выводятся на экран, потому что при выводе в элементе s[7] встретился символ с кодом 0, означающий конец строки. Для вывода одной стро ки удобно использовать функцию puts : puts ( s ); Она выводит строку на экран с переходом на новую строку, то есть автоматически добавляет сим вол ‘\n’ . Строку можно записать в массив при объявлении: char s[ 10 ] = «Привет!» ; Можно даже не указывать размер массива – в этом случае транслятор вычислит его автоматиче ски: char s[] = «Привет!» ; Размер этого массива будет равен 8 (7 символов строки + символ с кодом 0), записать в него стро ку длиннее 8 символов нельзя (в этом случае будет выход за границы массива , который приведет к изменению ячеек памяти, не принадлежащих этому массиву). Вводить строку с клавиатуры тоже можно по формату %s : scanf ( «%s» , s ); Обратите внимание, что знак & перед именем строки не ставится (в отличие от ввода целых пере менных), потому что имя строки в языке C воспринимается как адрес её первого символа (симво ла с индексом 0). Если вводить таким образом строку, содержащую пробелы, вы увидите, что вводится только первое слово (символы до первого пробела), так работает функция scanf . Часто бывает нужно ввести строку с пробелами целиком, для этого удобно использовать функцию gets : gets ( s );

http://kpolyakov.spb.ru

08.11.2014
Информатика, 10 класс	К.Ю. Поляков, Е.А. Еремин 49

Длина строки (количество символов от начала строки до завершающего символа с кодом 0) определяется с помощью стандартной функции strlen (от англ. string length – длина строки). Вот так в целочисленную переменную n записывается длина строки s : n = strlen ( s ); Чтобы использовать эту функцию (и другие функции для работы с символьными строками), нужно подключить заголовочный файл string.h : #include Для того, чтобы работать с отдельными символами строки, к ним нужно обращаться так же, как к элементам массива: в квадратных скобках записывают индекс символа. Например, так мож но изменить четвёртый символ на ‘a’ (при условии, что длина строки не менее 5 символов) : s[ 4 ] = ‘а’; Приведём полную программу, которая вводит строку с клавиатуры, заменяет в ней все бук вы ‘a’ на буквы ‘б’ и выводит полученную строку на экран. #include #include main() < char s[ 80 ]; int i; printf ( "Введите строку" ); gets ( s ); for ( i = 0 ; i < strlen(s); i++ ) if ( s[i] == 'а' ) s[i] = 'б' ; puts ( s ); >Теперь покажем, как сделать то же самое, используя возможности языка C++. Для работы с символьными строками в C++ введён специальный тип данных, который называется string : main() < string s; . >Начальное значение строки можно задать прямо при объявлении: string s = «Привет!» ; Новое значение строки записывается с помощью оператора присваивания: s = «Привет!» ; Для того, чтобы ввести из входного потока строку с пробелами, применяется функция getline : getline ( cin, s ); а вывод выполняется стандартным образом: cout using namespace std; main() < string s; int i; cout << "Введите строку: " ; getline ( cin, s );

http://kpolyakov.spb.ru

08.11.2014
Информатика, 10 класс	К.Ю. Поляков, Е.А. Еремин 50

for ( i = 0 ; i < s.size(); i++ ) if ( s[i] == 'а' ) s[i] = 'б' ; cout Операции со строками ( язык C) Для выполнения стандартных операций со строками (копирования, сцепления удаления и строк, вставки символов применяют функции стандартной библиотеки языка C, которые подклю чаются с помощью заголовочного файла string.h . Для того, чтобы объединить две строки в одну, используется функция strcat (от англ. string concatenation – сцепление строк). Она дописывает вторую строку в конец первой: char s[ 80 ]= "Привет" , s1[]= "Вася!" ; strcat ( s, ", " ); strcat ( s, s1 ); В результате в массиве s будет построена строка «Привет, Вася!». Первый вызов функции strcat добавит в конец строки s запятую и пробел, а второй – допишет ещё строку «Вася!», которая за писана в массиве s1 . Функция strcpy (от англ. string copy – копировать строку) копирует строку из одного места в другое. Например, после выполнения фрагмента программы: char s[ 80 ], s1[]= "Привет!" ; strcpy ( s1, "Вася" ); strcpy ( s, s1 ); в обоих массивах будет записана строка «Вася»: первый вызов функции strcpy запишет строку «Вася» в массив s1 , а второй вызов – скопирует строку из s1 в s . Обратите внимание, что при вы зове этой функции сначала указывают куда скопировать, а потом – что скопировать. Функция strcpy (как и другие функции для работы со строками) не проверяет, есть ли в массиве место для копирования строки. Если в приведённом примере размер массива s будет меньше, чем 5 символов, произойдет выход за границы массива. Это опасная ошибка, в результа те которой стираются данные за пределами массива. Функции strcpy на самом деле нужно передать два адреса в памяти – адрес строки приёмника и адрес строки источника данных. Как мы уже говорили, указав имя строки, мы сооб щаем функции адрес начала этой строки, но это не обязательно. В следующем примере адрес приёмника (куда будут скопированы данные) – это адрес символа s[7] : char s[ 80 ] = "Прошёл поезд." ; strcpy ( &s[ 7 ] , "пароход." ); В результате в массиве s будет построена строка «Прошёл пароход.». Вместо « &s[7] » можно использовать равносильную запись « s+7 ». Адрес источника данных (второй параметр) также не обязательно совпадает с началом строки. Например: char s[ 80 ] = "Прошёл поезд." , s1[] = "Привет, Вася." ; strcpy ( s+ 7 , s1+ 8 ); В массиве s будет построена строка «Прошёл Вася.». Функцию strcpy можно использовать для удаления символов из строки. Вот так удаляются 4 символа с s[2] по s[5] : char s[] = "0123456789" ; strcpy ( s+ 2 , s+ 6 ); «Хвост» строки, начиная с символа s[6] , переносится ближе к началу, на место символа s[2] . В массиве s остаётся строка «016789». В библиотеке языка C есть еще одна функция для копирования строк, которая называется strncpy (в середине названия есть дополнительная буква n ). Она отличается от strcpy тем, что • копирует не всю строку, а указанное количество символов (третий параметр функции, целое число); • не добавляет в конец строки завершающий символ с кодом 0.