Page 58 - Bkhargava_-_Grokaem_algoritmy

Пример кода 57

Алгоритмы сортировки очень полезны. Например, теперь вы можете отсор­
тировать:

D имена в телефонной книге;

о даты путешествий;
D сообщения электронной почты (от новых к старым).

Алгоритм сортировки выбором легко объясняется, но медленно работает.
Быстрая сортировка - эффективный алгоритм сортировки, который выпол­
няется за время О(п log п). Но мы займемся этой темой в следующей главе!

Пример кода

Мы не будем приводить код сортировки музыкального списка, но напи­
санный ниже код делает нечто очень похожее: он выполняет сортировку
массива по возрастанию. Напишем функцию для поиска наименьшего
элемента массива:
def find Smallest(a r r):
smallest = arr[0] С· · · ··· Дпя хранения наименьwеrо значения
smallest_index = 0 с""""". Дпя хранения индекса наименьwеrо значения
for i in range(l, len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index

Теперь на основе этой функции можно написать функцию сортировки вы­
бором:

def selectionSort(arr): С· Сортирует массив
newArr = []
for i in range(len(arr)):
smallest = indSmallest(arr) С· Находит наименьший эпемент в массиве
newArr.append(arr.pop(smallest)) и добавnяет ero в новый массив
return newArr
print selectionSort([S, З, 6, 2, 10])

www.trk.kg