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

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

Категории:

Свежие
комментарии:

Полина:
Мы такие задачи решаем в 6 классе. Как раз вчера по инф..

Олег:
Спасибо, все очень подробно написано..

Калужский Александр:
Можете мне заказать.

Сортировка пузырьком (Pascal)

Сегодня мы разберем сортировку методом "пузырька". Данный алгоритм часто проходится в школах и университетах, поэтому будем использовать язык Pascal. И, так, что такое сортировка? Сортировка — это упорядочение элементов от меньшего к большему (сортировка по возрастанию) или от большего элемента к меньшему (сортировка по убыванию). Сортируют обычно массивы.

Существуют различные алгоритмы сортировки. Некоторые, хорошо сортируют большое количество элементов, другие, более эффективны при очень маленьком количестве элементов. Наш метод пузырька характерен:

Плюсы:

  • Простота реализации алгоритма
  • Красивое название

Минусы:

  • Один из самых медленных методов сортировки (Время выполнения квадратично зависит от длины массива n 2 )
  • Почти не применяется в реальной жизни (используется в основном в учебных целях)

Пусть есть у нас некий массив: 3 1 4 2

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

Вернемся к нашему массиву : 3 1 4 2
Берем первый элемент "3" сравниваем со следующим "1". Т.к. "3" > "1", то меняем местами:
1 3 4 2
Теперь сравниваем "3" и "4", тройка не больше четвёрки, значит ничего не делаем. Далее, сравниваем "4" и "2". Четыре больше, чем два — значит меняем местами: 1 3 2 4 . Цикл закончился. Значит самый большой элемент уже должен стоять на своём месте!! Видим, что у нас так и произошло. Где бы "4" (наш самый большой элемент) не находился — он всё равно, после прохождения циклом всего массива, будет последним. Аналогия — как пузырёк воздуха всплывает в воде — так и наш элемент, всплывает в массиве. Поэтому и алгоритм, называется "Пузырьковая сортировка". Чтобы расположить следующий элемент, необходимо, начать цикл сначала, но последний элемент можно уже не рассматривать, потому что он стоит на своём месте.

Читайте также:  Как записать передачу с телевизора на флешку

Сравниваем "1" и "3" — ничего не меняем.
Сравниваем "3" и "2" — Три больше двух, значит меняем местами. Получается : 1 2 3 4 . Второй цикл закончили. Мы сделали уже два цикла — значит, с уверенностью можно сказать, что у нас, два последних элемента уже отсортированы. Осталось нам отсортировать третий элемент, а четвёртый, встанет в нужное место, автоматически. Ещё раз, сравниваем первый элемент и второй — видим, что у нас уже всё на своих местах, значит, массив, можно считать, отсортированный по возрастанию элементов.

Теперь осталось запрограммировать данный алгоритм на языке Pascal.
Вот результат:

А вот видеоурок

Задача

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

Решение

Существует множество методов сортировки. Одни из них являются более эффективными, другие – проще для понимания. Достаточно простой для понимания является сортировкаметодом пузырька, который также называют методом простого обмена. В чем же он заключается, и почему у него такое странное название: "метод пузырька"?

Как известно воздух легче воды, поэтому пузырьки воздуха всплывают. Это просто аналогия. В сортировке методом пузырька по возрастанию более легкие (с меньшим значением) элементы постепенно "всплывают" в начало массива, а более тяжелые друг за другом опускаются на дно (в конец массива).

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

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

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

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

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

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

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

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

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

begin
for j :=1 to N -1 do
for i :=1 to N — j do
if M[ i ] > M[ i +1] then
swap (M[ i ],M[ i +1])
end;

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

Читайте также:  Разъем похожий на hdmi

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

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

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

begin
M[0] := -oo;
for j :=2 to N do
begin
i := j ;
while M[ i ] M[ i — 1] do
begin
swap (M[ i ],M[ i -1]);
i := i -1
end
end
end;

Процедура 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]
кц

begin
for j :=1 to N -1 do
begin
FindMin ( j , i );
swap (M[ j ],M[ i ])
end
end;

В программе, как уже было сказано, используется процедура 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;

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

Ссылка на основную публикацию
Программа для отформатировать флешку
Процесс форматирования флешки мало отличается от форматирования HDD или SSD-дисков. Далее мы рассмотрим лучшие программы для форматирования флешек (такие как...
Приложение следить за человеком по номеру телефона
Отслеживание по номеру телефона - это приложение для Android, благодаря которому вы всегда будете знать где находятся ваши родные и...
Приложение чтобы играть андроид игры на компьютер
Самый мощный эмулятор Android из всех Newest ReleaseВерсия 7.1.3 2020.03.04 Играйте бесплатно в любые игры для Android. Наслаждайтесь оптимизированной графикой...
Программа для оцифровки винила
Каталог продаваемых пластинок (49230) Минимальные аппаратные требования, или что надо иметь для оцифровки Компьютер со звуковой картой. Проигрыватель винила Корректор...
Adblock detector