Статья Алгоритмы сортировки и их реализация на Python

Сегодня расскажу про методы сортировки
В данной статье пойдет речь про:
  • Сортировка выбором
  • Сортировка вставками
  • Сортировка “Методом пузырька”
  • Сортировка Шелла
  • Быстрая сортировка
Python:
def choise_sort(data):
    for i, e in enumerate(data):
        min_el = min(range(i, len(data)), key=data.__getitem__)
        data[i], data[min_el] = data[min_el], e
    return data
Python:
def insertion_sort(data):
    for i in range(len(data)):
        j = i - 1
        key = data[i]
        while data[j] > key and j >= 0:
            data[j + 1] = data[j]
            j -= 1
            data[j + 1] = key
    return data
Python:
def buble_sort(my_list):
    for i in range(len(my_list)):
        for in_element in range(1, len(my_list)):
            if my_list[in_element] < my_list[in_element - 1]:
                my_list[in_element], my_list[in_element - 1] = my_list[in_element - 1], my_list[in_element]
    return my_list
Python:
def quick_sort(data):
    if len(data) <= 1:
        return data
    q = random.choice(data)
    l_data = [n for n in data if n < q]
    e_data = [q] * data.count(q)
    r_data = [n for n in data if n > q]
    return quick_sort(l_data) + e_data + quick_sort(r_data)
Если у кого возник вопрос какая сортировка самая быстрая - это надо обращаться к понятию о сложности алгоритма.
По простому для коллекций элементов количеством меньше чем 1000 лучшим образом отрабатывают как не странно пузырьковая сортировка и сортировка вставками, а для коллекций с количеством элементов > 1000 наилучшим образом отрабатывают сортировка выбором и быстрая.
А пока - из предложенных быстрая сортировка показывает себя наилучшим образом.
В пайтоне с коробки реализованы сортировки для коллекций разных размеров:

для малых - insertion sort
для больших - merge sort

Если было полезно или интересно ставь лайк!)
Еще нашел прикольный сайт с демонстрацией алгоритмов
 
Последнее редактирование модератором:
Y

yagema

Как раз изучаю данный материал, огромное спасибо.

Сайт наглядно показывающий различия между сортировками с разными входными данными.
 

r0hack

DAG
Gold Team
29.09.2017
521
1 081
На собеседованиях до сих задают интересно сортировку методом пузырька, в одно время он топ был ))
 
В

Ванек

Вот это
Python:
for i in range(len(array))
вы явно принесли из С++. В Пайтоне делается проще:
Python:
for i in array
 

SooLFaa

Platinum
15.07.2016
899
1 567
Курсивить много текста не надо. Исправил и выложил
 
  • Нравится
Реакции: komodikus

explorer

Platinum
05.08.2018
1 065
2 426
Курсивить много текста не надо. Исправил и выложил
SoolFaa, не нужно было обновлять с кривым кодом. Автор выложил код полностью без отступов!!! Ещё нету импорта random в последнем коде. Если кто-то скопипастит, то увидит, что кода получились нерабочие. Кто понимает, исправит, а совсем начинающие запутаются. У автора вышло из серии "хотел как лучше, а получилось как всегда".
 
  • Нравится
Реакции: The Codeby

SooLFaa

Platinum
15.07.2016
899
1 567
SoolFaa, не нужно было обновлять с кривым кодом. Автор выложил код полностью без отступов!!! Ещё нету импорта random в последнем коде. Если кто-то скопипастит, то увидит, что кода получились нерабочие. Кто понимает, исправит, а совсем начинающие запутаются. У автора вышло из серии "хотел как лучше, а получилось как всегда".
Твоя правда. Исправь плиз.
 

explorer

Platinum
05.08.2018
1 065
2 426
Твоя правда. Исправь плиз.
Исправил. Автор только функции сделал, опять же не наглядно, новичку непонятно. Я не поленился поправить код и сделать скрины с примером, как это должно работать.

Сортировка выбором

a1.png


Сортировка вставками

11.png


Сортировка пузырьком

12.png


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

13.png
 

zol

Member
26.11.2019
8
0
Я так понимаю, материал для новичков, как в языке, так и в теории алгоритмов.
Прошу внимания на ресурсы с визуализацией алгоритмов. Не стоит ограничиваться ресурсами, которые оставил ТС :D

Algomation - базовые структуры данных, сортировки и нехитрые алгоритмы, вроде бинарного поиска.
Радужная визуализация - те же алгоритмы сортировки, но вместо чисел используем цвета (Версия для людей, с ограничениями восприятия цвета)

вы явно принесли из С++. В Пайтоне делается проще:
Действительно, мы можем делать так в Python. Проблема только в том, что переменная итерации read-only, мы не можем менять состояния объекта, так что такие претензии не всегда корректны, увы. У автора все довольно "питонично", кстати.

А ещё в python есть свои быстрые функции сортировки sort() и sorted()
А вообще, эти две функции (а точнее, метод списка и функция) работают, скорее всего, оптимизированнее любого на коленке написанного алгоритма. Понимание алгоритмов нужно только для собеседований и когда данных очень много (больше, чем размер оперативной памяти, например)
 

XaRoN_1337

Green Team
08.10.2020
27
5
Хорошая статья. Для тех кто хочет изучить алгоритмы с 0, лучше всего, как по-мне, будет книга "Грокаем алгоритмы", там как раз используется python.
 
Мы в соцсетях:

1 августа стартует курс «Основы программирования на Python» от команды The Codeby

Курс будет начинаться с полного нуля, то есть начальные знания по Python не нужны. Длительность обучения 2 месяца. Учащиеся получат методички, видео лекции и домашние задания. Много практики. Постоянная обратная связь с кураторами, которые помогут с решением возникших проблем.

Запись на курс до 10 августа. Подробнее ...