Известны результаты соревнования 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]> buf:=m[t]; {замена}
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. Символьный тип данных в языке Турбо-Паскаль.

Р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 000 000 элементов, используя всего лишь 20 сравнений! Недостатком, конечно же, является то, что сортировка массива с таким огромным количеством элементов — дело сравнительно затратное, и оно точно не выполняется ради одного поискового запроса.

В некоторых случаях сортировка массива делает поиск ненужным. Например, мы ищем наилучший результат студента за тест. Если массив не отсортирован, то нам придётся просмотреть каждый элемент массива, чтобы найти наивысшую оценку. Если же массив отсортирован, то наивысшая оценка будет находиться либо на первой позиции, либо на последней (в зависимости от метода сортировки массива: в порядке возрастания или в порядке убывания), поэтому нам не нужно искать вообще!

Сортировка обычно выполняется путём повторного сравнения пар элементов массива и замены значений, если они отвечают определённым критериям. Порядок, в котором эти элементы сравниваются, зависит от того, какой алгоритм сортировки используется. Критерии состоят из того, как будет сортироваться массив (например, в порядке возрастания или в порядке убывания).

Чтобы поменять два элемента местами, мы можем использовать функцию std::swap() из стандартной библиотеки C++, которая определена в algorithm. В C++11 std::swap() был перенесён в заголовочный файл utility:

#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"; }

#include #include // для std::swap. В C++11 используйте заголовок 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 // для std::swap. В C++11 используйте заголовок int main() { const int length = 5; int array = { 30, 50, 20, 10, 40 }; // Перебираем каждый элемент массива // (кроме последнего, он уже будет отсортирован к тому времени, когда мы до него доберёмся) for (int startIndex = 0; startIndex < length - 1; ++startIndex) { // В переменной smallestIndex хранится индекс наименьшего значения, которое мы нашли в этой итерации // Начинаем с того, что наименьший элемент в этой итерации - это первый элемент (индекс 0) int smallestIndex = startIndex; // Затем ищем элемент поменьше в остальной части массива for (int currentIndex = startIndex + 1; currentIndex < length; ++currentIndex) { // Если мы нашли элемент, который меньше нашего наименьшего элемента, if (array < array) // то запоминаем его smallestIndex = currentIndex; } // smallestIndex теперь наименьший элемент // Меняем местами наше начальное наименьшее число с тем, которое мы обнаружили std::swap(array, array); } // Теперь, когда весь массив отсортирован - выводим его на экран for (int index = 0; index < length; ++index) std::cout << array << " "; return 0; }

#include #include // для std::swap. В C++11 используйте заголовок 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 // для std::sort int main() { const int length = 5; int array = { 30, 50, 20, 10, 40 }; std::sort(array, array+length); for (int i=0; i < length; ++i) std::cout << array[i] << " "; return 0; }

#include #include // для std::sort 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 // для std::swap. В C++11 используйте заголовок int main() { const int length= 5; int array = { 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 > array) // то это новый наибольший элемент в этой итерации largestIndex = currentIndex; } // Меняем местами наше стартовое число с обнаруженным наибольшим элементом std::swap(array, array); } for (int index = 0; index < length; ++index) std::cout << array << " "; return 0; }

#include #include // для std::swap. В C++11 используйте заголовок 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 // для std::swap. В C++11 используйте заголовок int main() { const int length(9); int array = { 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 > array) std::swap(array, array); } } // Выводим отсортированный массив на экран for (int index = 0; index < length; ++index) std::cout << array << " "; return 0; }

#include #include // для std::swap. В C++11 используйте заголовок 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

Реализуйте следующие два решения оптимизации алгоритма сортировки пузырьком, который вы написали в предыдущем задании:

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

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

1.Алгоритм "Сортировка выбором".

Является одним из самых простых алгоритмов сортировки массива. Смысл в том, чтобы идти по массиву и каждый раз искать минимальный элемент массива, обменивая его с начальным элементом неотсортированной части массива. На небольших массивах может оказаться даже эффективнее, чем более сложные алгоритмы сортировки, но в любом случае проигрывает на больших массивах. Число обменов элементов по сравнению с "пузырьковым" алгоритмом N/2, где N - число элементов массива.

Алгоритм:
1. Находим минимальный элемент в массиве.
2. Меняем местами минимальный и первый элемент местами.
3. Опять ищем минимальный элемент в неотсортированной части массива
4. Меняем местами уже второй элемент массива и минимальный найденный, потому как первый элемент массива является отсортированной частью.
5. Ищем минимальные значения и меняем местами элементы,пока массив не будет отсортирован до конца.

