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

Идея быстрой сортировки была придумана информатиком Чарльзом Хоаром в 1960 году. Рассмотрим её преимущества над пузырьковой сортировкой и реализуем алгоритм в Python.
06 декабря 2017326451Илья Бубнов1628313

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

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

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)

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

Новые комментарии