Презентация по теме "Сортировка массива"

Алгоритм выбора использует вложенные циклы.

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

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

Метод простого обмена (пузырьковая сортировка)

В основе алгоритма лежит обмен соседних элементов массива.

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

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

Этот процесс повторяется на единицу меньше раз, чем элементов в массиве.

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

Идея – пузырек воздуха в стакане воды поднимается со дна вверх.

Для массивов – самый маленький («легкий» элемент перемещается вверх («всплывает»).

1-ый проход

• начиная снизу, сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами
• за 1 проход по массиву один элемент (самый маленький) становится на свое место

5

1

2

3

5

2

1

3

5

1

2

5

2

1

3

3

2-ой проход

3-ий проход

1

2

5

3

1

2

3

5

Для сортировки массива из N элементов нужен N -1 проход (достаточно поставить на свои места N-1 элементов).

1

5

2

3

1

1

2

5

5

2

3

3

Пример работы алгоритма простого обмена

• Исходный массив: 8, 3, 6, 4, 1 (последовательно меняются местами 8 и 3,8 и 6, 8 и 4, 8 и 1)
• После первого шага: 3, 6, 4, 1, 8

(далее последовательно меняются местами 6 и 4, 6 и 1)

• После второго шага: 3, 4, 1, 6, 8 (последовательно меняются местами 4 и 1)
• После третьего шага: 3, 1, 4, 6, 8 (последовательно меняются местами 3 и 1)
• После четвертого шага: 1, 3, 4, 6, 8

a [k + 1] then begin { обменяем k-й и (k + 1)-й элементы } buf:= a [k]; a [k]:= a [k + 1]; a [k + 1]:= buf; end; writeln (‘ Массив отсортирован .’); for k:= 1 to SIZE do write (a [k], ‘ ’); readln; end. Метод обмена " width="640"

Program Obmen;

const

SIZE=5

var

a: array [1..SIZE] of integer;

i , k , buf: integer;

begin

write (‘ Введите’ ,SIZE: 3, ’целых в одной строке через пробел’ );

for k:= 1 to SIZE do read (a [k]);

for i:= 1 to SIZE - 1do

for k:= 1 to SIZE – i do

if a [k] a [k + 1] then

begin

{ обменяем k-й и (k + 1)-й элементы }

buf:= a [k];

a [k]:= a [k + 1];

a [k + 1]:= buf;

end;

writeln (‘ Массив отсортирован .’);

for k:= 1 to SIZE do write (a [k], ‘ ’);

readln;

end.

Метод обмена

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

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

Пусть дана последовательность элементов a 1 , a 2 , ... , a n .

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

Сортировка означает перестановку элементов последовательности a k1 , a k2 , ... , a kn такую, что

a k 1 a k 2 a kn .

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

Это означает, что алгоритм не должен использовать дополнительных массивов и пересылок из массива a в эти массивы.

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

• сравнение двух элементов ( x y ) и пересылка элемента ( x := y ).
• сравнение двух элементов ( x y )
• и пересылка элемента ( x := y ).

Поэтому удобная мера сложности алгоритма сортировки массива a[1..n] :

• по времени – количество сравнений C (n) и количество пересылок M ( n ) .
• по времени – количество сравнений C (n)
• и количество пересылок M ( n ) .

Практическая часть

Задача1 . На соревнованиях по прыжкам в длину получен массив результатов b(n). Определить три лучших результата. Массив сформировать с помощью функции R A ND OM .

Задача2. Составить программу, которая выполняет сортировку фамилий в исходном массиве по алфавиту.

Успехов Вам!