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

komodikus

komodikus

Happy New Year
06.01.2017
39
69
Сегодня расскажу про методы сортировки
В данной статье пойдет речь про:
  • Сортировка выбором
  • Сортировка вставками
  • Сортировка “Методом пузырька”
  • Сортировка Шелла
  • Быстрая сортировка
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

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

IioS

Well-known member
09.06.2017
244
489
Хорошая статья, по нужному материалу. Видео которое визуально демонстрирует разные типы сортировк
 
Y

yagema

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

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

r0hack

DAG
Gold Team
29.09.2017
481
901
На собеседованиях до сих задают интересно сортировку методом пузырька, в одно время он топ был ))
 
Dr.Lafa

Dr.Lafa

Mod. Hardware
Gold Team
30.12.2016
510
1 036
А ещё в python есть свои быстрые функции сортировки sort() и sorted()
 
  • Нравится
Реакции: G0p43R и mrtyrel
В

Ванек

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

SooLFaa

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

explorer

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

SooLFaa

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

explorer

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

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

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


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

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


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

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


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

Алгоритмы сортировки и их реализация на Python
 
  • Нравится
Реакции: The Codeby и 1984
zol

zol

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

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

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

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