Remkomplekty.ru

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

Процедура сортировки массива паскаль

Сортировка одномерных массивов по убыванию и возрастанию в 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-го, это значит что количество проверяемых чисел станет меньше, что это значит. Вот когда у нас идет первый цикл, у нас проверяются все числа и мы находим самый последний элемент, он у нас хоть как самый большой и больше смысла проверять его просто нет. Когда пойдет уже второй цикл у нас это число просто не будет затрагиваться вот и всё, а какой смысл его затрагивать ведь оно и так самое больше? И так после каждого прохода цикла )))

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

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

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]
кц

Читать еще:  Rewrite паскаль что значит

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

Процедура сортировки массива паскаль

В повседневной жизни нам очень часто приходится раскладывать наши вещи, книги, кассеты диски и т. п. в удобном для нас порядке. Для чего? Чтобы облегчить их дальнейший поиск. В библиотеке мы раскладываем книги по авторам, в телефонной книге мы записываем фамилии по алфавиту, в словаре слова расставлены по алфавиту. С появлением компьютеров люди стали использовать «железных монстров» для хранения больших объемов информации. Очевидно, что появилась потребность обработки данных. Две самые необходимые для этого функции — это сортировка и поиск. На первой мы и остановимся.

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

Обычно алгоритмы сортировки разделяются на два типа — сортировка массивов и сортировка последовательностей. В этой статье речь пойдет о сортировке массивов как наиболее часто встречающейся задаче при создании программы обработки данных. Под «массивом» я подразумеваю одномерный массив. Думаю, для вас не составит труда после прочтения статьи написать алгоритм сортировки двухмерного или более массива. Моя цель — не написать вам готовую программу, а познакомить с идеей, методом. Для практичности за описанием алгоритма будет следовать исходный код программы-примера на языке Паскаль. Почему на Паскале? Да потому что это наиболее распространенный язык для учебных целей. И, на мой взгляд, Паскаль лучше всего подходит для демонстрации механизмов сортировки.

Для оценки эффективности алгоритма мы будем использовать два значения: количество сравнений ключей (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]. Сортировка каждого расстояния делается как сортировка прямым включением. Для условия окончания сортировки придется установить барьер, и не один.

Последний алгоритм, который мы рассмо¬трим, является самым быстрым из всех ныне существующих. Автор Ч. Хоар так и назвал его — Quicksort. В Quicksort сначала делают перемещения на большие расстояния. Для этого наугад выбираем в массиве элемент х. Просматриваем массив слева, пока не встретим элемент A[i]>x, потом смотрим массив справа, пока не обнаружим элемент А[j]

Процедура сортировки массива паскаль

страницы: 1 2

Содержание

Улучшенные сортировки

В отличие от простых сортировок, имеющих сложность

N 2 , к улучшенным сортировкам относятся алгоритмы с общей сложностью

