СДЕЛАЙТЕ СВОИ УРОКИ ЕЩЁ ЭФФЕКТИВНЕЕ, А ЖИЗНЬ СВОБОДНЕЕ

Благодаря готовым учебным материалам для работы в классе и дистанционно

Скидки до 50 % на комплекты
только до 20.07.2025

Готовые ключевые этапы урока всегда будут у вас под рукой

Организационный момент

Проверка знаний

Объяснение материала

Закрепление изученного

Итоги урока

Презентация "Сортировка списка" (10 класс углубленный уровень)

Категория: Информатика

Нажмите, чтобы узнать подробности

Презентация "Сортировка списка" (10 класс углубленный уровень) содержит методы сортировки списка

Просмотр содержимого документа
«Презентация "Сортировка списка" (10 класс углубленный уровень)»

Сортировка списка. Информатика 10 класс (профильный уровень) учитель МБОУ СОШ с.Тербуны Болгова Н.А.

Сортировка списка.

Информатика 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  (с) Болгова Н.А.

Тема: « Сортировка списка »

Методы сортировки:

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

Сортировкаэто упорядочивание элементов массива по заданному условию

  • по возрастанию, убыванию, последней цифре, по алфавиту, …
  • Алгоритмы:

Простые ( метод пузырька, метод выбора)

сложные, но эффективные ( быстрая сортировка)

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 (с) Болгова Н.А.

Метод выбора

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 (с) Болгова Н.А.

Сортировка слиянием

Или ввод списка с клавиатуры + сортировка методом 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 (с) Болгова Н.А.

Основная программа:

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 (с) Болгова Н.А.

Сортировки в 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  (с) Болгова Н.А.

Литература:

  • Поляков К.Ю., Еремин Е.А. «Информатика 10 класс :учебник базового и углубленного уровней»: Москва, АО «Просвещение», 2023 г.
  • Авторская мастерская Полякова К.Ю. [ https://kpolyakov.spb.ru/school/basebook.htm]

2020

(с) Болгова Н.А.


Скачать

Рекомендуем курсы ПК и ППК для учителей

Вебинар для учителей

Свидетельство об участии БЕСПЛАТНО!