Рrogram Sort_Obmen;
var а:array of integer;
n,i,k,x: integer;
begin write("количество элементов массива ");
for i:=1 to n do read([i]);
for k:=n-1 downto 1 do {количество сравниваемых пар}
for i:=1 to k do if a[i]>a then {меняем местами соседние элементы}
for i:=1 to n do write(a[i]," "); {упорядоченный массив}
Наряду с сортировкой методом пузырька, существуют и некоторые другие, более эффективные методы сортировки: быстрая сортировка, метод Шелла, сортировка вставками.. . Однако рассмотренный алгоритм наиболее прост в реализации и логичен.
Приведем, тем не менее, процедуру "быстрой сортировки", которая шаг за шагом ищет максимальный, второй по величине и т.д. элементы и переносит: их в конец массива. Остановка цикла произойдет тогда, когда при очередном проходе не произойдет (т.е., элементы встали на свои места):
Имя фала : FastSort.pas
Procedure FastSort(Var aa:Massive);
Var ii,kk,nn:byte;
For ii:=1 to nn-1 Do Begin
If (aa>aa) Then Begin
Swap (aa,a);
В то время, как при сортировке предыдущем методом для массива из 10 элементов понадобится 9 проходов, для данного алгоритма это число может уменьшиться. К примеру, массив из значений (1,-3,7,-10,11,4,-6,2,5,-4) будет отсортирован за 8 проходов, а массив (1,4,3,2,4,5,6,7,10,11) – всего за 1.
Следуя похожей, логике отсортируем массив по возрастанию:
Имя фала : Sort_Inc.pas
Procedure Sort_Inc(Var aa:Massive);
For kk:=1 to n-1 Do Begin
For ii:=1 to n-kk Do Begin
If (aa>aa) Then Begin
Swap (aa,a);
Обработка двумерных массивов
Основные принципы ввода двумерных массивов во многом схожи с принципами ввода одномерных. При его описании можно ссылать на введенные как константы число строк матрицы MиN, например
Type Matrix=array of Real;
Var a,b,c,d: Matrix;
e: array of Byte;
Как и в случае одномерного массива, обработка его двумерного родственника может быть локальной или глобальной, глобальная – обработкой по индекса, по значениям или комбинированной.
Заметим, что двумерный массив всегда можно развернуть в одномерный, а одномерный – свернуть в двумерный. Рассмотрим примеры решения задач на практическом занятии.
Литература Основная литература
Ахметов К.С. Курс молодого бойца. Изд. 5-е. М., Компьютер-Пресс,1998.
Фигурнов В.Э. IBM PC для пользователя. Изд. 7-е. М., Инфра-М, 1997, и 1999.
Александр Левин Самоучитель Работы на компьютере 8-ое издание Раздел «из чего состоит компьютер." – Питер, 2004 г.
Электронное методическое пособие МГАПИ 2005 г.
Алексеев Е.Р., Чеснокова О.В., Павлыш в.Р., Славинская Л.Ф. Турбо Паскаль 7.0 2-ое издание – NT Press, М., 2006 г.
Коротаев Д.Г. TURBO-PASCAL в примерах и задачах. Учебное пособие МГАПИ, М, 2000 г.
Программирование на языке Паскаль Задачник. Под редакцией О.Ф.Усковой – Питер, 2003 г.
Фаронов В.В. Учебное пособие Turbo - Pascal - Питер, 2007.
Чем больше массив анализируемых данных, тем труднее сконцентрировать внимание на их основных характеристиках. Чтобы лучше воспринять информацию, содержащуюся в наборе данных, их необходимо правильно организовать. Для этого используют либо упорядоченный массив, либо диаграмму «ствол и листья».
Упорядоченный массив
Упорядоченный массив (не обязательно одномерный) состоит из последовательности данных, расположенных по возрастанию. Например, таблица (рис. 1) содержит показатели о пятилетней среднегодовой доходности 158 фондов. Упорядоченные массивы позволяют сразу определить минимальное и максимальное значения, типичные величины, а также диапазон, которому принадлежит основная масса значений.
Рис. 1. Упорядоченный массив, содержащий данные о пятилетней среднегодовой доходности 158 фондов, ориентированных на быстрый рост капитала, за период с 1 января 1997 до 31 декабря 2001
Скачать заметку в формате или , примеры в формате
Видно, что наименьший уровень пятилетней среднегодовой доходности равен –6,1% в год, а наивысший достигает 26,3%. Кроме того, среднегодовые показатели большинства фондов колеблются в диапазоне от 5 до 15%. И всё же представление данных в виде двумерного массива (как на рис. 1) не является оптимальным, так как не позволяет быстро и легко создать сводную таблицу. Поэтому я рекомендую создавать одномерные вертикальные упорядоченные массивы. Excel предоставляет несколько возможностей для этого.
Рассмотрим в качестве сквозного примера среднемесячные температуры июля в Москве за 130 лет наблюдений (рис. 2).
Рис. 2. Среднемесячная температура июля в Москве; исходные данные
Простейший способ упорядочения массива данных предоставляется опцией Excel Сортировать . Выделите столбцы А и В; пройдите по меню Данные → Сортировка (рис. 3). Откроется меню Сортировка . В поле Сортировать по выберите Средняя температура июля, °C , в поле Порядок – По возрастанию . Нажмите Ok.
Рис. 3. Сортировка данных
Вы получите отсортированный (упорядоченный) по температуре список (рис. 4). Сразу видно, что минимальная среднемесячная температура в июле была зафиксирована в Москве в 1904 г. – 14,6°С, а самая высокая – в 2010 г. – 26,1°С. Наверное, вы помните этот ужасный год!? Обратите внимание, что предыдущий рекорд был превышен более, чем на 10%.
Рис. 4. Упорядоченный список
Диаграмма «ствол и листья»
Диаграмма «ствол и листья» представляет собой инструмент для наглядной организации набора данных и анализа их распределения. Данные в диаграмме распределены в соответствии с первыми цифрами, или стволами, и замыкающими цифрами, или листьями. Например, число 18,9 в диаграмме «ствол и листья» состоит из ствола 18 и листа 9 (рис. 5). К сожалению, Excel не умеет автоматически строить диаграмму «ствол и листья». Поэтому воспользуемся ручной процедурой. В качестве ствола используем целую часть температуры, а в качестве листьев – десятичную (см. формулы на листе «Ствол и листья» Excel-файла; сначала я выделил дробную часть, затем перенес дроби из столбцов в строки, и, наконец, отформатировал диаграмму для придания ей большей наглядности).
Рис. 5. Диаграмма «ствол и листья»
Диаграмма «ствол и листья» визуализирует большой массив информации. Например, по ней непосредственно можно определить минимальное (14,6) и максимальное (26,1) значения. Видно, что большинство значений попадают в диапазон 16…20°С, а сами значения образуют со средним около 18°С. Также наблюдается довольно широкий хвост в области бо льших значений.
Контрольные задания
- Данные, приведенные ниже, содержат количество чеков, возвращенных 23 банками своим вкладчикам ввиду отсутствия средств на счете. (Минимальный размер вклада не должен быть ниже 100 долл.): 26 28 20 20 21 22 25 25 18 25 15 20 18 20 25 25 22 30 30 30 15 20 29.
- Постройте диаграмму «ствол и листья», содержащую указанные данные.
- Определите значение, вокруг которого концентрируется распределение количества возвращенных чеков.
- Данные, приведенные ниже, содержат величину ежемесячной платы за услуги (в долларах), взимаемой 26 банками со своих клиентов, если сумма на счету клиента не превышает установленного минимума, равного 1500 долл.: 12 8 5 5 6 6 10 10 9 7 10 7 7 5 0 10 6 9 12 0 5 10 8 5 5 9.
- Создайте упорядоченный массив, содержащий указанные данные.
- Постройте диаграмму «ствол и листья, содержащую указанные данные.
- Какой способ представления данных более информативен? Обоснуйте свой ответ.
- Определите значение, вокруг которого концентрируется распределение ежемесячной оплаты банковских услуг.
Ответы на контрольные задания
1. См. лист «КонтрЗад1» Excel-файла и рис. 6. Диаграмма «ствол и листья» более информативна, чем упорядоченный массив, так как лучше визуализирует данные. Среднее значение составляет приблизительно 22. Хитрость задания заключается в выборе шага для значений ствола. Если в качества шага выбрать число десятков (10, 20, 30), диаграмма «ствол и листья» потеряет в своей наглядности.
Известны результаты соревнования 9 участников по стрельбе. Расположить данные результаты в порядке возрастания набранных при стрельбе очков.
Алгоритм решения данной задачи является наиболее сложным из приведенных выше примеров и требует использования вложенных циклов.
Один из способов сортировки массивов заключается в следующем. Сначала первый элемент массива в цикле сравнивается по очереди со всеми оставшимися элементами. Если очередной элемент массива меньше по величине, чем первый, то эти элементы переставляются местами. Сравнение продолжается далее уже для обновленного первого элемента. В результате окончания данного цикла будет найден и установлен на первое место самый наименьший элемент массива. Далее продолжается аналогичный процесс уже для оставшихся элементов массива, т.е. второй элемент сравнивается со всеми остальными и, при необходимости, переставляется с ними местами. После определения и установки второго элемента массива, данный процесс продолжается для третьего элемента, четвертого элемента и т.д. Алгоритм завершается, когда сравниваются и упорядочиваются предпоследний и последний из оставшихся элементов массива.
Программа реализации изложенного алгоритма может иметь следующий вид:
Program pr4;
Type STREL=arrayof integer;
Var rez:strel;
i,j,s:integer;
For i:=1 to 9 do
writeln(‘Введите результаты ",i,"-го участника");
readln(rez[i]);
for i:=1 to 8 do
for j:=i+1 to 9 do
if rez[i]>rez[j] then
s:=rez[j];
rez[j]:=rez[i];
rez[i]:=s;
writeln(‘Отсортированные по возрастанию результаты:");
for i:=1 to 9 do write (rez[i]:5," ‘);
Здесь STREL - тип массива результатов стрельбы участников, rez[i] - переменная для описания результатов i-го участника (i меняется от 1 до 9). Вспомогательная переменная s используется при перестановке местами элементов массива.
Алгоритм сортировки выбором в Turbo Pascal
Очевидно, что первое место в массиве должен занять минимальный элемент массива, второе - наименьший из всех остальных, третий - наименьший из оставшихся и т.д.
Для этого необходимо выполнить следующую последовательность действий:
1. Определить минимальный элемент массива;
2. Поменять его местами с первым элементом;
3. Определить минимальный элемент среди оставшихся;
4. Поменять его местами со вторым элементом и т.д.;
Эта последовательность действий должна выполняться до тех пор, пока не будет определён последний минимальный элемент.
Данный способ называется сортировка выбором.
Всю операцию по упорядочиванию массива можно разбить на более простые задачи и назвать сортировкой выбора.
Первая - поиск минимального элемента. Предлагаемый фрагмент программы напомнит Вам, как это делается.
min:=m; {допустим, что 1-й элемент - минимален}
t:=1; {и его номер = 1}
FOR i:=1 TO 30 DO
if m[i]>
m[t]:=m[i];
m[i]:=buf;
END;
Описанный метод «сортировки выбором» сортировки массивов можно применять как для сортировки массивов по возрастанию, так и для сортировки массивов по убыванию. Для этого просто необходимо определять не минимальный элемент массива, а максимальный. В тексте программы это выражается заменой в некоторых местах знака "".
41. Множества в Паскале
Множество - это структурированный тип данных, представляющий собой набор взаимосвязанных по какому-либо признаку или группе признаков объектов, которые можно рассматривать как единое целое. Каждый объект в множестве называется элементом множества.
Все элементы множества должны принадлежать одному из порядковых типов, содержащему не более 256 значений. Этот тип называется базовым типом множества. Базовый тип задается диапазоном или перечислением.
Область значений типа множество - набор всевозможных подмножеств, составленных из элементов базового типа. В выражениях на языке Паскаль значения элементов множества указываются в квадратных скобках: , ["а",‘b","с"], ["a".."z"].
Если множество не имеет элементов, оно называется пустым и обозначается как . Количество элементов множества называется его мощностью.
Множество может принимать все значения базового типа. Базовый тип не должен превышать 256 возможных значений. Поэтому базовым типом множества могут быть byte, char, boolean и производные от них типы.
Множество в памяти хранится как массив битов, в котором каждый бит указывает является ли элемент принадлежащим объявленному множеству или нет. Максимальное число элементов множества 256, а данные типа множество могут занимать не более 32 байт.
Число байтов, выделяемых для данных типа множество, вычисляется по формуле:
ByteSize = (max div 8) - (min div 8) + 1,
где max и min - верхняя и нижняя границы базового типа данного множества.
Номер байта для конкретного элемента Е вычисляется по формуле:
ByteNumber = (E div 8) - (min div 8),
номер бита внутри этого байта по формуле:
BitNumber = E mod 8
Не имеет значения порядок записи элементов множества внутри конструктора. Например, и - это эквивалентные множества.
Каждый элемент в множестве учитывается только один раз. Поэтому множество эквивалентно .
Переменные множественного типа описываются так:
Var <идентификатор> : set of <базовый тип>;
Например:
Var A, D: Set Of Byte; B: Set Of "a".."z"; C: Set Of Boolean;
Нельзя вводить значения во множественную переменную процедурой ввода и выводить процедурой вывода.
Множественная переменная может получить конкретное значение только в результате выполнения оператора присваивания:
<множественная переменная> := <множественное выражение>;
Например:
A: = ;B: = ["m", "n", "k"]; C: = ; D: = A;
Кроме того, выражения могут включать в себя операции над множествами.
Операции над множествами
Объединением двух множеств A и B называется множество, состоящее из элементов, входящих хотя бы в одно из множеств A или B. Знак операции объединения в Паскале «+».
1) + => 2) +[‘a’..’z’]+[‘A’..’E’, ‘k’] => [‘A’..’E’, ‘a’..’z’]3) + =>
Пересечением двух множеств A и B называется множество, состоящее из элементов, одновременно входящих во множество A и во множество B.
Знак операции пересечения в Паскале «*»
1) * => 2) [‘a’..’z’]*[‘A’..’E’, ‘k’] => [‘k’]3) * =>
Разностью двух множеств A и B называется множество, состоящее из элементов множества A, не входящих во множество B.
1a) - => 1b) - => 2a) [‘a’..’z’]-[‘A’..’E’, ‘k’] => [‘a’..’j’, ‘i’..’z’]2b) [‘A’..’E’, ‘k’] - [‘a’..’z’] => [‘A’..’E’]3a) - => 3b) - =>
Операция вхождения . Это операция, устанавливающая связь между множеством и скалярной величиной, тип которой совпадает с базовым типом множества. Если x - такая скалярная величина, а M - множество, то операция вхождения записывается так: x in M.
Результат - логическая величина true, если значение x входит в множество M, и false - в противном случае.
Например, 4 in –– true, 5 in –– false.
Используя данную операцию, можно не только работать с элементами множества, но и, даже если в решении задачи явно не используются множества, некоторые логические выражения можно записать более лаконично.
1) Натуральное число n является двухзначным. Вместо выражения (n >= 10) and (n <=99) можно записать n in .
2) Символ c является русской буквой. Вместо выражения (c >= ‘А’) and (c <= ‘Я’) or (c>=‘а’) and (c<=‘п’) or (c>=‘р’) and (c<=‘я’) пишем c in [‘А’.. ‘Я’, ‘а’.. ‘п’, ‘р’.. ‘я’] и т.д.
Добавить новый элемент в множество можно с использованием операции объединения. Например, a:= a+ Для этих же целей в Turbo Pascal 7.0 предназначена процедура Include: include (M, A) M – множество, A – переменная того же типа, что и элементы множества M. Тот же пример можно записать так: Include (a, 5)
Исключить элемент из множества можно с помощью операции «разность множеств». Например, a:= a- Для этих же целей в Turbo Pascal 7.0 предназначена процедура Exclude: exclude (M, A) M – множество, A – переменная того же типа, что и элементы множества M. Тот же пример можно записать так: Exclude (a, 5)
Рассмотрим несколько примеров использования множеств при решении задач.
Задача 1.
В городе имеется n высших учебных заведений, которые производят закупку компьютерной техники. Есть шесть компьютерных фирм: «Диалог», «Avicom», «Нэта», «Сервер», «Декада», «Dega.ru». Ответить на следующие вопросы:
1) в каких фирмах закупка производилась каждым из вузов?
2) в каких фирмах закупка производилась хотя бы одним из вузов?
3) в каких фирмах ни один из вузов не закупал компьютеры?
Решим задачу с использованием множеств. Для удобства дальнейших манипуляций в порядке следования занумеруем компьютерные фирмы, начиная с единицы. Занесём информации о месте закупок компьютеров каждым из вузов в отдельное множество.
Ответ на первый вопрос можно получить, выполнив пересечение всех таких множеств.
Ответ на второй вопрос – результат объединения множеств.
И, наконец, на последний – разность множества всех фирм и множества фирм, где хотя бы один вуз делал покупки.
Program ex_set_1;type firma = set of 1..6; v = array of firma;const f: array of string = ("Диалог", "Avicom", "Нэта", "Сервер", "Декада", "Dega.ru");{процедура ввода информации о закупке компьютеров в очередной фирме}procedure vvod(var a: firma);var i: byte; ans: 0..1;begin a:= ; for i:= 1 to 6 do begin Write("Вуз покупал компьютеры в фирме ", f[i], " (1 - да, 0 - нет)? "); ReadLn(ans); if ans = 1 then a:=a+[i] end;end;{процедура вывода элементов массива, номера которых содержатся в множестве}procedure Print(a: firma);var i: byte;begin for i:= 1 to 6 do if i in a then write(f[i]:10); writelnend;{Процедура, дающая ответ на первый вопрос}procedure Rez1(a: v; n: byte; var b: firma);var i: byte;begin b:= ; for i:= 0 to n-1 do b:= b * a[i];end;{Процедура, дающая ответ на второй вопрос}procedure Rez2(a: v; n: byte; var b: firma);var i: byte;begin b:= ; for i:= 0 to n-1 do b:= b + a[i];end;var a: v; n, i: byte; c: firma;begin write("Сколько вузов делали закупку? "); readln(n); for i:= 0 to n-1 do vvod(a[i]); Rez1(a, n, c); writeln("Каждый из вузов закупил компьютеры в фирмах: "); Print(c); Rez2(a, n, c); writeln("Хотя бы один из вузов закупил компьютеры в фирмах: "); Print(c); writeln("Ни один из вузов не закупил компьютеры в фирмах: "); Print(-c);end.
Задача 2. Сгенерировать n множеств (нумерацию начать с 1). Вывести элементы, которые входят во все множества с номерами, кратными трём, но не входят в первое множество.
Program ex_set_2;type mn = set of byte; v = array of mn;{процедура ввода информации в очередное множество}procedure vvod(var a: mn);var i, n, vsp: byte;begin a:= ; n:= 1 +random(200); for i:= 1 to n do begin vsp:= random(256); a:=a+ end;end;{процедура вывода элементов множества}procedure Print(a: mn);var i: byte;begin for i:= 0 to 255 do if i in a then write(i:4); writelnend;{Процедура, дающая ответ на вопрос}procedure Rez(a: v; n: byte; var b: mn);var i: byte;begin b:= ; i:= 3; while i <= n do begin b:= b * a[i]; i:= i + 3 end; b:= b - aend;var a: v; n, i: byte; c: mn;begin randomize; write("Сколько множеств? "); readln(n); for i:= 1 to n do begin vvod(a[i]); print (a[i]) end; Rez(a, n, c); Print(c);end.
Program ex_set_3;var m: set of char; s: string; i: byte;begin write("Введите строку: "); readln(s); m:=; i:= 1; while i <= length(s) do if s[i] in m then delete(s, i, 1) else begin m:=m+]; i:= i + 1 end; writeln(s)end.
42. Программа поиска количества определенных символов в тексте.
Здесь представлены наиболее часто используемые функции. Приведем пример программы, определяющей количество символов и слов в произвольной строке символов .
program pr28;
const YES=1; {Константы, опpеделяющие является ли }
NO=0; { текущий символ элементом слова}
str: string;
nw, {Количество слов}
nc, {Количество символов}
inword: integer; {Пеpеменная, пpинимающая значения
констант YES или NO}
i: integer;
writeln("Введите стpоку символов:");
read (str);
nw:=0;nc:=0;inword:=NO;
for i:=1 to length(str) do
nc:=nc+1;
if str[i] in [":",".",",",""","!","?",";"," "]{Если pазделитель,}
then inword:=NO {то текущий символ вне слова}
if inword=NO then
begin inword:=YES;
nw:=nw+1;
writeln ("nc=",nc,"nw=",nw);
43. Символьный тип данных в языке Турбо-Паскаль.
Сортировка массива — это процесс распределения всех элементов в определённом порядке. Очень часто это бывает полезным. Например, в вашем почтовом ящике электронные письма отображаются в зависимости от времени получения; новые письма считаются более релевантными, чем те, которые вы получили полчаса, час, два или день назад; когда вы переходите в свой список контактов, имена обычно находятся в алфавитном порядке, потому что так легче что-то найти. Все эти случаи включают в себя сортировку данных перед их фактическим выводом.
Как работает сортировка?
Сортировка данных может сделать поиск внутри массива более эффективным не только для людей, но и для компьютеров. Например, рассмотрим случай, когда нам нужно узнать, отображается ли определённое имя в списке имён. Чтобы это узнать, нужно проверить каждый элемент массива на соответствие с нашим значением. Поиск в массиве с множеством элементов может оказаться слишком неэффективным (затратным).
Однако, предположим, что наш массив с именами отсортирован в алфавитном порядке. Тогда наш поиск начинается с первой буквы нашего значения и заканчивается буквой, которая идёт следующей по алфавиту. В таком случае, если мы дошли до этой буквы и не нашли имя, то точно знаем, что оно не находится в остальной части массива, так как в алфавитном порядке нашу букву мы уже прошли!
Не секрет, что есть алгоритмы поиска внутри отсортированных массивов и получше. Используя простой алгоритм, мы можем искать определённый элемент в отсортированном массиве, содержащем 1 000 000 элементов, используя всего лишь 20 сравнений! Недостатком, конечно же, является то, что сортировка массива с таким огромным количеством элементов — дело сравнительно затратное, и оно точно не выполняется ради одного поискового запроса.
В некоторых случаях сортировка массива делает поиск ненужным. Например, мы ищем наилучший результат студента за тест. Если массив не отсортирован, то нам придётся просмотреть каждый элемент массива, чтобы найти наивысшую оценку. Если же массив отсортирован, то наивысшая оценка будет находиться либо на первой позиции, либо на последней (в зависимости от метода сортировки массива: в порядке возрастания или в порядке убывания), поэтому нам не нужно искать вообще!
Сортировка обычно выполняется путём повторного сравнения пар элементов массива и замены значений, если они отвечают определённым критериям. Порядок, в котором эти элементы сравниваются, зависит от того, какой алгоритм сортировки используется. Критерии состоят из того, как будет сортироваться массив (например, в порядке возрастания или в порядке убывания).
Чтобы поменять два элемента местами, мы можем использовать функцию std::swap() из стандартной библиотеки C++, которая определена в algorithm. В C++11 std::swap() был перенесён в заголовочный файл utility:
#include
#include #include int main () int a = 3 ; int b = 5 ; std :: cout << "Before swap: a = " << a << ", b = " << b << "\n" ; std :: swap (a , b ) ; // меняем местами значения переменных a и b std :: cout << "After swap: a = " << a << ", b = " << b << "\n" ; |
Результат выполнения программы выше:
Before swap: a = 3, b = 5
After swap: a = 5, b = 3
После выполнения операции замены значения переменных a и b поменялись местами.
Сортировка массивов методом выбора
Существует множество способов сортировки массивов. Сортировка массивов методом выбора, пожалуй, самая простая для понимания, хоть и одна из самых медленных.
Для сортировки массива методом выбора от наименьшего до наибольшего элемента выполняются следующие шаги:
Начиная с элемента под индексом 0, ищем в массиве наименьшее значение.
Найденное значение меняем местами с нулевым элементом.
Повторяем шаги №1 и №2 уже для следующего индекса в массиве.
Другими словами, мы ищем наименьший элемент в массиве и перемещаем его на первое место. Затем ищем второй наименьший элемент и перемещаем его уже на второе место после первого наименьшего элемента. Этот процесс продолжается до тех пор, пока в массиве не закончатся неотсортированные элементы.
Вот пример работы этого алгоритма в массиве с 5-ью элементами:
{ 30, 50, 20, 10, 40 }
Сначала ищем наименьший элемент, начиная с индекса 0:
{ 30, 50, 20, 10 , 40 }
Затем меняем местами наименьший элемент с элементом под индексом 0:
{ 10 , 50, 20, 30 , 40 }
Теперь, когда первый элемент массива отсортирован, мы его игнорируем. Ищем следующий наименьший элемент, но уже начиная с индекса 1:
{ 10 , 50, 20 , 30, 40 }
И меняем его местами с элементом под индексом 1:
{ 10 , 20 , 50 , 30, 40 }
Теперь мы можем игнорировать первые два элемента. Ищем следующий наименьший элемент, начиная с индекса 2:
{ 10 , 20 , 50, 30 , 40 }
И меняем его местами с элементом под индексом 2:
{ 10 , 20 , 30 , 50 , 40 }
Ищем следующий наименьший элемент, начиная с индекса 3:
{ 10 , 20 , 30 , 50, 40 }
И меняем его местами с элементом под индексом 3:
{ 10 , 20 , 30 , 40 , 50 }
Ищем следующий наименьший элемент, начиная с индекса 4:
{ 10 , 20 , 30 , 40 , 50 }
И меняем его местами с элементом под индексом 4 (выполняется самозамена, т.е. ничего не делаем):
{ 10 , 20 , 30 , 40 50 }
{ 10, 20, 30, 40, 50 }
Обратите внимание, последнее сравнение всегда будет одиночным (т.е. самозамена), что является лишней операцией, поэтому, фактически, мы можем остановить выполнение сортировки перед последним элементом массива.
Сортировка массивов методом выбора в C++
Вот как этот алгоритм реализован в C++:
#include
#include #include int main () const int length = 5 ; // Перебираем каждый элемент массива // (кроме последнего, он уже будет отсортирован к тому времени, когда мы до него доберёмся) < length - 1 ; ++ startIndex ) // В переменной smallestIndex хранится индекс наименьшего значения, которое мы нашли в этой итерации // Начинаем с того, что наименьший элемент в этой итерации - это первый элемент (индекс 0) int smallestIndex = startIndex ; // Затем ищем элемент поменьше в остальной части массива < length ; ++ currentIndex ) // Если мы нашли элемент, который меньше нашего наименьшего элемента, if (array [ currentIndex ] < array [ smallestIndex ] ) // то запоминаем его smallestIndex = currentIndex ; // smallestIndex теперь наименьший элемент // Меняем местами наше начальное наименьшее число с тем, которое мы обнаружили std :: swap (array [ startIndex ] , array [ smallestIndex ] ) ; // Теперь, когда весь массив отсортирован - выводим его на экран for (int index = 0 ; index < length ; ++ index ) std :: cout << array [ index ] << " " ; return 0 ; |
Наиболее запутанной частью этого алгоритма является внутри другого цикла (так называемый вложенный цикл). Внешний цикл (startIndex) перебирает элементы один за другим (поочерёдно). В каждой итерации внешнего цикла внутренний цикл (currentIndex) используется для поиска наименьшего элемента среди элементов, которые остались в массиве (начиная со startIndex + 1). smallestIndex отслеживает индекс наименьшего элемента, найденного внутренним циклом. Затем smallestIndex меняется значением со startIndex . И, наконец, внешний цикл (startIndex) передаёт этот элемент, и процесс повторяется.
Подсказка: Если у вас возникли проблемы с пониманием того, как работает программа выше, то попробуйте записать её выполнение на листке бумаги. Запишите начальные (неотсортированные) элементы массива горизонтально в строке в верхней части листа. Нарисуйте стрелки, указывающие, какие элементы являются startIndex , currentIndex и smallestIndex на данный момент. Прокрутите выполнение программы вручную и перерисуйте стрелки по мере изменения индексов. После каждой итерации внешнего цикла нарисуйте новую строку, показывающую текущее состояние массива (расположение его элементов).
Сортировка текста выполняется с помощью того же алгоритма. Просто измените тип массива из -а в и инициализируйте его с помощью соответствующих значений.
std::sort()
Поскольку операция сортировки массивов очень распространена, то стандартная библиотека C++ предоставляет встроенную функцию сортировки — std::sort() . Она находится в заголовочном файле algorithm и вызывается следующим образом:
#include
#include #include int main () const int length = 5 ; int array [ length ] = { 30 , 50 , 20 , 10 , 40 } ; std :: sort (array , array + length ) ; for (int i = 0 ; i < length ; ++ i ) std :: cout << array [ i ] << " " ; return 0 ; |
Тест
Задание №1
Напишите на листке бумаги выполнение сортировки следующего массива методом выбора (так как мы это делали выше):
{30, 60, 20, 50, 40, 10}
Ответ №1
30 60 20 50 40 10
10
60 20 50 40 30
10 20
60
50 40 30
10 20 30
50 40 60
10 20 30 40
50
60
10 20 30 40 50
60 (самозамена)
10 20 30 40 50 60
(самозамена)
Задание №2
Перепишите код программы из подзаголовка «Сортировка массивов методом выбора в C++» так, чтобы сортировка выполнялась в порядке убывания (от наибольшего числа к наименьшему). Хотя это может показаться сложным на первый взгляд, но, на самом деле, это очень просто.
Ответ №2
Просто измените:
If (array < array)
if (array [ currentIndex ] < array [ smallestIndex ] ) |
If (array > array)
if (array [ currentIndex ] > array [ smallestIndex ] ) |
Также smallestIndex следует переименовать в largestIndex:
#include
#include #include int main () const int length = 5 ; int array [ length ] = { 30 , 50 , 20 , 10 , 40 } ; // Перебираем каждый элемент массива, кроме последнего for (int startIndex = 0 ; startIndex < length - 1 ; ++ startIndex ) // largestIndex - это индекс наибольшего элемента, который мы обнаружили до сих пор int largestIndex = startIndex ; // Перебираем каждый элемент массива начиная со startIndex + 1 for (int currentIndex = startIndex + 1 ; currentIndex < length ; ++ currentIndex ) // Если текущий элемент больше нашего наибольшего элемента, if (array [ currentIndex ] > array [ largestIndex ] ) // то это новый наибольший элемент в этой итерации largestIndex = currentIndex ; // Меняем местами наше стартовое число с обнаруженным наибольшим элементом std :: swap (array [ startIndex ] , array [ largestIndex ] ) ; // Выводим отсортированный массив на экран for (int index = 0 ; index < length ; ++ index ) std :: cout << array [ index ] << " " ; return 0 ; |
Задание №3
Это задание уже немного сложнее.
Ещё одним простым методом сортировки элементов является «сортировка пузырьком» (или ещё «пузырьковая сортировка» ). Суть заключается в сравнении пары значений, которые находятся рядом, и, если удовлетворены заданные критерии, значения из этой пары меняются местами. И таким образом элементы «скачут пузырьком» до конца массива. Хотя есть несколько способов оптимизировать сортировку пузырьком, в этом задании мы будем придерживаться неоптимизированной версии, так как она проще.
При неоптимизированной версии сортировки пузырьком выполняются следующие шаги для сортировки массива от наименьшего до наибольшего значения :
Сравнивается элемент массива под индексом 0 с элементом массива под индексом 1. Если элемент под индексом 0 больше элемента под индексом 1, то значения меняются местами.
Затем мы перемещаемся к следующей пары значений: элемент под индексом 1 и элемент под индексом 2 и так до тех пор, пока не достигнем конца массива.
Повторяем шаг №1 и шаг №2 до тех пор, пока весь массив не будет отсортирован.
Напишите программу, которая отсортирует следующий массив методом пузырька в соответствии с правилами выше:
const int length(9); int array = { 7, 5, 6, 4, 9, 8, 2, 1, 3 };
const int length (9 ) ; |
В конце программы выведите отсортированные элементы массива.
Подсказка: Если мы можем отсортировать только один элемент за одну итерацию, то это означает, что нам нужно будет повторить выполнение цикла столько раз, сколько есть чисел в нашем массиве (его длина), дабы гарантировать выполнение сортировки всего массива.
Ответ №3
#include
#include #include int main () const int length (9 ) ; int array [ length ] = { 7 , 5 , 6 , 4 , 9 , 8 , 2 , 1 , 3 } ; for (int iteration = 0 ; iteration < length - 1 ; ++ iteration ) // Перебираем каждый элемент массива до последнего элемента (не включительно) // Последний элемент не имеет пары для сравнения for (int currentIndex = 0 ; currentIndex < length - 1 ; ++ currentIndex ) { // Если текущий элемент больше элемента после него, то меняем их местами if (array [ currentIndex ] > array [ currentIndex + 1 ] ) std :: swap (array [ currentIndex ] , array [ currentIndex + 1 ] ) ; } } // Выводим отсортированный массив на экран for (int index = 0 ; index < length ; ++ index ) std :: cout << array [ index ] << " " ; return 0 ; } |
Задание №4
Реализуйте следующие два решения оптимизации алгоритма сортировки пузырьком, который вы написали в предыдущем задании:
Обратите внимание, с каждым выполнением сортировки пузырьком наибольшее значения в массиве «пузырится» до конца. После первой итерации последний элемент массива уже отсортирован. После второй итерации отсортирован предпоследний элемент массива и т.д. С каждой новой итерацией нам не нужно перепроверять элементы, которые уже были отсортированы. Измените свой цикл так, чтобы не перепроверять элементы, которые уже были отсортированы.
Часто при решении определенных задач требуется сделать сортировку данных, которые хранятся в массиве. Что такое сортировка массивов? Вот, например, играя в преферанс, люди раскладывают свои карты по значению и масти. Это дает возможность определить, каких еще карт им не хватает. А в словарях все упорядочивается по алфавиту. Примеров можно привести много. Сортировка - перегруппировка определенного множества объектов в каком-либо порядке по заданному признаку. Сортировка массивов требуется довольно часто. Для этого применяются разные методы. Чтобы понять их суть, достаточно рассмотреть подробно несколько способов.
На основе чего делают
Важно понимать, что массив состоит из многочисленных пар ключей и определенных значений. Сортировка массивов на языке Си делается при помощи десятков строк кода, а на языке PHP это достигается лишь одной несложной командой. Сортировка массивов возможна на основе ключей или значений. Еще можно распределять значения, оставив им существующие ключи или присвоив новые.
Главные различия функций
Сортировка возможна при помощи разных функций. Давайте рассмотрим, чем они отличаются:
Одни функции сортируют массивы по ключам их элементов, а другие - по значениям.
Бывает разный порядок сортировки: убывающий, возрастающий, натуральный, числовой, алфавитный, определенный пользователями или случайный.
Некоторые функции способны сохранять после сортировки связь, существующую между ключом и значением. Но есть функции, в которых ключи сбросятся в новые значения.
Каждая функция осуществляет модификацию переданного массива. Отсортированную копию они не возвращают.
Порядок сортировки считается неопределенным, когда функция определяет два элемента, как равные. Это нестабильная сортировка.
Некоторые функции сортировки массивов в PHP
Функции sort() и rsort() . Sort() упорядочивает в алфавитном порядке массив. Обратим внимание: данная функция чувствительна к регистру. Происходит сортировка по значениям без учета ключей. Rsort() сортирует в обратном порядке тоже по значениям и не учитывает ключи.
Asort() - это одна из функций, сохраняющая отношения ключей и значений. Ее полезно применять для ассоциативных массивов, когда это важно.
В примере ключами выбраны наименования фруктов, а значения - это цены. Сортировка происходит по возрастанию цены. Если необходима сортировка по то нужна функция ksort (), которая делает сортировку по ключам. Arsort () осуществляет сортировку с индексами (описательными) по убыванию значений. Krsort () сортирует по убыванию ключей элементов.
Двумерный массив
Интересна сортировка двумерного массива. Это можно делать по-разному. В PHP есть возможность сравнивать два числа или две строки. Но в любом многомерном массиве каждый из элементов представляет собой массив. В PHP, чтобы сравнить несколько массивов, надо создать определенный метод. Рассмотрим двумерный массив, в котором хранится сокращенное название фруктов, полное название и цена. Элементы массива можно отсортировать в алфавитном порядке по сокращенным названиям.
В примере у нашей функции имя compare (сравнение). У нее 2 аргумента - x, y. Функция должна принять 2 значения, после чего определить порядок. Параметры x, y - 2 массива, которые находятся внутри y основного массива. Чтобы сравнивать description-элементы из массивов, что переданы в функцию, нужны переменные $x, $y. В строке return1 происходит возвращение значения коду, который вызвал функцию. В основе сортировки нашего массива функция usort(). Сортировка идет по правилам, которые описывает функция compare().
Теперь сортировка массивов в PHP станет для вас понятной.