Сортировки: введение

Июль 24, 2022

Главная
Информатика
Сортировки: введение

Содержание

2. Сортировки: терминология N – количество элементов массива Проход – последовательный просмотр всех элементов массива в прямом
3. Эффективность сортировок: время, затрачиваемое на программирование; время, затрачиваемое на собственно сортировку; необходимый объем памяти. Усовершенствованные методы
4. Сортировка прямого обмена Алгоритм: на каждом проходе сравниваются элементы А(i) и А(i+1) для i в интервале
5. Исходный массив Проход 1 45 А(1) 32 А(2) 5 А(3) 67 А(4) 98 А(5) 15 А(6)
6. Проход 4 5 А(1) 32 А(2) 15 А(3) 34 А(4) 8 А(5) 45 А(6) 67 А(7)
7. Блок-схема i=1 i:N-1 н > к ≤ j=1 j:N-1 > ≤ A(j):A(j+1) > Обмен j=j+1 i=i+1
8. Напрашиваются улучшения: запоминать индекс последнего обмена в проходе и следующий проход прерывать на данном индексе; если
9. Блок-схема i=1,l=N-1,ne=N-1 i:N-1 AND ne 0 н > к ≤ j=1, ne=0 j:l > ≤ A(j):A(j+1)
10. Асимметрия метода: «легкий» элемент в конце массива в случае просмотра слева направо будет просачиваться на свое
11. Исходный массив Проход 1 45 А(1) 32 А(2) 5 А(3) 67 А(4) 98 А(5) 15 А(6)
12. 5 А(1) 8 А(2) 32 А(3) 45 А(4) 15 А(5) 34 А(6) 67 А(7) 98 А(8)
13. Сортировка прямым выбором Идея: массив делится на две части – левую, уже отсортированную и правую, исходную;
14. Исходный массив Проход 1 45 А(1) 32 А(2) 5 А(3) 67 А(4) 98 А(5) 15 А(6)
15. Проход 5 5 А(1) 8 А(2) 15 А(3) 32 А(4) 98 А(5) 45 А(6) 34 А(7)
16. Блок схема i=1 i:N-1 н > к ≤ k=i, j=i+1 j:N > ≤ A(j):A(k) k=j j=j+1
17. Сортировка прямого включения Идея: массив делится на две части – левую, уже отсортированную и правую, исходную;
18. Исходный массив Проход 1 45 А(1) 32 А(2) 5 А(3) 67 А(4) 98 А(5) 15 А(6)
19. 5 А(1) 32 А(2) 45 А(3) 67 А(4) 98 А(5) 15 А(6) 34 А(7) 8 А(8)
20. i=2 i:N н > к ≤ x=A(i) j:2 ≤ A(j):x j=j-1 i=i+1 ≥ > Блок схема
22. Скачать презентацию

Слайд 2

Сортировки: терминология
N – количество элементов массива
Проход – последовательный просмотр всех элементов

массива в прямом или обратном направлении
C – число необходимых сравнений элементов
М - обмен (перестановка) элементов – запись значения i-того элемента массива в k-тый, а k-того – в i-тый с промежуточным сохранением одного из значений в специальной переменной

Слайд 3

Эффективность сортировок:
время, затрачиваемое на программирование;
время, затрачиваемое на собственно сортировку;

необходимый объем памяти.

Усовершенствованные методы сортировок: C÷N*logN
Простые методы: C÷N2

Перестановки элементов – строго на «том же месте»,
т.е. вспомогательный массив не используется

Слайд 4

Сортировка прямого обмена
Алгоритм: на каждом проходе сравниваются элементы А(i) и А(i+1)

для i в интервале от 1 до N-1, если А(i) больше А(i+1), то происходит обмен.
Число проходов N-1
Число сравнений С=n*(n-1)/2
Число обменов (среднее) М=С

Слайд 5

Исходный массив
Проход 1
45
А(1)
32
А(2)
5
А(3)
67
А(4)
98
А(5)
15
А(6)
34
А(7)
8
А(8)
Проход 2
32
А(1)
5
А(2)
45
А(3)
67
А(4)
15
А(5)
34
А(6)
8
А(7)
98
А(8)
Нет обмена
Проход 3
5
А(1)
32
А(2)
45
А(3)
15
А(4)
34
А(5)
8
А(6)
67
А(7)
98
А(8)
Нет обмена
Нет обмена

