Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - Адитья Бхаргава

• даты путешествий;

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

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

Пример кода

Мы не будем приводить код сортировки музыкального списка, но написанный ниже код делает нечто очень похожее: он выполняет сортировку массива по возрастанию. Напишем функцию для поиска наименьшего элемента массива:

def findSmallest(arr):

  smallest = arr[0] Для хранения наименьшего значения

  smallest_index = 0 Для хранения индекса наименьшего значения

  for i in range(1, 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 = findSmallest(arr)  Находит наименьший элемент в массиве и добавляет его в новый массив

      newArr.append(arr.pop(smallest))

  return newArr

print selectionSort([5, 3, 6, 2, 10])

Шпаргалка

• Память компьютера напоминает огромный шкаф с ящиками.

• Если вам потребуется сохранить набор элементов, воспользуйтесь массивом или списком.

• В массиве все элементы хранятся в памяти рядом друг с другом.

• В списке элементы распределяются в произвольных местах памяти, при этом в одном элементе хранится адрес следующего элемента.

• Массивы обеспечивают быстрое чтение.

• Списки обеспечивают быструю вставку и выполнение.

• Все элементы массива должны быть однотипными (только целые числа, только вещественные числа и т.д.).

3. Рекурсия

В этой главе

• Вы узнаете, что такое рекурсия — метод программирования, используемый во многих алгоритмах. Это важная концепция для понимания дальнейших глав книги.

• Вы научитесь разбивать задачи на базовый и рекурсивный случай. В стратегии «разделяй и властвуй» (глава 4) эта простая концепция используется для решения более сложных задач.

Эта глава мне самому очень нравится, потому что в ней рассматривается рекурсия — элегантный метод решения задач. Рекурсия относится к числу моих любимых тем, но вызывает у людей противоречивые чувства. Они либо обожают ее, либо ненавидят, либо ненавидят, пока не полюбят через пару-тройку лет. Лично я отношусь к третьему лагерю. Чтобы вам было проще освоить эту тему, я дам несколько советов:

• Глава содержит множество примеров кода. Самостоятельно выполните этот код и посмотрите, как он работает.

• Мы будем рассматривать рекурсивные функции. Хотя бы один раз возьмите бумагу и карандаш и разберите, как работает рекурсивная функция: «Так, я передаю функции factorial значение 5, потом возвращаю управление и передаю значение 4 функции factorial, которая…» и т.д. Такой разбор поможет вам понять, как работает рекурсивная функция.

В этой главе также приводится большое количество псевдокода. Псевдокод представляет собой высокоуровневое описание решаемой задачи. Он записывается в форме, похожей на программный код, но в большей степени напоминает естественный язык.

Рекурсия

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

Бабушка говорит, что ключ к чемодану, скорее всего, лежит в коробке.

В коробке лежат другие коробки, а в них лежат маленькие коробочки. Ключ находится где-то там. Какой алгоритм поиска ключа предложите вы? Подумайте над алгоритмом, прежде чем продолжить чтение.

Одно из решений может выглядеть так:

1. Сложить все коробки в кучу.

2. Взять коробку и открыть.

3. Если внутри лежит коробка, добавить ее в кучу для последующего поиска.

4. Если внутри лежит ключ, поиск закончен!

5. Повторить.

Есть и альтернативное решение.

1. Просмотреть содержимое коробки.

2. Если вы найдете коробку, вернуться к шагу 1.

3. Если вы найдете ключ, поиск закончен!

Какое решение кажется вам более простым? Первое решение можно построить на цикле while. Пока куча коробок не пуста, взять очередную коробку и проверить ее содержимое:

def look_for_key(main_box):

  pile = main_box.make_a_pile_to_look_through()

  while pile is not empty:

    box = pile.grab_a_box()

    for item in box:

      if item.is_a_box():

        pile.append(item)

      elif item.is_a_key():

        print "found the key!"

Второй способ основан на рекурсии. Рекурсией называется вызов функцией самой себя. Второе решение на псевдокоде может выглядеть так:

def look_for_key(b ox):

  for item in box:

    if item.is_a_box():

      look_for_key(item)     Рекурсия!

    elif item.is_a_key():

      print "found the key!"

Оба решения делают одно и то же, но второе решение кажется мне более понятным. Рекурсия применяется тогда, когда решение становится более понятным. Применение рекурсии не ускоряет работу программы: более того, решение с циклами иногда работает быстрее. Мне нравится одна цитата Ли Колдуэлла с сайта Stack Overlow: «Циклы могут ускорить работу программы. Рекурсия может ускорить работу программиста. Выбирайте, что важнее в вашей