//Сортировка выбором {--- Функция СортировкаВыбором(Знач Массив) Мин = 0; Для i = 0 По Массив.ВГраница() Цикл Мин = i; Для j = i + 1 ПО Массив.ВГраница() Цикл //Ищем минимальный элемент в массиве Если Массив[j] < Массив[Мин] Тогда Мин = j; КонецЕсли; КонецЦикла; Если Массив [Мин] = Массив [i] Тогда //Если мин. элемент массива = первому элементу неотс. части массива, то пропускаем. Продолжить; КонецЕсли; Смена = Массив[i]; //Производим замену элементов массива. Массив[i] = Массив[Мин]; Массив[Мин] = Смена; КонецЦикла; Возврат Массив; КонецФункции

2.Алгоритм "Сортировка пузырьком".

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

Алгоритм:
1. Каждый элемент массива сравнивается с последующим и если элемент[i] > элемент происходит замена. Таким образом самые "легкие" элементы "всплывают" - перемещаются к началу списка,а самые тяжелые "тонут" - перемещаются к концу.
2. Повторяем Шаг 1 n-1 раз, где n - Массив.Количество ().

//Сортировка пузырьком {--- Функция СортировкаПузырьком(Знач Массив) Для i = 0 По Массив.ВГраница() Цикл Для j = 0 ПО Массив.Вграница() - i - 1 Цикл Если Массив[j] > Массив Тогда Замена = Массив[j]; Массив[j] = Массив; Массив = Замена; КонецЕсли; КонецЦикла; КонецЦикла; Возврат Массив; КонецФункции //---}

3.Алгоритм "Шейкерная сортировка"(Сортировка перемешиванием,Двунаправленная пузырьковая сортировка).

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

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

В приведенном ниже примере, есть усовершенствование в шейкерной сортировке. В отличие от классической, используется в 2 раза меньше итераций.

//Сортировка перемешивание (Шейкер-Сортировка) {--- Функция СортировкаПеремешиванием(Знач Массив) Для i = 0 ПО Массив.ВГраница()/2 Цикл нИтер = 0; конИтер = Массив.ВГраница(); Пока нИтер Массив[нИтер+1] Тогда Замена = Массив[нИтер]; Массив[нИтер] = Массив[нИтер + 1]; Массив[нИтер + 1] = Замена; КонецЕсли; нИтер = нИтер + 1;//Двигаем позицию на шаг вперед //Проходим с конца Если Массив[конИтер - 1] > Массив[конИтер] Тогда Замена = Массив[конИтер - 1]; Массив[конИтер-1] = Массив[конИтер]; Массив[конИтер] = Замена; КонецЕсли; конИтер = конИтер - 1;//Двигаем позицию на шаг назад КонецЦикла; КонецЦикла; Возврат Массив; КонецФункции //---}

4. Алгоритм "Гномья сортировка".

Алгоритм так странно назван благодаря голландскому ученому Дику Груну.

Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.
Дик Грун

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

//Гномья сортировка {--- Функция ГномьяСортировка(Знач Массив) i = 1; j = 2; Пока i < Массив.Количество() Цикл // Сравнение < - Сортировка по возрастанию, > - по убыванию Если Массив i = j; j = j + 1; Иначе Замена = Массив[i]; Массив[i] = Массив; Массив = Замена; i = i - 1; Если i = 0 Тогда i = j; j = j + 1; КонецЕсли; КонецЕсли; КонецЦикла; Возврат Массив; КонецФункции //---}

5. Алгоритм "Сортировка вставками".

Представляет собой простой алгоритм сортировки. Смысл заключается в том, что на каждом шаге мы берем элемент, ищем для него позицию и вставляем в нужное место.
Элементарный пример: При игре в дурака, вы тянете из колоды карту и вставляете ее в соответствующее место по возрастанию в имеющихся у вас картах. Или
в магазине вам дали сдачу 550 рублей- одна купюра 500, другая 50. Заглядываете в кошелек, а там купюры достоинством 10,100,1000. Вы вставляете купюру
достоинсвом 50р. между купюрами достоинством 10р и 100р, а купюру в 500 рублей между купюрами 100р и 1000р. Получается 10,50,100,500,1000 - Вот вам
и алгоритм "Сортировка вставками".
Таким образом с каждым шагом алгоритма, вам необходимо отсортировать подмассив данных и вставить значение в нужное место.

