Сортировка одномерного массива паскаль - IT Новости из мира ПК
Remkomplekty.ru

IT Новости из мира ПК
2 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Сортировка одномерного массива паскаль

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 будут упорядочены.
Сказанное можно записать следующим образом:

нц для j от 2 до N
переместить M[j] на позицию i = M[i-1], либо i=1
кц

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

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

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

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

Идея сортировки с помощью выбора не сложнее двух предыдущих. На 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]

Сортировка одномерных массивов по убыванию и возрастанию в 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]) и т.д.
Читать еще:  Sql коды ошибок

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

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):

  • Инициализируем две переменные (будущие индексы массива): L:=1, R:=N (N — количество элементов).
  • Увеличиваем L и ищем первый элемент A[L], который больше либо равен X (в итоге он должен находиться справа).
  • Уменьшаем R и ищем элемент A[R], который меньше либо равен X (в итоге он должен находиться слева).
  • Смотрим, если L X do R:= R — 1; if L

    5 комментариев

    Bronislav

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

    admin

    Именно поэтому в коде : for j:=N-1 downto i do

    downto i — то есть мы доходим сначала до первого элемента, потом до второго и т.д.

    Bronislav

    Смотрите. Ваш код работает. Но работает не так, как вы пишете перед этим. Он просеивает минимальный элемент с конца через весь массив до первой позиции (первого индекса если хотите). А не так как вы пишете: «При второй итерации цикла нет надобности сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте, он самый большой.» Соответственно вашему коду и вашим рисункам на второй итерации не сравнивается первый элемент (минимальный) со вторым, а не последний (который вообще не факт что максимальный) с предпоследним. Вот об чем речь. Или код меняйте или описание алгоритма перед кодом.

    Владимир

    А как насчёт странного способа поменки оандомням образом, конечно это долго , но все таки есть
    Var
    A: array[1..10] of integer;
    I,e,r,r1: integer;
    Begin
    While i

    7 Pascal сортировка массива
    презентация к уроку по информатике и икт (9 класс) по теме

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

    Скачать:

    Предварительный просмотр:

    Подписи к слайдам:

    Язык программирования Pascal Сортировка массива А. Жидков

    Задача о сортировке массива Сортировкой или упорядочением массива называется расположение его элементов по возрастанию (или убыванию). Если не все элементы различны, то надо говорить о неубывающем (или невозрастающем ) порядке. В теории алгоритмов задача сортировки носит канонический характер. Критерии оценки эффективности этих алгоритмов могут включать следующие параметры: количество шагов алгоритма, необходимых для упорядочения; количество сравнений элементов; количество перестановок, выполняемых при сортировке. известно множество алгоритмов сортировки, наиболее известным является метод «пузырька».

    Сортировка пузырьком Чтобы уяснить его идею, представьте , что массив (таблица) расположен вертикально. Элементы с большим значением всплывают вверх наподобие больших пузырьков. При первом проходе вдоль массива, начиная проход «снизу», берется первый элемент и поочередно сравнивается с последующими. При этом: если встречается более «легкий» (с меньшим значением) элемент, то они меняются местами; при встрече с более «тяжелым» элементом, последний становится » эталоном » для сравнения, и все следующие сравниваются с ним . В результате наибольший элемент оказывается в самом верху массива. program sort_puz; const N=6; var M: array [1..n] of integer; i,j,r,k :integer; procedure swap (var x,y: integer); var t: integer; Begin t:= x; x:= y; y:= t; end; begin write (‘Укажите интервал от 0 до R=’); readln (r); writeln (‘исходный массив’); for j:=1 to N do begin M[j]:=random(r+1); write( ‘M(‘,j,’)=’,M[j],’ ‘); end; writeln; writeln (‘процесс сортировки’); for j:=1 to N-1 do for i:=1 to N-j do if M[i] > M[i+1] then begin swap (M[i],M[i+1]); for k:=1 to N do write(‘M(‘,k,’)=’,M[k],’ ‘); writeln; end; writeln (‘отсортированный массив’); for k:=1 to N do write( ‘M(‘,k,’)=’,M[k],’ ‘); end.

    Сортировка пузырьком тест

    По теме: методические разработки, презентации и конспекты

    Конспект урока по теме «Сортировка массивов».

    Зачетная работа на курсах повышения квалификации.

    Рассматривается данный алгоритм и обсуждается вопрос оценки сложности данного алгоритма.

    Презентация к учебнику «Информатика 10 класс» авторы Поляков К.Ю., Еремин Е.А. Глава 8 «Алгоритмизация и программирование», §64 «Сортировка».Демонстрация презентации дает наглядное представление выпол.

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

    Описаны алгоритмы сортировки, приведены примеры подпрограмм на Паскале.

    Презентация по теме: «Сортировка массивов». В презентации расссмотрены определение сортировки, краткая история развития, несколько способов сорттировки, в частности следующие алгоритмы1.Сортировка пуз.

    Урок информатики по теме «Сортировка одномерного массива»

    Тип урока: комбинированный – изучение нового материала, закрепление, выполнение практической работы.

    Время реализации урока: 2х45 мин

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

    Продукт урока: решение задач на упорядочивание элементов одномерного массива.

    Оборудование: ПК, интерактивная доска, проектор.

    • алгоритм сортировки методом выбора;
    • алгоритм сортировки методом «пузырька»;
    • улучшенный алгоритм «пузырьковой» сортировки;
    • программа на Паскале сортировки методом выбора;
    • программа на Паскале сортировки методом «пузырька».

    Особенности изложения содержания урока:

    Это один из заключительных уроков изучения темы «Программирование» в 9 классе. Учащиеся изучили алгоритмы заполнения одномерного массива, поиска числа в массиве; научились составлять программу на Паскале по данному алгоритму. Знания, умения и навыки, приобретенные на этом уроке, понадобятся в дальнейшем при изучении модуля «Программирование» в 11 классе.

    Урок проводится на основании знаний, полученных по модулю «Программное управление работой компьютера» (Глава 6) и материала для углубленного изучения курса п.6.3 [1].

    1. Организационный момент

    Приветствие и проверка готовности учащихся к уроку.

    2. Мотивация учащихся

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

    Читать еще:  Error c2059 синтаксическая ошибка

    Сегодня на уроке научимся упорядочивать элементы числовых массивов.

    Зачем нужна сортировка? С отсортированными данными работать легче, чем с произвольно расположенными:

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

    Сортировка является мощным средством ускорения работы практически любого алгоритма, в котором нужно часто обращаться к определенным элементам данных. Если хотите стать хорошими программистами, то обязательно должны знать различные методы сортировки[3].

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

    3. Изучение алгоритмов сортировки

    3.1. Сортировка выбором

    Задача сортировки массива – это перестановка элементов массива так, чтобы они были упорядочены по возрастанию, убыванию или другой аналогичной характеристике.

    3.1.1. Алгоритм сортировки прямым выбором по убыванию

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

    Рассмотрим алгоритм сортировки выбором. Суть ее в случае упорядочивания по убыванию заключается в следующем. Будем просматривать массив слева направо. Найдем максимальный элемент в массиве и поменяем его с первым элементом. Затем найдем максимальный элемент среди оставшихся элементов и поменяем его со вторым элементом. На N-1 шаге мы закончим упорядочивание нашего массива, состоящего из N элементов [2].

    3.1.2. Алгоритм сортировки прямым выбором по возрастанию

    Используя флеш-ролик (Приложение 3), выполним алгоритм сортировки выбором. Ученик у доски выполняет упорядочивание элементов массива по возрастанию, используя алгоритм сортировки прямым выбором.

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

    3.2. Сортировка обменом или «пузырьковая» сортировка

    «Пузырьковая» сортировка традиционно считается более простой в реализации [2].

    3.2.1. Алгоритм сортировки обменом или «пузырьковая» сортировка по возрастанию

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

    Суть упорядочивания по возрастанию заключается в следующем. Просматриваем слева направо все пары соседних элементов. Если при этом рассматриваемый элемент массива больше следующего, то элементы меняем местами. В результате такого просмотра массива максимальный элемент окажется на крайнем справа (своём) месте. Будем просматривать массив снова, исключив из рассмотрения правый элемент. На своем месте теперь окажется уже второй по величине элемент. В последнем просмотре будут участвовать только первый и второй элементы. Общее число просмотров массива из N элементов при этом равно N-1 [2].

    3.2.2. «Пузырьковая» сортировка по убыванию

    Используя флеш-ролик (Приложение 4), выполним алгоритм сортировки обменом. Ученик у доски выполняет упорядочивание элементов массива по убыванию, используя алгоритм сортировки обменом.

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

    3.2.3. Усовершенствованная «пузырьковая» сортировка

    При просмотре видеоматериала (Приложение 2) обращаем внимание учеников на то, что «пузырьковую» сортировку можно усовершенствовать.

    Используя флеш-ролик (Приложение 5), выполним алгоритм «пузырьковой» сортировки. Сформулируем, как надо изменить алгоритм, чтобы он заканчивал свою работу в случае, когда на очередном проходе не произошло ни одного обмена (это означает, что массив уже отсортирован и дальнейшие проходы не нужны) [2].

    4. Рефлексия деятельности на уроке

    Рассмотрели наиболее простые алгоритмы сортировки:

    1. сортировка выбором;
    2. сортировка обменом или «пузырьковая» сортировка;
    3. усовершенствованная «пузырьковая» сортировка.

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

    5. Практическая работа

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

    1. Выполнить сортировку только четных элементов массива (нечетные элементы остаются на своих местах)

    Примерный вариант решения задачи:

    2. Выполнить сортировку элементов, записанных на нечетных местах [4].

    Примерный вариант решения задачи:

    Для помощи в составлении и отладке программ ученик может самостоятельно за своим рабочим местом просмотреть видеоматериалы и флеш-приложения еще раз.

    6. Домашнее задание

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

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

    Список учебной и дополнительной литературы

    1. Семакин И.Г. Информатика и ИКТ: учебник для 9 класса. Москва, БИНОМ. Лаборатория знаний, 2010.
    2. Андреева Е.В. Программирование – это так просто, программирование – это так сложно. Современный учебник программирования. – М.: МЦНМО, 2009.
    3. Златопольский Д.М. Программирование: типовые задачи, алгоритмы, методы. Москва, БИНОМ. Лаборатория знаний,2007.
    4. Окулов С.М. Основы программирования. Москва, БИНОМ. Лаборатория знаний, 2010.
  • Ссылка на основную публикацию
    ВсеИнструменты
    Adblock
    detector
    ×
    ×