#8. Сортировка выбором | Алгоритмы на Python

Рассказывается об одном очень популярном алгоритме сортировки - сортировки выбором. Приведен пример его реализации на Python.
algorithm-sort-select.py: github.com/selfedu-rus/python...

[@user-no5hc7eo8t]

Спасибо, большое за ваше подробное объяснение, посмотрел несколько видео нечего не понял( Открыл Ваше, увидел первые 1:25 и сразу все дошло! ))

[@Vanya1977]

Спасибо за хорошее объяснение, но в python обмен значениями можно делать не использую 3-ю переменную t. Строки 17-19 можно заменить на a[i], a[p] = a[p], a[i] Хотя короткая версия имела бы такой алгоритм, не прибегая к дополнительным переменным for i in range(n-1): for j in range(i+1, n): if a[i] > a[j]: a[i], a[j] = a[j], a[i]

[@selfedu_rus]

да, все верно, ваш вариант куда лучше, спасибо!

[@tedi145]

Сижу ничего и понять не могу как бл оно работает(тупица походу)как только вижу твой вариант увидел сразу все понял (сижу офигеваю сам с себя)

[@FEOD0R]

В вашей версии реализован алгоритм

[@lokusok5080]

@@FEOD0R Сортировка пузырьком была бы такой: N = len(a) for j in range(1, N): for i in range(N-j): if a[i] > a[i+1]: a[i], a[i+1] = a[i+1], a[i]

[@alexandreabramtsev9160]

кроме как визуального эффекти ничего так не экономится. Операция a, b = b, a использует для обмена 2 переменных, вместо предложенной версии автора одной. Просто эти переменные неименованные, да и еще собраны в 3-ю переменную - кортеж Так вот - сначала создается котреж, а потом он распаковывается - процессорно тут куда намного больше телодвижений. Хотя визуально обмен значений через кортеж выглядит красивее

[@squalogender]

спасибо! все понятно объясняете

[@friend1cat]

Спасибо, Сергей.

[@user-vq2if9up5u]

спасибо за ваши видео

[@tsunamicross1061]

спасибо огромное, помогли разобраться!

[@user-yp6yv2ub2u]

Сергей, спасибо.

[@suiorarashbek]

лучшей сделай курс или по алгоритмам или продолжающий python , я бы с удовольствием училсябы у тебя.. спасибо за видео. ты крут чувак..

[@vyacheslavs5642]

Можно ещё добавить про сложность алгоритма. И сказать пару слов про О-большое и как оно определяется

[@user-ee1lx1pe7n]

Сложность данного алгоритма: O(n^2)

[@user-pl2rq4lg3j]

В блоке обмена значениями проверка if излишняя. И это, бро, ты бы называл переменные понятно, например temp_value и temp_index, а то я коло часа медитировал над кодом, что бы разобраться что к чему. А так спасибо за разбор

[@andyabsent4648]

все там правильно со вторым ифом, во избежание лишних замен, другой вопрос что можно было упростить код не используя такого кол-ва переменных во всех ифах и в первом ифе переопределять только указатели.

[@user-ep8mj5dd4c]

Здравствуйте пожалуйста снимите видео про двумерные массивы и сортировку. в интернете вообще мало информации. очень интересно и полезно! одномерные поняла теперь двумерные надо понять! Или хотябы общие алгоритмы как изменятся

[@vovadun]

Я чего то не понял или на видео переменной t присваивается j-й элемент, а в реализации кода i-й ?

[@alexd3596]

Не понятно зачем здесь заводить переменную m, каждый раз ей присваивать значение a[i] и сравнивать ? Лишняя операция. Если можно сразу писать: if a[i] > a[j]: ….

[@user-ww1ur8ww8r]

a = [-3,5,0,-8,1,10] for i in range (len(a)-1): for j in range (i+1, len(a)): if a[i] > a[j]: a[i], a [j] = a[j], a[i] print(a) Можно проще решить

[@nekiyzzz9656]

Но это не сортировка выбором, а пузырьковая

[@user-bw4xg8tb9r]

Сергей, реализация программы из книги "Грокаем алгоритмы" в два раза быстрее по скорости, почему не использовали её в данном уроке?

[@selfedu_rus]

Здесь учебная реализация. И кроме того эту книгу я не читал ) Надо будет посмотреть. Спасибо!

[@user-bw4xg8tb9r]