//Сортировка вставками {--- Функция СортировкаВставками(Знач Массив) Для i = 0 По Массив.ВГраница()-1 Цикл Ключ = i + 1; Замена = Массив[Ключ]; j = i + 1; Пока j > 0 И Замена < Массив Цикл Массив[j] = Массив; Замена = j - 1; Ключ = j - 1; j = j - 1; КонецЦикла; Массив[Ключ] = Замена; КонецЦикла; Возврат Массив; КонецФункции //---}

6. Алгортим "Сортировка слиянием".

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

p/s не смог вставить сюда рисунок с более наглядной схемой, постоянно размазывается. Зато хорошо видна в блоке скриншотов внизу. Можно посмотреть как работает алгоритм.

//Сортировка слиянием {---

Функция СортировкаСлиянием(Знач Массив) Если Массив.Количество() = 1 Тогда Возврат Массив; КонецЕсли; ТочкаРазрыв = Массив.Количество() / 2; лМассив = Новый Массив; прМассив = Новый Массив; Для Сч = 0 ПО Массив.ВГраница() Цикл Если Сч < ТочкаРазрыв Тогда лМассив.Добавить(Массив[Сч]); Иначе прМассив.Добавить(Массив[Сч]); КонецЕсли; КонецЦикла; Возврат Слияние(СортировкаСлиянием(лМассив),СортировкаСлиянием(прМассив)); КонецФункции Функция Слияние(массив1,массив2) a = 0; b = 0; слМассив = Новый Массив; Для Сч = 0 ПО (Массив1.Количество() + Массив2.Количество())-1 Цикл слМассив.Добавить(); КонецЦикла; Для i = 0 ПО (массив1.Количество() + массив2.Количество())-1 Цикл Если b < массив2.Количество() И a < массив1.Количество() Тогда Если (массив1[a] > массив2[b]) И (b < массив2.Количество()) Тогда слМассив[i] = массив2[b]; b = b + 1; Иначе слМассив[i] = массив1[a]; a = a + 1; КонецЕсли; Иначе Если b < массив2.количество() Тогда слМассив[i] = массив2[b]; b = b + 1; Иначе слМассив[i] = массив1[a]; a = a + 1; КонецЕсли; КонецЕсли; КонецЦикла; Возврат слМассив; КонецФункции //---}

7. Алгортим "Сортировка Шелла".

Алгоритм назван так в честь американского ученого Дональда Шелла. По своей сути этот алгоритм является усовершенствованным алгоритмом "Сортировка вставками". Смысл алгоритма заключается в том, чтобы сравнивать не только элементы, стоящие рядом друг с другом, но и на некотором удалении. Сначало выбирается Шаг - некий промежуток, через который будут сравниваться элементы массива на каждой итерации. Обычно его определяют так:
Для первой итерации Шаг = Цел(Массив.Количество()/2), для последующих Шаг = Цел(Шаг/2). Т.е. постепенно шаг сокращается и когда Шаг будет равен 1 произойдет последние сравнение и массив будет отсортирован.

Пример:
Дан массив (10,5,3,1,14,2,7,12).
1. Шаг = 4.
Сортируем простыми вставками каждые 4 группы по 2 элемента (10,14)(5,2)(3,7)(1,12)

10 ,2 ,3 ,1,14 ,5 ,7 ,12

2. Шаг = 2
Сортируем простыми вставками каждые 2 группы по 4 элемента (10,3,14,7)(2,1,5,12)

3 ,1 ,7 ,2 ,10 ,5 ,14 ,12

3. Шаг = 1
Сортируем простыми вставками каждую 1 группу по 8 элементов.

1,2,3,5,7,10,12,14

//Сортировка Шелла {--- Функция СортировкаШелла(Знач Массив) Шаг = Цел(Массив.Количество()/2); Пока Шаг > 0 Цикл i = 0; Пока i < (Массив.Количество() - Шаг) Цикл j = i; Пока j >= 0 И Массив[j] > Массив Цикл Замена = Массив[j]; Массив[j] = Массив; Массив = Замена; j = j - 1; Если ПрименитьОтображениеСортировки Тогда ОтобразитьДиаграммуСортировки(Массив); КонецЕсли; КонецЦикла; i = i + 1; КонецЦикла; Шаг = Цел(Шаг/2); ОбработкаПрерыванияПользователя(); КонецЦикла; Возврат Массив; КонецФункции //---}