Слайд 6

Проход 4
5
А(1)
32
А(2)
15
А(3)
34
А(4)
8
А(5)
45
А(6)
67
А(7)
98
А(8)
Нет обмена
Нет обмена
Нет обмена
Проход 5
5
А(1)
15
А(2)
32
А(3)
8
А(4)
34
А(5)
45
А(6)
67
А(7)
98
А(8)
Нет обмена
Нет обмена
Нет обмена
Нет обмена
Нет обменов
Проход

А(1)

А(2)

А(3)

А(4)

А(5)

А(6)

А(7)

А(8)

Нет обмена

Нет обменов

Проход 7

А(1)

А(2)

А(3)

А(4)

А(5)

А(6)

А(7)

А(8)

Нет обменов

Число проходов – 7, число сравнений – 28, число перестановок – 16. Если рассматривать массив как вертикальный, то легкие элементы постепенно «всплывают» наверх – «пузырек».

Слайд 7

Блок-схема
i=1
i:N-1
н
>
к
≤
j=1
j:N-1
>
≤
A(j):A(j+1)
>
Обмен
j=j+1
i=i+1
≤
Ввод и вывод массива не показаны
Внешний цикл реализует N-1 проход,
i –

номер прохода

Внутренний цикл реализует N-1
сравнение элементов внутри
прохода

Для обеспечения устойчивости сортировки знак «равно» должен быть именно здесь

Слайд 8

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

на данном индексе;
если в текущем проходе не было обменов, сортировку можно заканчивать
Т.е., можно ввести специальную переменную numb_exc, в которой можно запоминать левый индекс последнего обмена. Если numb_ecx=0, то сортировку можно заканчивать

Слайд 9

Блок-схема
i=1,l=N-1,ne=N-1
i:N-1
AND
ne<>0
н
>
к
≤
j=1, ne=0
j:l
>
≤
A(j):A(j+1)
>
Обмен
j=j+1
l=ne,i=i+1
≤
≤
ne=j
ne (numb_exc) – если в предыдущем проходе не было

обменов, ne=0 и сортировка заканчивается

l (limit) – равняется индексу последнего обмена в предыдущем проходе

Слайд 10

Асимметрия метода:
«легкий» элемент в конце массива в случае просмотра
слева

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

А(1)

А(2)

А(3)

А(4)

А(5)

А(6)

А(7)

А(8)

И т.д., вплоть до А(1)

Улучшение: на каждом проходе чередовать направление
просмотра – «шейкерная» сортировка

Слайд 11

Исходный массив
Проход 1
45
А(1)
32
А(2)
5
А(3)
67
А(4)
98
А(5)
15
А(6)
34
А(7)
8
А(8)
32
А(1)
5
А(2)
45
А(3)
67
А(4)
15
А(5)
34
А(6)
8
А(7)
98
А(8)
Проход 2
5
А(1)
32
А(2)
8
А(3)
45
А(4)
67
А(5)
15
А(6)
34
А(7)
98
А(8)
Проход 3

Слайд 12

5
А(1)
8
А(2)
32
А(3)
45
А(4)
15
А(5)
34
А(6)
67
А(7)
98
А(8)
Проход 4
5
А(1)
8
А(2)
32
А(3)
15
А(4)
34
А(5)
45
А(6)
67
А(7)
98
А(8)
Проход 5
Обменов нет
Данную сортировку целесообразно применять, когда
известно, что массив

уже почти упорядочен.
Большого эффекта все улучшения дать не могут, т.к.
не влияют на число перестановок.

Слайд 13

Сортировка прямым выбором
Идея: массив делится на две части – левую, уже

отсортированную и правую, исходную; на каждом проходе в исходном массиве ищется минимальный элемент и меняется местами с первым в неотсортированной части, который
переходит в отсортированную часть.
Число проходов N-1
Число сравнений C=N(N-1)/2
Число обменов

Слайд 14

