• Познакомьтесь с пентестом веб-приложений на практике в нашем новом бесплатном курсе

    «Анализ защищенности веб-приложений»

    🔥 Записаться бесплатно!

  • CTF с учебными материалами Codeby Games

    Обучение кибербезопасности в игровой форме. Более 200 заданий по Active Directory, OSINT, PWN, Веб, Стеганографии, Реверс-инжинирингу, Форензике и Криптографии. Школа CTF с бесплатными курсами по всем категориям.

Статья Алгоритмы сортировки и их реализация на 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
522
1 087
BIT
0
На собеседованиях до сих задают интересно сортировку методом пузырька, в одно время он топ был ))
 
В

Ванек

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

explorer

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

SooLFaa

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

explorer

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

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

a1.png


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

11.png


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

12.png


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

13.png
 

zol

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

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

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

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

XaRoN_1337

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

Обучение наступательной кибербезопасности в игровой форме. Начать игру!