@@selfedu_rus да, посмотрите. Забавное пособие)) Но, к сожалению, там не так много алгоритмов разбирается, и они не самые сложные

[@selfedu_rus]

@@user-bw4xg8tb9r спасибо, уже скачал )

[@user-bw4xg8tb9r]

@@selfedu_rus вам спасибо за уроки)

[@ranli4998]

А если я допустим хочу с 5-го элемента по 9-ый в порядке возрастания сделать, как это написать?

[@higherupanddown8642]

Реализация программы плохая, но хорошее объяснение общего принципа

[@selfedu_rus]

я все расписал в учебных целях, не более того

[@Stanis_LOVE]

получается что даже последний условный оператор выполняет 3 действия которые можно было показать одним множественным присваиванием > a[p], a[i] = a[i], a[p]. Есть ли у этого метода какие то плюсы по сравнению с пузырьком? С первого взгляда это кажется усложнением пузырька, но я возможно чего то не понимаю еще.

[@selfedu_rus]

в общем, одно и то же, вычислительная сложность O(n^2) - медленный алгоритм

[@CCblLKA]

Какой алгоритм нахождения самого минимального j?

[@user-go2zu3zx7n]

вот самое обидное. Я прекрасно понимаю логику проведения. Но, блин, не могу понять, как это описано... Вот вообще...

[@firi4737]

А сам sort в питоне как сортирует?

[@selfedu_rus]

Определенно реализован один из быстрых алгоритмов, но какой именно не скажу.

[@higherupanddown8642]

Timsort

[@isok.atyrau]

А обмен значение можно делать без временный переменные???

[@selfedu_rus]

Нет, нужна одна или две переменные.

[@MuratAstrakhan]

Можно. i, j = j, i

[@suddenname]

@@MuratAstrakhan На самом же деле там используется временная переменная, просто она "скрыта" от глаз программиста

[@MuratAstrakhan]

@@suddenname нет там никаких скрытых переменных

[@suddenname]

@@MuratAstrakhan Проверил с помощью модуля dis и работает это так: 1) В стек помещаются две переменные, стоящие справа от знака равно 2) Два верхних элемента стека меняются местами (а вот это сделать без дополнительной переменной не выйдет) 3) Затем элементы по очереди снимаются со стека и присваиваются соответствующей переменной слева от знака равно Я написал вот такую функцию: def test(): a, b = 5, 6 a, b = b, a Затем импортировал модуль dis и выполнил функцию dis из него, передав функцию в качестве аргумента: import dis dis.dis(test) На выходе получил следующее: 2 0 LOAD_CONST 1 ((1, 5)) 2 UNPACK_SEQUENCE 2 4 STORE_FAST 0 (a) 6 STORE_FAST 1 (b) 3 8 LOAD_FAST 0 (a) 10 LOAD_FAST 1 (b) 12 ROT_TWO 14 STORE_FAST 1 (b) 16 STORE_FAST 0 (a) 18 LOAD_CONST 0 (None) 20 RETURN_VALUE Слева указан номер строки. Вторая строка нас не интересует, поэтому перейдем к третьей, где и увидим описанный выше алгоритм

[@mao13132]

Почему данный алгоритм не сортирует если есть дубли? a = [10, 21, 1, -10, 10, 0, -2]

[@selfedu_rus]

отсортировал, получилось: [-10, -2, 0, 1, 10, 10, 21]

[@mao13132]

Разобрался. блок с последним if сдвинул и он зашёл в зону видимость цикла. Спасибо!

[@ez9723]

def s_sort(a): i = 0 j = 1 while j < len(a): element_index = a[j: len(a)].index(min(a[j: len(a)])) + j if a[element_index] < a[i]: a[i], a[element_index] = a[element_index], a[i] i += 1 j += 1 return a Вот моя реализация с использованием срезов и встроенной функции min

[@falcon4687]

Говнокод если честно

[@qmv774]

Код на Rust: fn selection_sort(arr: &mut [i32]) { let len = arr.len(); for i in 0..len { let mut min_index = i; for j in (i + 1)..len { if arr[j] < arr[min_index] { min_index = j; } } if i != min_index { arr.swap(i,min_index); } } } fn main() { let mut arr = [-3,5,0,-8,1,10]; selection_sort(&mut arr); arr.iter().for_each(|x| println!("{x}")); }