Сортировка списка.
Информатика 10 класс
(профильный уровень)
учитель МБОУ СОШ с.Тербуны
Болгова Н.А.
Тема: « Сортировка списка »
Методы сортировки:
a. sort () – сортировка списка по возрастанию
a. sort (reverse=True) сортировка списка по убыванию
a = [11, 14, 7, 13]
Вывод: [7, 11, 13, 14]
a = [11, 14, 7, 13]
Вывод: [14, 13, 11, 7]
2020
(с) Болгова Н.А.
Сортировка – это упорядочивание элементов массива по заданному условию
- по возрастанию, убыванию, последней цифре, по алфавиту, …
Простые ( метод пузырька, метод выбора)
сложные, но эффективные ( быстрая сортировка)
N
1000
Метод пузырька
5000
0,08 с
Метод выбора
15000
1,8 с
0,05 с
Сортировка слиянием
17,3 с
0,006 с
Быстрая сортировка
1,3 с
11,2 с
0,033 с
0,002 с
0,108 с
0,006 с
0,019 с
(с) Болгова Н.А.
2020
a[j + 1]: a[j], a[j + 1] = a[j + 1], a[j] print(a) 2020 (с) Болгова Н.А. " width="640"
Сортировка «пузырьком» по возрастанию:
n = int(input( ' введите кол-во элементов- ' )) a = [int(input()) for i in range(n)] for i in range(n - 1):
for j in range(n – 1 - i ):
if a[j] a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
print(a)
2020
(с) Болгова Н.А.
Метод выбора
n = int(input( 'введите кол-во элементов-' )) a = [int(input()) for i in range(n)] for i in range(n - 1):
nMin = i
for j in range(i+1,n):
if a[j]
nMin = j
if i != nMin:
a[i], a[nMin] = a[nMin], a [i]
print(a)
Max элемент помещается в конец списка
2020
(с) Болгова Н.А.
Сортировка слиянием
Или ввод списка с клавиатуры + сортировка методом A.sort()
2020
(с) Болгова Н.А.
= X 2020 (с) Болгова Н.А. " width="640"
Быстрая сортировка
1) выбрать «средний» элемент массива X
2 ) переставить элементы так:
(при сортировке элементы остаются в своей части!
3) Шаг 2 повторяется
X
a[i]
a[i] = X
2020
(с) Болгова Н.А.
= X ( должен стоять справа ), уменьшая R , найти первый элемент A[R] X ( должен стоять слева ) если L то меняем местами A[L] и A[R], далее к п3, или стоп . 78 L 6 82 67 55 44 34 R 34 6 82 L 67 55 44 R 78 34 6 44 67 55 L R 82 78 (с) Болгова Н.А. 2020 " width="640"
Быстрая сортировка
- выбрать середину ( X=67 )
- установить L = 0 , R = N-1
- увеличивая L , найти первый элемент A[L] , который = X ( должен стоять справа ), уменьшая R , найти первый элемент A[R] X ( должен стоять слева )
- если L то меняем местами A[L] и A[R], далее к п3, или стоп .
78
L
6
82
67
55
44
34
R
34
6
82
L
67
55
44
R
78
34
6
44
67
55
L
R
82
78
(с) Болгова Н.А.
2020
R : разделение закончено 34 6 44 67 55 L 82 R 78 34 6 44 55 R 67 L 82 78 Данный метод «Разделяй и властвуй!» лежит в основе рекурсии! 2020 (с) Болгова Н.А. " width="640"
Быстрая сортировка
4) если L то меняем местами A[L] и A[R], далее к п3, или стоп .
5) L R : разделение закончено
34
6
44
67
55
L
82
R
78
34
6
44
55
R
67
L
82
78
Данный метод «Разделяй и властвуй!» лежит в основе рекурсии!
2020
(с) Болгова Н.А.
= end: return L = start # левая граница R = end # правая граница x = a[(L + R) // 2] # медиана while L while a[L] L += 1 while a[R] x: R -= 1 if L a[L], a[R] = a[R], a[L] # меняем местами ……… # делим на 2 части список 2020 (с) Болгова Н.А. " width="640"
def a_sort(a, start, end): if start = end: return L = start # левая граница R = end # правая граница x = a[(L + R) // 2] # медиана while L while a[L] L += 1 while a[R] x: R -= 1 if L a[L], a[R] = a[R], a[L] # меняем местами ………
# делим на 2 части список
2020
(с) Болгова Н.А.
= end: return L = start R = end x = a[(L + R) // 2] while L # делим на 2 части while a[L] L += 1 while a[R] x: R - = 1 if L a[L], a[R] = a[R], a[L] # меняем местами L += 1 R - = 1 a_sort(a, start, R) # рекурсия вызывает сама себя a_sort(a, L, end) 2020 (с) Болгова Н.А. " width="640"
def a_sort(a, start, end): if start = end: return L = start R = end x = a[(L + R) // 2] while L # делим на 2 части while a[L] L += 1 while a[R] x: R - = 1 if L a[L], a[R] = a[R], a[L] # меняем местами L += 1 R - = 1 a_sort(a, start, R) # рекурсия вызывает сама себя a_sort(a, L, end)
2020
(с) Болгова Н.А.
Основная программа:
n = int (input( )) a = [int(input()) for i in range(n)] a_sort (a, 0, n - 1) # массив , начало , конец сортировки print ( 'sort-' , a)
2020
(с) Болгова Н.А.
Сортировки в python
По возрастанию :
A. sort ()
B = sorted (A)
По убыванию :
A. sort (reverse= True )
B = sorted (A,reverse = True )
По последней цифре (вариант 1 :
def A_sort(n):
return n % 10
B = sorted (A, key = A_sort )
def A_sort(n):
return n % 10
A. sort (key = A_sort)
Вариант 2 :
B = sorted (A, key = lambda x:x % 10 )
A. sort ( key = lambda x:x % 10 )
«лямбда»-функция
(функция без имени)
2020
(с) Болгова Н.А.
Литература:
- Поляков К.Ю., Еремин Е.А. «Информатика 10 класс :учебник базового и углубленного уровней»: Москва, АО «Просвещение», 2023 г.
- Авторская мастерская Полякова К.Ю. [ https://kpolyakov.spb.ru/school/basebook.htm]
2020
(с) Болгова Н.А.