8. Алгортим "Быстрая сортировка".

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

//Алгоритм "Быстрая сортировка" { Процедура б_Сортировка(Массив,НижнийПредел,ВерхнийПредел) i = НижнийПредел; j = ВерхнийПредел; m = Массив[Цел((i+j)/2)]; Пока Истина Цикл Пока Массив[i] < m Цикл i = i + 1; КонецЦикла; Пока Массив[j] > m Цикл j = j - 1; КонецЦикла; Если i > j Тогда Прервать; КонецЕсли; КонецЦикла; Если НижнийПредел < j Тогда б_Сортировка(Массив,НижнийПредел,j); КонецЕсли; Если i < ВерхнийПредел Тогда б_Сортировка(Массив,i,ВерхнийПредел); КонецЕсли; КонецПроцедуры Функция БыстраяСортировка(Массив) НижняяГраница = 0; ВерхняяГраница = Массив.ВГраница(); б_Сортировка(Массив,НижняяГраница,ВерхняяГраница); Возврат Массив; КонецФункции //---}

9. Классическая сортировка массива в 1с.

Передаем массив в список значений. Сортируем стандартным методом "Сортировать".

//Сортировка списком значений {--- Функция СортировкаСпискомЗначений(Знач Массив) мСписокЗнч = Новый СписокЗначений; мСписокЗнч.ЗагрузитьЗначения(Массив); мСписокЗнч.СортироватьПоЗначению(НаправлениеСортировки.Возр); Возврат мСписокЗнч.ВыгрузитьЗначения(); КонецФункции //---}

Все сортировки можно ускорить расположив код в циклах в 1 строку. Но для читабельности, оставил так.

Написал обработку в которой реализованы все вышеперечисленные алгоритмы, также поддерживается динамическая анимация процесса сортировки (Кроме стандартной сортировки 1с).

-При запуске обработки автоматически происходит формирование массива случайных чисел от 0 до 100 размерностью 100 элементов.
-Для создания другого массива необходимо нажать на кнопку "Создание ГСЧ массива ", также можно выбирать необходимый диапазон.
-Для включения динамической анимации необходимо поставить галочку на "Отобразить сортировку в диаграмме". Советую на неэффективных алгоритмах устанавливать галочку при размерности массива до 100 элементов, иначе состаритесь ждать сортировки:)

Динамическая отрисовка процесса сортировки очень сильно снижает производительность, зато наглядно видно как работает алгоритм.

Рано или поздно необходимость сортировать данные из массива возникает у любого программиста. Будь то вывод данных из базы в алфавитном порядке или сортировка имен файлов по дате последнего изменения, можно осуществить благодаря встроенным php функциям для сортировки данных массива. В данной статье продемонстрирую и объясню в примерах как работают такие функции как: sort(), rsort().

Функция ; - Сортировка массива по возрастанию и по алфавиту

Структура:

($Массив, $Флаг);

Функция сортирует заданный ей массив $Массив по возрастанию. Функция предназначена для работы со списками. Списки это обычные массивы, ключи которых начинаются с нуля. Функции можно задать необязательный аргумент $Флаг, который манипулирует тем как именно должно происходить сортировка . Рассмотрим описание аргумента $Флаг:

SORT_REGULAR – Сортировка по умолчанию работы функции

SORT_NUMERIC - Сортировка чисел, по возрастанию

SORT_STRING - Сортировка строк, по алфавиту

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

"; } ?> Результат работы скрипта: Курс: 1 - 72 пар Курс: 2 - 83 пар Курс: 3 - 100 пар Если бы мы не применили функцию результат работы был бы следующим: Курс: 1 - 83 пар Курс: 2 - 100 пар Курс: 3 - 72 пар

Сортировка по алфавиту

Ниже приведен скрипт который сортирует страны их массива по алфавиту, второй аргумент функции ($Флаг) не обязательно ставить, т.к. функция сама поймет, что предстоит работать со строками.

"; } ?> Результат работы: Армения Италия Россия Япония

Функция rsort() - Сортировка массива по убыванию

функция является алогичной функции только сортирует массивы по убыванию. рассмотрим структуру синтаксиса:

($Массив, $Флаг);

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

"; } ?> Результат выполнения скрипта: 1 место - приз: 2800 руб. 2 место - приз: 1200 руб. 3 место - приз: 500 руб.

Wi-Fi