Исходный массив
Проход 1
45
А(1)
32
А(2)
5
А(3)
67
А(4)
98
А(5)
15
А(6)
34
А(7)
8
А(8)
Проход 2
5
А(1)
32
А(2)
45
А(3)
67
А(4)
98
А(5)
15
А(6)
34
А(7)
8
А(8)
Проход 3
5
А(1)
8
А(2)
45
А(3)
67
А(4)
98
А(5)
15
А(6)
34
А(7)
32
А(8)
Проход 4
5
А(1)
8
А(2)
15
А(3)
67
А(4)
98
А(5)
45
А(6)
34
А(7)
32
А(8)

Слайд 15

Проход 5
5
А(1)
8
А(2)
15
А(3)
32
А(4)
98
А(5)
45
А(6)
34
А(7)
67
А(8)
Проход 6
5
А(1)
8
А(2)
15
А(3)
32
А(4)
34
А(5)
45
А(6)
98
А(7)
67
А(8)
! Нет обмена
Проход 7
5
А(1)
8
А(2)
15
А(3)
32
А(4)
34
А(5)
45
А(6)
98
А(7)
67
А(8)
5
А(1)
8
А(2)
15
А(3)
32
А(4)
34
А(5)
45
А(6)
67
А(7)
98
А(8)
Число проходов – 7, число сравнений

– 28, число перестановок - 6

Слайд 16

Блок схема
i=1
i:N-1
н
>
к
≤
k=i, j=i+1
j:N
>
≤
A(j):A(k)
<
k=j
j=j+1
i=i+1
≥
k:i
>
Обмен
≤
I – номер прохода
k – индекс минимального
элемента в

проходе

Устойчивость
сортировки

Если k>i, значит был найден
минимальный элемент

Слайд 17

Сортировка прямого включения
Идея: массив делится на две части – левую, уже

отсортированную и правую, исходную; на каждом проходе, начиная с i=2 и увеличивая i каждый раз на 1, из исходной последовательности извлекается i-й элемент и вставляется на нужное место в отсортированную часть массива
Число проходов N-1
Число сравнений C=(N2+N-2)/4
Число обменов M=(N2+9N-10)/4

Слайд 18

Исходный массив
Проход 1
45
А(1)
32
А(2)
5
А(3)
67
А(4)
98
А(5)
15
А(6)
34
А(7)
8
А(8)
Проход 2
32
А(1)
45
А(2)
5
А(3)
67
А(4)
98
А(5)
15
А(6)
34
А(7)
8
А(8)
5
А(1)
32
А(2)
45
А(3)
67
А(4)
98
А(5)
15
А(6)
34
А(7)
8
А(8)
Проход 3
! Нет обмена
5
А(1)
32
А(2)
45
А(3)
67
А(4)
98
А(5)
15
А(6)
34
А(7)
8
А(8)
Проход 4
! Нет обмена

Слайд 19

5
А(1)
32
А(2)
45
А(3)
67
А(4)
98
А(5)
15
А(6)
34
А(7)
8
А(8)
Проход 5
Нет обмена
5
А(1)
15
А(2)
32
А(3)
45
А(4)
67
А(5)
98
А(6)
34
А(7)
8
А(8)
Нет обмена
Проход 6
5
А(1)
15
А(2)
32
А(3)
34
А(4)
45
А(5)
67
А(6)
98
А(7)
8
А(8)
Нет обмена
Проход 7
5
А(1)
8
А(2)
15
А(3)
32
А(4)
34
А(5)
45
А(6)
67
А(7)
98
А(8)
Число проходов – 7, число

сравнений – 21, число перестановок - 16

Метод плох из-за сдвижек целых групп элементов

Слайд 20

Сортировки: введение

Содержание

Сортировки: терминологияN – количество элементов массиваПроход – последовательный просмотр всех элементов

Эффективность сортировок: время, затрачиваемое на программирование; время, затрачиваемое на собственно сортировку;

Сортировка прямого обменаАлгоритм: на каждом проходе сравниваются элементы А(i) и А(i+1)

Исходный массивПроход 145А(1)32А(2)5А(3)67А(4)98А(5)15А(6)34А(7)8А(8)Проход 232А(1)5А(2)45А(3)67А(4)15А(5)34А(6)8А(7)98А(8)Нет обменаПроход 35А(1)32А(2)45А(3)15А(4)34А(5)8А(6)67А(7)98А(8)Нет обменаНет обмена

