Сортировка массива паскаль

12. Методы сортировки массивов

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

• количество шагов алгоритма, необходимых для упорядочения;
• количество сравнений элементов;
• количество перестановок, выполняемых при сортировке.

Мы рассмотрим только три простейшие схемы сортировки.

Метод «пузырька»

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

В результате наибольший элемент оказывается в самом верху массива.

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

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

Теперь можно привести текст программы упорядочения массива M[1..N] :

Стандартная процедура swap будет использоваться и в остальных алгоритмах сортировки для перестановки элементов (их тип мы уточнять не будем) местами:

procedure swap (var x,y: . );
var t: . ;
begin
t := x;
x := y;
y := t
end;

Заметим, что если массив M — глобальный, то процедура могла бы содержать только аргументы (а не результаты). Кроме того, учитывая специфику ее применения в данном алгоритме, можно свести число парметров к одному (какому?), а не двум.

Применение метода «пузырька» можно проследить здесь.

Сортировка вставками

Второй метод называется метод вставок ., т.к. на j -ом этапе мы «вставляем» j -ый элемент M[j] в нужную позицию среди элементов M[1] , M[2] ,. . ., M[j-1] , которые уже упорядочены. После этой вставки первые j элементов массива M будут упорядочены.
Сказанное можно записать следующим образом:

Чтобы сделать процесс перемещения элемента M[j] , более простым, полезно воспользоваться барьером: ввести «фиктивный» элемент M[0] , чье значение будет заведомо меньше значения любого из «реальных»элементов массива (как это можно сделать?). Мы обозначим это значение через —оо.

Если барьер не использовать, то перед вставкой M[j] , в позицию i-1 надо проверить, не будет ли i=1 . Если нет, тогда сравнить M[j] ( который в этот момент будет находиться в позиции i ) с элементом M[i-1].

Описанный алгоритм имеет следующий вид:

Процедура swap нам уже встречалась.

Сортировка посредством выбора

Идея сортировки с помощью выбора не сложнее двух предыдущих. На j -ом этапе выбирается элемент наименьший среди M[j] , M[j+1] ,. . ., M[N] (см. процедуру FindMin ) и меняется местами с элементом M[j] . В результате после j -го этапа все элементы M[j] , M[j+1] ,. . ., M[N] будут упорядочены.

Сказанное можно описать следующим образом:

нц для j от 1 до N-1
выбрать среди M[j] ,. . ., M[N] наименьший элемент и
поменять его местами с M[j]
кц

В программе, как уже было сказано, используется процедура FindMin , вычисляющая индекс lowindex элемента, наименьшего среди элементов массива с индексами не меньше, чем startindex :

procedure FindMin (start index : integer; var lowindex : integer );
var lowelem: . ;
u: integer;
begin
lowindex := start index ;
lowelem := M[startindex];
for u:= start index +1 to N do
if M[u] lowelem then
begin
lowelem := M[u];
lowindex := u
end
end;

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

Сортировка одномерных массивов по убыванию и возрастанию в Pascal.

В чем заключается вопрос: Как организовать сортировку массивов по убыванию и возрастанию в Паскаль. Метод пузырька.

Сложность : средняя .

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

Естественно есть готовый код, который мы сейчас и разберем:

Массив mass, n кол-во элементов массива, i и j для циклов, buf для того чтобы поменять числа местами. Как я и сказал суть в том чтобы поменять местами соседние элементы пока не от сортируется. Давайте пока забудем про приведенный выше код и напишем следующее:

Мы меняем соседние элементы местами, СОСЕДНИЕ. , цикл до n-1, потому что у последнего элемента массива соседнего элемента нету.

Что же делает этот цикл, он само собой поменяет местами соседние элементы при выполнении условия, что левый больше правого, т.е. например ( 3 , 2 ), 3 больше 2 значит поменяем местами.

После прохода этого цикла ХОТЬ КАК найдется наибольший элемент, т.е. он встанет в самый конец.

Сначала у нас j = 1, j + 1 = 2, т.е. сначала сравняться числа 5 и 2, они поменяются местами, потом j=2, j+1=3,
т.е. j = 2, там у нас уже 5, а в j = 3, у нас 3, условие выполняется значит опять местами.

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

Теперь когда мы запустим цикл еще раз у нас найдется предпоследний элемент, и так пока не от сортируется. Но сколько раз надо выполнить такой цикл спросите вы. Давайте попробуем выполнять его столько раз сколько у нас кол-во элементов массива, вроде логично звучит.

Всё работает правильно, можете проверить но все работает абсолютно ПРАВИЛЬНО. Теперь давайте сравним наш код с образцом:

Есть два отличия:

По поводу 1-го, не заморачивайте голову, можете оставить и просто n, но как видно что нам хватит на один проход меньше чтобы отсортировать массив, вот и всё.

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

Пффффф… надеюсь вы поняли, да и еще это была сортировка по возрастанию чтобы сделать сортировку по убыванию достаточно просто понять знак в условии:

Готовый код задачи на сортировку массива по возрастанию:

лабы по информатике, егэ

лабораторные работы и задачи по программированию и информатике, егэ по информатике

Pascal: Занятие № 5. Одномерные массивы в Паскале

Одномерные массивы в Паскале

Объявление массива

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

var dlina: array [1..3] of integer; begin dlina[1]:=500; dlina[2]:=400; dlina[3]:=150; .

Объявить размер можно через константу:

Инициализация массива

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

const a:array[1..4] of integer = (1, 3, 2, 5);

Заполнение последовательными числами:

Ввод с клавиатуры:

writeln (‘введите кол-во элементов: ‘); readln(n); <если кол-во заранее не известно, - запрашиваем его>for i := 1 to n do begin write(‘a[‘, i, ‘]=’); read(a[i]); . end; .

✍ Пример результата:

Вывод элементов массива

var a: array[1..5] of integer; <массив из пяти элементов>i: integer; begin a[1]:=2; a[2]:=4; a[3]:=8; a[4]:=6; a[5]:=3; writeln(‘Массив A:’); for i := 1 to 5 do write(a[i]:2); <вывод элементов массива>end.

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

Функция Random в Pascal

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

var f: array[1..10] of integer; i:integer; begin randomize; for i:=1 to 10 do begin f[i]:=random(10); < интервал [0,9] >write(f[i],’ ‘); end; end.

Для вещественных чисел в интервале [0,1):

var x: real; . x := random;

Числа Фибоначчи в Паскале

Наиболее распространенным примером работы с массивом является вывод ряда чисел Фибоначчи в Паскаль. Рассмотрим его.

Получили формулу элементов ряда.

var i:integer; f:array[0..19]of integer; begin f[0]:=1; f[1]:=1; for i:=2 to 19 do begin f[i]:=f[i-1]+f[i-2]; writeln(f[i]) end; end.

На данном примере, становится понятен принцип работы с числовыми рядами. Обычно, для вывода числового ряда находится формула определения каждого элемента данного ряда. Так, в случае с числами Фибоначчи, эта формула-правило выглядит как f[i]:=f[i-1]+f[i-2] . Поэтому ее необходимо использовать в цикле for при формировании элементов массива.

Максимальный (минимальный) элемент массива

Псевдокод:

Поиск максимального элемента по его индексу:

Пример:

Поиск в массиве

Рассмотрим сложный пример работы с одномерными массивами:

var f: array[1..10] of integer; flag:boolean; i,c:integer; begin randomize; for i:=1 to 10 do begin f[i]:=random(10); write(f[i],’ ‘); end; flag:=false; writeln(‘введите образец’); readln(c); for i:=1 to 10 do if f[i]=c then begin writeln(‘найден’); flag:=true; break; end; if flag=false then writeln(‘не найден’); end.

Рассмотрим эффективное решение:

Задача: найти в массиве элемент, равный X , или установить, что его нет.

Алгоритм:

• начать с 1-го элемента ( i:=1 );
• если очередной элемент ( A[i] ) равен X , то закончить поиск иначе перейти к следующему элементу.

решение на Паскале Вариант 2. Цикл While:

Поиск элемента в массиве

Предлагаем посмотреть подробный видео разбор поиска элемента в массиве (эффективный алгоритм):

Пример:

Циклический сдвиг

Программа:

Перестановка элементов в массиве

Рассмотрим, как происходит перестановка или реверс массива.

Решение:

Псевдокод:

Программа:

Выбор элементов и сохранение в другой массив

Решение:

Вывод массива B:

writeln(‘Выбранные элементы’); for i:=1 to count-1 do write(B[i], ‘ ‘)

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

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

Выполнение на Паскале:

for i:=1 to N-1 do begin for j:=N-1 downto i do if A[j] > A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с; end; end;

• в массиве ищется минимальный элемент и ставится на первое место (меняется местами с A[1]);
• среди оставшихся элементов также производится поиск минимального, который ставится на второе место (меняется местами с A[2]) и т.д.

Выполнение на Паскале:

for i := 1 to N-1 do begin min:= i ; for j:= i+1 to N do if A[j] i then begin c:=A[i]; A[i]:=A[min]; A[min]:=c; end; end;

Выбирается и запоминается средний элемент массива (присвоим X):