Сортировка массивов в среде DELPHI - LAZARUS 10 класс

DELPHI-LAZARUS»

ШУНТОВА ЛЮДМИЛА ВЛАДИМИРОВНА
учитель информатики
МБОУ Лесногородской сош
Одинцовского

района Московской области

2013 год

управления Б.Д.,
сетевое программное обеспечение и т.д.
ДАННЫЕ-символьная,графическая, мультимедийная информация

сортировки данных.

От эффективности их выполнения во многом зависит эффективность работы

всей программы.

Различают алгоритмы
внутренней сортировки – во внутренней памяти внешней сортировки- сортировки файлов

в массивах.
В простейшем случае – сортируются числовые массивы.

в определенном порядке (убывания или возрастания)
(Д.Златопольский)
Сортировка- один из наиболее распространенных

процессов современной обработки информации. Это распределение элементов множества по группам в соответствии с определенными правилами.
(Е.В.Андреева)

Слияниями
Пирамидальная

элементов, меньших его.
Например, если значение некоторого элемента исходного массива

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

элем)
5 место
(4 элем)
6 место
(5 элем)
7 место
(6 элем)
8 место
(7 элем)

a}
нц для I от 1 до n

k [i]:=0
кц
нц для I от 2 до n
нц для j от 1 до i-1
если a [i] то {увеличиваем значение к для j-го элемента}
k [j]:= k [j] +1
иначе {увеличиваем значение k для i-го элемента}
k [i]:= k [i] +1
все
кц
кц
{размещаем все элементы массива а на соответствующих им местах в массиве b
нц для I от 1 до n
b [k [i] + 1]:=a [i] {позиция в массиве больше на 1 к-ва меньших по в-не числ}
кц
кон

элемент исключается из дальнейшей обработки , а оставшаяся последовательность элементов

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

min:=a[1] indmin:= 1
нц для j от 2

до n
если a [j] < a [indmin]
то {увеличиваем значение к для j-го элемента}
min:= a [j]
indmin := j
все
кц
{записываем минимальный элемент на i-е место в массиве b }
b [i] := min
{заменяем минимальный элемент исходного массива «большим числом»
b [i] := max
Кц
{выводим на экран отсортированный массив b}
нц для I от 1 до n
вывод b [i]
кц
кон

массива
Для нахождения минимального элемента и его индек-са на каждом проходе

приходится просматривать все элементы массива
Указанные недостатки устраняются, если все изменения проводить в исходном массиве:
Найти минимальный элемент среди всех элементов массива и поменять его местами с первым элементом
Найти минимальный элемент среди второго, третьего и т.д. элементов массива и поменять его местами со вторым элементом и т.д.
….
В данной разработке урока применяется именно этот способ

do {i - позиция, в которую нужно записать}
begin Min1 :=

999999; {нач. значение для поиска минимальный элемента }
for j := i to Dreal do {Поиск минимального элемента }
begin if Mass [j] < Min1 then {в оставшейся части массива }
begin k := j; Min1 := Mass [j]; {к - номер найденного элемента }
end; {Min1 - найденное значение }
end; { }
rab := Mass[i]; {Обмен элементов массива }
Mass [i] := Min1; {с номерами (i) и (k) }
Mass [k] := rab; { }
sss := ''; {Вывод }
for rab := 1 to dreal do {текущего }
begin sss := sss + intToStr(Mass[rab]) + ' '; {состояния }
end; {массива }
ListBox3.Items.Add(sss); {в список }
ListBox3.ItemIndex := ListBox3.Count - 1; {ListBox3 }
sleep(5000); {Задержка }
end;
ListBox3.Items.Add('OK !'); {Вывод "OK"}
end;

сравниваются друг с другом и меняются местами, если предшествующий элемент

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

массива –внизу)
и проследить за перемещением элементов, то можно увидеть,

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

1 to n-1 do{кол-во повторений}
begin
for j := 1

to n-1 do
begin
if Mass [j] > Mass [j + 1] then {Если 2 соседа нарушают }
begin rab := Mass[j]; {порядок возрастания, то }
Mass[j] := Mass[j + 1]; {производится их обмен }
Mass[j + 1] := rab; { }
k := k + 1; {к - счетчик обменов }
end; { }
end;
sss := ''; {Вывод }
for rab := 1 to Dreal do {текущего }
begin sss := sss + intToStr(Mass[rab]) + ' '; {состояния }
end; {массива }
ListBox3.Items.Add(sss); {в список }
ListBox3.ItemIndex := ListBox3.Count - 1; {ListBox3 }
sleep(5000); {Задержка }
end;
ListBox3.Items.Add('OK ! Перестановок= ' + intToStr(k)); {Вывод "OK"}
end;

каждый элемент, сравнивается с предыдущим (уже упорядоченным) списком и помещается

на соответствующее место в нем.
В данном примере жирным выделен очередной элемент, а стрелкой- место для его размещения. На второй строке –вид массива после очередного перемещения.

1-й этап: 38 12 80 15 36 23 74 62
12 38 80 15 36 23 74 62

2-й этап: 12 38 80 15 36 23 74 62
12 38 80 15 36 23 74 62

3-й этап: 12 38 80 15 36 23 74 62
12 15 38 80 36 23 74 62

12 15

36 38 80 23 74 62


5-й этап: 12 15 36 38 80 23 74 62
12 15 23 36 38 80 74 62


6-й этап: 12 15 23 36 38 80 74 62
12 15 23 36 38 74 80 62

7-й этап:

12 15 23 36 38 74 80 62
12 15 23 36 38 62 74 80

:= ListBox3.Count - 1; {вывод текущего массива }
sleep(5000);

{Задержка }
for i := 2 to Dreal do
Begin {i - номер элемента, который }
for j := 1 to i - 1 do {вставляется в растущий массив }
begin if Mass [j] > Mass [i] then {Поиск номера элемента, }
begin rab := Mass [i]; {который больше вставляемого }
for k := i - 1 downto j do {Если такой элемент найден, }
begin {то на его место вставляем }
Mass[k + 1] := Mass[k]; {i-й элемент, а остальные }
end; {сдвигаем на 1 позицию вправо }
Mass[j] := rab; goto Lab1 { }
end; { }
end;
Lab1: sss := ''; {Вывод }
for rab := 1 to i do {текущего }
begin sss := sss + intToStr(Mass[rab]) + ' '; {состояния }
end; {массива }
ListBox3.Items.Add(sss); {в список }
ListBox3.ItemIndex := ListBox3.Count - 1; {ListBox3 }
sleep(5000); {Задержка }
end;
ListBox3.Items.Add('OK !');
end;
end;
end;
end;

причин заняться ею!
Изобретательные методы сортировки говорят о том, что

она и сама по себе интересна как объект исследования.»
Д.Кнут

типовые задачи, алгоритмы, методы»
3. И.Г.Семакин
«Информатика» учебник

для 10 класса профильный курс
4. И.Г.Семакин А.П.Шестаков
«Основы программирования»