Блок-схемаi=1i:N-1н>к≤j=1j:N-1>≤A(j):A(j+1)>Обменj=j+1i=i+1≤Ввод и вывод массива не показаныВнешний цикл реализует N-1 проход,i –

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

Блок-схемаi=1,l=N-1,ne=N-1i:N-1AND ne<>0н>к≤j=1, ne=0j:l>≤A(j):A(j+1)>Обменj=j+1l=ne,i=i+1≤≤ne=jne (numb_exc) – если в предыдущем проходе не было

Асимметрия метода: «легкий» элемент в конце массива в случае просмотра слева

Исходный массивПроход 145А(1)32А(2)5А(3)67А(4)98А(5)15А(6)34А(7)8А(8)32А(1)5А(2)45А(3)67А(4)15А(5)34А(6)8А(7)98А(8)Проход 25А(1)32А(2)8А(3)45А(4)67А(5)15А(6)34А(7)98А(8)Проход 3

5А(1)8А(2)32А(3)45А(4)15А(5)34А(6)67А(7)98А(8)Проход 45А(1)8А(2)32А(3)15А(4)34А(5)45А(6)67А(7)98А(8)Проход 5Обменов нетДанную сортировку целесообразно применять, когда известно, что массив

Сортировка прямым выборомИдея: массив делится на две части – левую, уже

Блок схемаi=1i:N-1н>к≤k=i, j=i+1j:N>≤A(j):A(k)<k=jj=j+1i=i+1≥k:i>Обмен≤I – номер проходаk – индекс минимального элемента в

Сортировка прямого включенияИдея: массив делится на две части – левую, уже

i=2i:Nн>к≤x=A(i)j:2≤A(j):x<j=j-1i=i+1≥>Блок схемаj=iA(j)=A(j-1)A(j-1)=xНедостатки?

Похожие презентации

Сортировки: терминология
N – количество элементов массива
Проход – последовательный просмотр всех элементов

Эффективность сортировок:
время, затрачиваемое на программирование;
время, затрачиваемое на собственно сортировку;

Сортировка прямого обмена
Алгоритм: на каждом проходе сравниваются элементы А(i) и А(i+1)

Блок-схема
i=1
i:N-1
н
>
к
≤
j=1
j:N-1
>
≤
A(j):A(j+1)
>
Обмен
j=j+1
i=i+1
≤
Ввод и вывод массива не показаны
Внешний цикл реализует N-1 проход,
i –

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

Блок-схема
i=1,l=N-1,ne=N-1
i:N-1
AND
ne<>0
н
>
к
≤
j=1, ne=0
j:l
>
≤
A(j):A(j+1)
>
Обмен
j=j+1
l=ne,i=i+1
≤
≤
ne=j
ne (numb_exc) – если в предыдущем проходе не было

Асимметрия метода:
«легкий» элемент в конце массива в случае просмотра
слева

Исходный массив
Проход 1
45
А(1)
32
А(2)
5
А(3)
67
А(4)
98
А(5)
15
А(6)
34
А(7)
8
А(8)
32
А(1)
5
А(2)
45
А(3)
67
А(4)
15
А(5)
34
А(6)
8
А(7)
98
А(8)
Проход 2
5
А(1)
32
А(2)
8
А(3)
45
А(4)
67
А(5)
15
А(6)
34
А(7)
98
А(8)
Проход 3

Сортировка прямым выбором
Идея: массив делится на две части – левую, уже

Блок схема
i=1
i:N-1
н
>
к
≤
k=i, j=i+1
j:N
>
≤
A(j):A(k)
<
k=j
j=j+1
i=i+1
≥
k:i
>
Обмен
≤
I – номер прохода
k – индекс минимального
элемента в

Сортировка прямого включения
Идея: массив делится на две части – левую, уже

i=2
i:N
н
>
к
≤
x=A(i)
j:2
≤
A(j):x
<
j=j-1
i=i+1
≥
>
Блок схема
j=i
A(j)=A(j-1)
A(j-1)=x
Недостатки?