Как сделать сортировку массива pascal
Pascal: Занятие № 5. Одномерные массивы в Паскале
Одномерные массивы в Паскале
Объявление массива
Массивы в Паскале используются двух типов: одномерные и двумерные.
Определение одномерного массива в Паскале звучит так: одномерный массив — это определенное количество элементов, относящихся к одному и тому же типу данных, которые имеют одно имя, и каждый элемент имеет свой индекс — порядковый номер.
Описание массива в Паскале (объявление) и обращение к его элементам происходит следующим образом:
Объявить размер можно через константу:
Инициализация массива
Кроме того, массив может быть сам константным, т.е. все его элементы в программе заранее определены. Описание такого массива выглядит следующим образом:
const a:array[1..4] of integer = (1, 3, 2, 5);
Заполнение последовательными числами:
Ввод с клавиатуры:
Вывод элементов массива
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
Диапазон в Паскале тех самых случайных чисел от a до b задается формулой:
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 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.
Максимальный (минимальный) элемент массива
Поиск максимального элемента по его индексу:
Пример:
Поиск в массиве
Рассмотрим сложный пример работы с одномерными массивами:
Для решения поставленной задачи понадобится оператор break — выход из цикла.
Решение Вариант 1. Цикл 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.
Рассмотрим эффективное решение:
Алгоритм:
решение на Паскале Вариант 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;
Выполнение на Паскале:
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;
Рубрики:
См. пузырьковая сортировка.
При второй итерации цикла (согласно вашим рисункам и коду ) нет надобности сравнивать первый элемент со вторым. Снова вы всех путаете =)
admin
Именно поэтому в коде : for j:=N-1 downto i do
downto i — то есть мы доходим сначала до первого элемента, потом до второго и т.д.
Bronislav
Смотрите. Ваш код работает. Но работает не так, как вы пишете перед этим. Он просеивает минимальный элемент с конца через весь массив до первой позиции (первого индекса если хотите). А не так как вы пишете: «При второй итерации цикла нет надобности сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте, он самый большой.» Соответственно вашему коду и вашим рисункам на второй итерации не сравнивается первый элемент (минимальный) со вторым, а не последний (который вообще не факт что максимальный) с предпоследним. Вот об чем речь. Или код меняйте или описание алгоритма перед кодом.
Владимир
В сохранении в другой массив ошибка. Надо поменять местами счётчик и команду сохранения. В массиве В нет элемента 0.
Как сделать сортировку массива pascal
В повседневной жизни нам очень часто приходится раскладывать наши вещи, книги, кассеты диски и т. п. в удобном для нас порядке. Для чего? Чтобы облегчить их дальнейший поиск. В библиотеке мы раскладываем книги по авторам, в телефонной книге мы записываем фамилии по алфавиту, в словаре слова расставлены по алфавиту. С появлением компьютеров люди стали использовать «железных монстров» для хранения больших объемов информации. Очевидно, что появилась потребность обработки данных. Две самые необходимые для этого функции — это сортировка и поиск. На первой мы и остановимся.
Сначала появились самые простенькие алгоритмы, впоследствии изобретались более эффективные. И хоть рассказать обо всех в рамках данной статьи невозможно, я опишу наиболее распространенные и известные.
Обычно алгоритмы сортировки разделяются на два типа — сортировка массивов и сортировка последовательностей. В этой статье речь пойдет о сортировке массивов как наиболее часто встречающейся задаче при создании программы обработки данных. Под «массивом» я подразумеваю одномерный массив. Думаю, для вас не составит труда после прочтения статьи написать алгоритм сортировки двухмерного или более массива. Моя цель — не написать вам готовую программу, а познакомить с идеей, методом. Для практичности за описанием алгоритма будет следовать исходный код программы-примера на языке Паскаль. Почему на Паскале? Да потому что это наиболее распространенный язык для учебных целей. И, на мой взгляд, Паскаль лучше всего подходит для демонстрации механизмов сортировки.
Для оценки эффективности алгоритма мы будем использовать два значения: количество сравнений ключей (K) и число пересылок элементов (S). Последнее значение представляет для нас большой интерес — пересылка данных в памяти является более длительным процессом, чем сравнение. Также при описании алгоритмов я буду использовать такие величины: n — количество элементов массива, А[1..n] — сортируемый массив, x — переменная того же типа, что и элементы массива. Будем считать, что у нас массив целых чисел (А: array[l..n] of integer; х: integer;).
По количеству необходимых сравнений алгоритмы сортировки разделяют на два класса: более простые требуют примерно n^2 сравнений, а наиболее эффективные — порядка n*log(n). Я начну с более простых и наглядных алгоритмов. Первый метод сортировки, о котором я хочу рассказать, называется «сортировка с помощью прямого включения». Идея такова: мы по порядку берем элементы массива и ставим на их «законное» место. Начиная со второго, мы перебираем все элементы массива и последовательно сравниваем с элементами, которые имеют индекс меньше данного. Если наш элемент меньше предыдущего, то меняем их местами и продолжаем сравнивать дальше, если больше, то оставляем его — он уже на своем месте. И так продолжаем до тех пор, пока не достигнем левой границы массива. Чтобы в данном случае процесс сравнивания не уходил за пределы левой границы массива, необходимо создать так называемый «барьер» — добавить в начало массива ячейку (например, А[0]), в которую будем заносить сортируемый в этом проходе элемент. Вот полный код алгоритма:
Здесь A[0] — вышеупомянутый барьер, A[1..n] — сортируемый массив.
Мой совет: для простейших алгоритмов сортировок попробуйте написать на бумажке какую-нибудь последовательность из 4-5 чисел. А потом «прогоните» ее на листочке через алгоритм сортировки. При этом пишите значения всех переменных и изменения массива на каждом шаге. Это не так уж трудно сделать для первых трех алгоритмов и займет не больше половины тетрадного листа. Таким образом гораздо легче понять алгоритм. Конечно, для усовершенствованных методов это представляет значительную сложность, но и в этом случае есть выход. Например, в Delphi можно запустить программу в пошаговом режиме и смотреть значения всех переменных программы — очень полезная вещь для того чтобы понять, как работает какая-то часть программы. Не пренебрегайте этим советом!
Средние числа сравнения ключей и пересылки элементов имеют следующие значения: K=(n^2+n-2)/4, S=(n^2+9n-10)/4 Минимальные и максимальные значения такие: Kmin=n-1, Smin=3*(n-1), Kmax=(n^2+n-4)/4, Smax=(n^2+3n-4)/2. У алгоритма есть один существенный недостаток. Предположим, у нас есть массив чисел: 3,7,4,6,8,2. В этом случае последний элемент массива (2) придется «тащить» через весь массив.
Попробуем алгоритм, где перемещения делаются на большие расстояния. Такой алгоритм называется «сортировка прямым выбором». Он основан на следующей идее: выбираем в массиве наименьший элемент и меняем его местами с первым, после этого повторяем данную операцию для оставшихся элементов до тех пор, пока не останется единственный элемент. Ниже следует сам алгоритм:
В данном случае никакого барьера (A[0]) не нужно, и мы рассматриваем массив в диапазоне [1..n].
Сравнение ключей: K=(n^2-n)/2. Для пересылки ключей вычислить среднее значение нелегко, потому привожу минимальное (ключи уже отсортированы) и максимальное (ключи стоят в обратном порядке) значения: Smin=3*(n-1), Smax=n^2/4+3*(n-l). Как видим, алгоритм прямого выбора в большинстве случаев эффективнее прямого включения. Исключение составляет лишь ситуация, когда массив уже упорядочен или почти упорядочен. Однако в этом случае выигрыш не столь велик, и в целом данный метод предпочтительнее, чем предыдущий.
И последний тип сортировки первого класса называется «сортировка прямым обменом». Основное отличие этого метода от двух вышеперечисленных — обмен является характерной особенностью этого алгоритма. Идея алгоритма: последовательно перебираются по два рядом стоящих элемента, сравниваются и, в случае необходимости, меняются местами. Повторяем данную операцию до тех пор, пока не упорядочим весь массив.
При таких проходах по массиву мы сдвигаем наименьший элемент к левому краю. Если мы представим массив как вертикальную цепочку, то элементы при сортировке будут как пузырьки «всплывать» на свой уровень. Поэтому более широко известное наименование данного метода — «пузырьковая сортировка». Вот как выглядит код этого алгоритма:
Здесь используется переменная f в качестве флага. Если f=true, значит, в последнем проходе были сделаны перестановки и нужны еще проходы, а если f=false, значит, перестановок в последнем проходе не было и массив уже отсортирован. В этом алгоритме есть также свой недостаток: если наименьшее число расположено в конце массива, то для того, чтобы переместить его в начало (на его «законное» место), потребуется n-1 проходов. А в это время наибольший элемент с начала массива переместится в конец за один проход. Согласитесь, довольно неприятный факт. Вывод напрашивается сам собой: необходимо проходить массив с разных сторон по очереди, т. е. первый раз с начала в конец, второй — с конца в начало, третий — опять с начала в конец и т. д. Такой улучшенный алгоритм называется «шейкерной сортировкой» (ShakerSort). А вот программу для данного варианта предлагаю написать самим. Если вы полностью разобрались с методом пузырьковой сортировки, то это не будет для вас сложной задачей.
Для пузырьковой и шейкерной сортировок подсчитать число сравнений ключей и пересылок довольно сложно. Поэтому объективно сравнить эффективность последних двух методов с предыдущими мы сможем в конце статьи — я приведу время сортировки массива различными алгоритмами.
Теперь мы вплотную подошли к обсуждению улучшенных методов сортировки. Разобраться в них гораздо сложнее. В 1959 году Д. Шелл предложил усовершенствованную сортировку прямого включения. Идея довольно простая. Сначала мы сортируем элементы, отстоящие друг от друга на расстоянии 4. Например, берем элемент A[1] и сравниваем его с элементом A[5] (A[1+4]), если А[1] больше А[5], то меняем их местами. Потом берем A[2] и сравниваем с A[6] и т. д. После этого прохода с «четвертной» сортировкой проходим по массиву опять, но уже сортируем элементы, отстоящие друг от друга на расстоянии 2. И на последнем проходе идет обычная одинарная сортировка. Последовательность расстояний можно менять, как и их количество. Поэтому для обобщения все t расстояний занесем в массив s[1..t]. Сортировка каждого расстояния делается как сортировка прямым включением. Для условия окончания сортировки придется установить барьер, и не один.
Отсортировать массив по возрастанию
Решите эти задачи пожалуйста очень надо.
1. Организуйте массив, содержащий 20 различных целых чисел. После этого элементы массива упорядочиваются по убыванию и содержимое отсортированного массива выводится на экран.
3. Организуйте массив, содержащий 15 различных целых чисел. После этого первых 5 элементов, вторых 5 элементов и последних 5 элементов сортируются по возрастанию. Содержимое таким образом отсортированного массива выводится на экран.
4. Организуйте массив, содержащий 10 различных целых чисел. Одержимое массива сортируется по возрастанию, и после этого определяется минимальный и максимальный элементы массива.
5. Организуйте массив, содержащий 20 различных символов. Отсортируйте его по возрастанию.
6. Организуйте массив, содержащий 20 целых чисел. Отсортируйте отдельно элементы с четными индексами по возрастанию, и элементы с нечетными индексами по убыванию.
7. Организуйте массив, содержащий 20 целых чисел. Отсортируйте его по возрастанию. После этого определите и выведите на экран сумму элементов с четными индексами и сумму элементов с нечетными индексами.
8. Создайте массив, содержащий 15 целых чисел. Отдельно первых 5 элементов массива вторых 5 элементов и последних 5 элементов отсортируйте по убыванию. Определите и выведите на экран сумму каждой пятерки отсортированного таким образом массива.
9. Создайте массив, содержащий 15 различных символов. Отсортируйте его по убыванию. После этого определите и выведите на экран «наименьший» и «наибольший» символы.
10. Создайте массив, содержащий 10 различных символов. Первую половину массива отсортируйте по возрастанию, а вторую по убыванию. Отсортированный массив выведите на экран.
11. Создайте массив А, содержащий 8 различных символов. Отсортируйте его по возрастанию. Организуйте и выведите на экран целочисленный массив В, заполнив его числами, полученными преобразованием символов массива А в целые числа.
12. Создайте целочисленный массив А, содержащий 10 различных чисел. Отсортируйте первую половину массива А по возрастанию, а вторую по убыванию. Организуйте и выведите на экран символьный массив В, заполнив его символами, полученными преобразованием чисел массива А в символы.
13. Создайте массив содержащий 20 различных целых чисел. Отсортируйте его по возрастанию. После этого замените все элементы массива на противоположные и выведите содержимое обработанного массива на экран.
14. Создайте массив содержащий 20 различных целых чисел. Отсортируйте первую половину массива по возрастанию, а вторую по убыванию. Все четные элементы массива увеличить в 3 раза, а нечетные в 2 раза. Содержимое таким образом отсортированного массива выводится на экран.
сортировка строк массива
Подскажите пожалуйста как сортировать строки некого массива.
Допустим нам дан двумерный массив с размерностью 5 на 5 целых чисел, не важно как, заполняется массив числами, он же выводится. А вот далее:
1) Нужно найти наименьшее значение в каждой строке
2) Отсортировать строки в порядке убывания найденных элементов.
(разделил на пункты чтобы попонятнее было)
.. ну и вывести конечный массив.
Сортировка массива строк
Дан массив из n слов. Написать программу, которая сортирует слова по длине, от максимального к.
Сортировка строк двумерного массива
Друзья нужно помочь отсортировать строки двумерного массива по возрастанию по первому элементу.
Сортировка массива состоящего из строк!! Подскажите
У нас есть текстовой файл с цифрой в начале указывающей количество имен ниже и именами (каждое имя.
.
For i:=1 to n do
For j:=1 to n do
read(a[i,j]);
.
Ах да, еще хотел спросить на счет. М. в общем, нужно как-то из текстового фаила выгрузить массив в программу. Далее идут преобразования(сортировка строк как раз) и результат нужно переписать в этот же текстовый фаил
Добавлено через 14 минут
ладно начну с «пирогов».
о господи.
Я наверное не так в самом начале написал. перефразирую.
Нужно отсортировать массив по строкам(т.е Все элементы должны остаться на своих местах. А переносить нужно сами строки(группу элементов)) Причем отсортировать так: в порядке убывания самого маленького элемента каждой строки.
Приложил док с самим заданием от препода. Вариант 11. Чесно скажу у нас препод всё делает через кхм.
Вложения
______________________________________2________________(30_____________)_(1).doc (58.5 Кб, 32 просмотров) |
Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.
Сортировка элементов строк / столбцов двумерного массива
Необходимо заполнить массив 4х4 случайными числами и сделать сортировку : элементов строк по.
Сортировка строк массива методом простого включения
Дана квадратная матрица, упорядочить строки алгоритмом простого включения по возростанию сумм.
Сортировка строк двухмерного массива методом вставки
TP/FPC: Упорядочить в возрастающем порядке элементы каждой строки двухмерного массива, используя.