Для студентов по предмету Системное программированиеЭффективные методы сортировок, бинарный поискЭффективные методы сортировок, бинарный поиск
2023-03-092023-03-09СтудИзба
Задача: Эффективные методы сортировок, бинарный поиск
Описание
Эффективные сортировки, бинарный поиск
1 A. Сортировка слиянием
Разбор:
В этой задаче требовалось реализовать алгоритм сортировки слиянием. Используя возможности языка Python, можно было написать меньше кода при помощи "срезов". Однако, срезы требуют дополнительной памяти и времени на копирование подмассива, поэтому наиболее эффективным решением является разделение не всего массива пополам, а только индексов, которые передаются ниже в рекурсию.
Асимптотика решения: O(N × log N).
Решение:
def merge_sort (a , l , r) :
if r - l < 2:
return 0
m = (r + l) // 2
merge_sort (a , l , m)
merge_sort (a , m , r)
merge (a , l , m , r)
def merge (a , l , m , r):
l1 , r1 = l , m
l2 , r2 = m , r
result = []
while l1 < r1 or l2 < r2 :
if l1 < r1 and l2 < r2 :
if a[ l1 ] < a [ l2 ]:
result . append ( a[ l1 ])
l1 += 1
else :
result . append ( a[ l2 ])
l2 += 1
elif l1 >= r1 and l2 < r2 :
result . append ( a[ l2 ])
l2 += 1
elif l2 >= r2 and l1 < r1 :
result . append ( a[ l1 ])
l1 += 1
for i in range (l , r ):
a[i ] = result [ i - l]
n = int ( input () )
x = list ( map (int , input () . split () ) )
merge_sort (x , 0, n)
print (’ ’. join ( map (str , x)) )Показать/скрыть дополнительное описание
1 A. Сортировка слиянием
Разбор:
В этой задаче требовалось реализовать алгоритм сортировки слиянием. Используя возможности языка Python, можно было написать меньше кода при помощи "срезов". Однако, срезы требуют дополнительной памяти и времени на копирование подмассива, поэтому наиболее эффективным решением является разделение не всего массива пополам, а только индексов, которые передаются ниже в рекурсию.
Асимптотика решения: O(N × log N).
Решение:
def merge_sort (a , l , r) :
if r - l < 2:
return 0
m = (r + l) // 2
merge_sort (a , l , m)
merge_sort (a , m , r)
merge (a , l , m , r)
def merge (a , l , m , r):
l1 , r1 = l , m
l2 , r2 = m , r
result = []
while l1 < r1 or l2 < r2 :
if l1 < r1 and l2 < r2 :
if a[ l1 ] < a [ l2 ]:
result . append ( a[ l1 ])
l1 += 1
else :
result . append ( a[ l2 ])
l2 += 1
elif l1 >= r1 and l2 < r2 :
result . append ( a[ l2 ])
l2 += 1
elif l2 >= r2 and l1 < r1 :
result . append ( a[ l1 ])
l1 += 1
for i in range (l , r ):
a[i ] = result [ i - l]
n = int ( input () )
x = list ( map (int , input () . split () ) )
merge_sort (x , 0, n)
print (’ ’. join ( map (str , x)) )Показать/скрыть дополнительное описание
Эффективные методы сортировок, бинарный поиск, сортировка слиянием, двоичный поиск, сортировка подсчётом. Анализ данных. .
Характеристики решённой задачи
Предмет
Учебное заведение
Неизвестно
Учебная пора
Просмотров
1
Покупок
0
Качество
Идеальное компьютерное
Размер
188,51 Kb
Список файлов
- Эффективные методы сортировки, бинарный поиск.pdf 188,51 Kb
QuadD4rv1n7
QuadD4rv1n7
09 марта в 22:17
