194 183 Одно из первых заданий программиста в любом языке программирования — разработка алгоритма сортировки массива. Большинство выбирает пузырьковый метод, то есть упорядочивание элементов после сравнения друг с другом. В Python это выглядит так:
nums = [4, 1, 6, 3, 2, 7, 8] n = 1 while n < len(nums): for i in range(len(nums) - n): if nums[i] > nums[i + 1]: nums[i], nums[i + 1] = nums[i + 1], nums[i] n += 1
входят в ТОП-30 с доходом
от 210 000 ₽/мес
Скачивайте и используйте уже сегодня:
Топ-30 самых востребованных и высокооплачиваемых профессий 2023
Поможет разобраться в актуальной ситуации на рынке труда
Подборка 50+ бесплатных нейросетей для упрощения работы и увеличения заработка
Только проверенные нейросети с доступом из России и свободным использованием
ТОП-100 площадок для поиска работы от GeekBrains
Список проверенных ресурсов реальных вакансий с доходом от 210 000 ₽
Однако на практике он неэффективен, так как предполагает многократное прохождение по всему массиву. Альтернативный метод, впоследствии получивший название «быстрая сортировка», изобрел информатик Чарльз Хоар в 1960.
Читайте также!
Он предполагает деление массива на две части, в одной из которых находятся элементы меньше определённого значения, в другой – больше или равные. Рассмотрим реализацию в Python быстрой сортировки Хоара.
def quicksort(nums): if len(nums) <= 1: return nums else: q = random.choice(nums) s_nums = [] m_nums = [] e_nums = [] for n in nums: if n < q: s_nums.append(n) elif n > q: m_nums.append(n) else: e_nums.append(n) return quicksort(s_nums) + e_nums + quicksort(m_nums)Скачать файл
В идеале, выбранный элемент должен быть медиальным, но для его поиска пришлось бы запускать ещё один цикл. Наша реализация на питоне сортировки Хоара использует случайный элемент, но она тоже не идеальна: в случае, если выбрано первое или последнее число, а массив отсортирован, то на питоне быстрая сортировка будет совпадать по эффективности с пузырьковой.
Впрочем, описанный алгоритм можно прокачать, сократив количество используемой памяти:
def quicksort(nums, fst, lst): if fst >= lst: return i, j = fst, lst pivot = nums[random.randint(fst, lst)] while i <= j: while nums[i] < pivot: i += 1 while nums[j] > pivot: j -= 1 if i <= j: nums[i], nums[j] = nums[j], nums[i] i, j = i + 1, j - 1 quicksort(nums, fst, j) quicksort(nums, i, lst)
на обучение «Python-разработчик» до 22 сентября
В этом случае вы используете память только для организации рекурсии и в Python быстрая сортировка становится по-настоящему «быстрой». В заключении темы опишем на питоне сортировку Хоара в функциональном виде:
def quicksort(nums): if len(nums) <= 1: return nums else: q = random.choice(nums) l_nums = [n for n in nums if n < q] e_nums = [q] * nums.count(q) b_nums = [n for n in nums if n > q] return quicksort(l_nums) + e_nums + quicksort(b_nums)
ТОП-100 площадок для поиска работы от GeekBrains
20 профессий 2023 года, с доходом от 150 000 рублей
Чек-лист «Как успешно пройти собеседование»
Также важно упомянуть, что в питоне методов сортировки чисел в массиве – множество, практически в каждой библиотеке, предназначенной для работы с числами. Однако знать и понимать описанные – важно не только для общего развития, но и для прохождения собеседований. Там это один из самых популярных вопросов.
0 
Разберем 11 самых важных жизненных вопросов
Только до 
Эксклюзивные лекции по основам программирования