Необходимо, однако, отметить, что на небольших наборах сортируемых данных (N 1 базируется на уже известном нам алгоритме простых вставок ПрВст. Смысл её состоит в раздельной сортировке методом ПрВст нескольких частей, на которые разбивается исходный массив. Эти разбиения помогают сократить количество пересылок: для того, чтобы освободить «правильное» место для очередного элемента, приходится уже сдвигать меньшее количество элементов.

Алгоритм УлШелл

На каждом шаге (пусть переменная t хранит номер этого шага) нужно произвести следующие действия:

  1. вычленить все подпоследовательности, расстояние между элементами которых составляет kt;
  2. каждую из этих подпоследовательностей отсортировать методом ПрВст.

Нахождение убывающей последовательности расстояний kt, kt-1. k1 составляет главную проблему этого алгоритма. Многочисленные исследования позволили выявить её обязательные свойства:

  • k1 = 1;
  • для всех t kt > kt-1;
  • желательно также, чтобы все kt не были кратными друг другу (для того, чтобы не повторялась обработка ранее отсортированных элементов).

Дональд Кнут предлагает две «хорошие» последовательности расстояний:

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

Как же определить начальное значение для t (а вместе с ним, естественно, и для kt)?

Можно, конечно, шаг за шагом проверять, возможно ли вычленить из сортируемого массива подпоследовательность (хотя бы длины 2) с расстояниями 1, 3, 7, 15 и т. д. между её элементами. Однако такой способ довольно неэффективен. Мы поступим иначе, ведь у нас есть формула для вычисления kt = 2 t -1.

Итак, длина нашего массива (N) должна попадать в такие границы:

Прологарифмируем эти неравенства (по основанию 2):

Таким образом, стало ясно, что t можно вычислить по следующей формуле:

К сожалению, язык Pascal предоставляет возможность логарифмировать только по основанию е (натуральный логарифм). Поэтому нам придётся вспомнить знакомое из курса средней школы правило «превращения» логарифмов:

В нашем случае m = 2, z = e. Таким образом, для начального t получаем:

Однако при таком t часть подпоследовательностей будет иметь длину 2, а часть — и вовсе 1. Сортировать такие подпоследовательности незачем, поэтому стоит сразу же отступить ещё на 1 шаг:

Расстояние между элементами в любой подпоследовательности вычисляется так:

Количество подпоследовательностей будет равно в точности k. В самом деле, каждый из первых k элементов служит началом для очередной подпоследовательности. А дальше, начиная с (k + 1)–го, все элементы уже являются членами некоторой, ранее появившейся подпоследовательности, значит, никакая новая подпоследовательность не сможет начаться в середине массива.

Сколько же элементов будет входить в каждую подпоследовательность? Ответ таков: если длину всей сортируемой последовательности (N) можно разделить на шаг k без остатка, тогда все подпоследовательности будут иметь одинаковую длину, а именно:

Если же N не делится на шаг k нацело, то первые р подпоследовательностей будут длиннее на 1. Количество таких «удлинённых» подпоследовательностей совпадает с длиной «хвоста» — остатка от деления N на шаг k:

Читать еще:  Паскаль размерность в си

Реализация алгоритма УлШелл

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

program shell_sort ;
const
n = 18 ;
a : array [ 1 .. n] of Integer =
( 18 , 17 , 16 , 15 , 14 , 13 , 12 , 11 , 10 , 9 , 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 ) ;
var ii , m , x , s , p , t , k , r , i , j : Integer ;
begin
t := Trunc ( Ln (n) / Ln ( 2 )) ;
repeat
t := t — 1 ;
k := ( 1 shl t) — 1 ;
p := n mod k ;
s := n div k ;
if p = 0 then
p := k
else
s := s + 1 ;

WriteLn (k , ‘-сортировка’ ) ;
for i := 1 to k do <берём и длинные, и короткие подпоследовательности>
begin
if i = p + 1 then
s := s — 1 ; <для коротких — уменьшаем длину>
for j := 1 to s — 1 do <метод ПрВст с шагом k>
if a[i + (j — 1 ) * k] > a[i + j * k] then
begin
x := a[i + j * k] ;
m := i + (j — 1 ) * k ;
while (m > 0 ) and (a[m] > x) do
begin
a[m + k] := a[m] ;
m := m — k ;
end ;
a[m + k] := x ;
end ;
for ii := 1 to n do
Write (a[ii] , ‘ ‘ ) ;
WriteLn ;
end ;
until k = 1 ;
end .

Результат работы

7–сортировки

3–сортировки

1–сортировка

Эффективность алгоритма УлШелл

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

N 3/2 . И хотя это несколько хуже, чем N*logN, всё–таки эта сортировка относится к улучшенным.

Пример сравнения сортировок: Вновь возьмём последовательность, для сортировки которой методом простых вставок ПрВст потребовалось 15 сдвигов (25 пересылок и 20 сравнений):

Теперь применим к ней метод Шелла.

Здесь N = 7, поэтому:

  1. 3–сортировки:

Состояние массива Сдвиги Сравнения Пересылки данных

0 шаг: 1323645
1 шаг: 1 323645 0 1 0
2 шаг: 13 23645 1 1+1 1+2
3 шаг: 123 3645 0 1 0
4 шаг: 1233 645 0 1 0
5 шаг: 12336 45 1 1+1 1+2
6 шаг: 123346 5 1 1+1 1+2
результат: 1233456 3 9 9

При сортировке методом Шелла в сумме получилось 7 сдвигов (19 пересылок и 17 сравнений). Выигрыш по сравнению с методом простых вставок составляет 53% (24% экономится на пересылках и 15% — на сравнениях) 2 . Если вместо метода простых вставок ПрВст использовать метод бинарных вставок БинВст, то выигрыш по количеству сравнений будет ощутимее.

Кроме того, не нужно забывать, что в нашем примере последовательность очень коротка: N = 7. Для больших N (скажем, N = 10000) преимущество метода Шелла станет ещё заметнее.

Пирамидальная сортировка

Попытаемся теперь усовершенствовать другой рассмотренный выше простой алгоритм: сортировку простым выбором ПрВыб.

Р. Флойд предложил перестроить линейный массив в пирамиду — своеобразное бинарное дерево, — а затем искать минимум только среди тех элементов, которые находятся непосредственно «под» текущим вставляемым.

Просеивание

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

Итак, будем рассматривать наш линейный массив как пирамидальную структуру:

Процедура сортировки массива паскаль

Категории:

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

Полина:
Мы такие задачи решаем в 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.
Вот результат:

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

Ссылка на основную публикацию
Adblock
detector