Быстрая сортировка в Python

Одно из первых заданий программиста в любом языке программирования — разработка алгоритма сортировки массива. Большинство выбирает пузырьковый метод, то есть упорядочивание элементов после сравнения друг с другом. В 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

Однако на практике он неэффективен, так как предполагает многократное прохождение по всему массиву. Альтернативный метод, впоследствии получивший название «быстрая сортировка», изобрел информатик Чарльз Хоар в 1960.

Читайте также!

Циклы в Python: виды и примеры

Подробнее

Он предполагает деление массива на две части, в одной из которых находятся элементы меньше определённого значения, в другой – больше или равные.  Рассмотрим реализацию в 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)

Узнай, какие ИТ - профессии
входят в ТОП-30 с доходом
от 210 000 ₽/мес

Павел Симонов

Исполнительный директор Geekbrains

Команда GeekBrains совместно с международными специалистами по развитию карьеры подготовили материалы, которые помогут вам начать путь к профессии мечты.

Подборка содержит только самые востребованные и высокооплачиваемые специальности и направления в IT-сфере. 86% наших учеников с помощью данных материалов определились с карьерной целью на ближайшее будущее!

Скачивайте и используйте уже сегодня:

Павел Симонов

Исполнительный директор Geekbrains

Топ-30 самых востребованных и высокооплачиваемых профессий 2023

Поможет разобраться в актуальной ситуации на рынке труда

Подборка 50+ бесплатных нейросетей для упрощения работы и увеличения заработка

Только проверенные нейросети с доступом из России и свободным использованием

ТОП-100 площадок для поиска работы от GeekBrains

Список проверенных ресурсов реальных вакансий с доходом от 210 000 ₽

Получить подборку бесплатно

pdf 3,7mb

doc 1,7mb

Уже скачали 32510

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

Только до 30.12

Скачай подборку материалов, чтобы гарантированно найти работу в IT за 14 дней

Список документов:

ТОП-100 площадок для поиска работы от GeekBrains

20 профессий 2023 года, с доходом от 150 000 рублей

Чек-лист «Как успешно пройти собеседование»

Чтобы получить файл, укажите e-mail:

Введите e-mail, чтобы получить доступ к документам

Подтвердите, что вы не робот,
указав номер телефона:

Введите телефон, чтобы получить доступ к документам

Скачать подборку бесплатно pdf 2,5mb

Уже скачали 52300

Я подтверждаю согласие на обработку персональных данных.

Впрочем, описанный алгоритм можно прокачать, сократив количество используемой памяти:

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 быстрая сортировка становится по-настоящему «быстрой». В заключении темы опишем на питоне сортировку Хоара в функциональном виде:

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)

Дарим скидку от 60%
на обучение «Python-разработчик» до 29 декабря

Уже через 9 месяцев сможете устроиться на работу с доходом от 150 000 рублей

Забронировать скидку

Автор статьи:

Илья Бубнов