#8. Сортировка выбором | Алгоритмы на Python
Vložit
- čas přidán 27. 02. 2021
- Рассказывается об одном очень популярном алгоритме сортировки - сортировки выбором. Приведен пример его реализации на Python.
algorithm-sort-select.py: github.com/selfedu-rus/python...
Спасибо за хорошее объяснение, но в 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]
да, все верно, ваш вариант куда лучше, спасибо!
Сижу ничего и понять не могу как бл оно работает(тупица походу)как только вижу твой вариант увидел сразу все понял (сижу офигеваю сам с себя)
В вашей версии реализован алгоритм
@@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]
кроме как визуального эффекти ничего так не экономится. Операция a, b = b, a использует для обмена 2 переменных, вместо предложенной версии автора одной. Просто эти переменные неименованные, да и еще собраны в 3-ю переменную - кортеж Так вот - сначала создается котреж, а потом он распаковывается - процессорно тут куда намного больше телодвижений. Хотя визуально обмен значений через кортеж выглядит красивее
Спасибо, большое за ваше подробное объяснение, посмотрел несколько видео нечего не понял( Открыл Ваше, увидел первые 1:25 и сразу все дошло! ))
спасибо! все понятно объясняете
Спасибо, Сергей.
спасибо за ваши видео
Сергей, спасибо.
спасибо огромное, помогли разобраться!
лучшей сделай курс или по алгоритмам или продолжающий python , я бы с удовольствием училсябы у тебя.. спасибо за видео. ты крут чувак..
Здравствуйте пожалуйста снимите видео про двумерные массивы и сортировку. в интернете вообще мало информации. очень интересно и полезно! одномерные поняла теперь двумерные надо понять! Или хотябы общие алгоритмы как изменятся
Я чего то не понял или на видео переменной t присваивается j-й элемент, а в реализации кода i-й ?
В блоке обмена значениями проверка if излишняя. И это, бро, ты бы называл переменные понятно, например temp_value и temp_index, а то я коло часа медитировал над кодом, что бы разобраться что к чему. А так спасибо за разбор
все там правильно со вторым ифом, во избежание лишних замен, другой вопрос что можно было упростить код не используя такого кол-ва переменных во всех ифах и в первом ифе переопределять только указатели.
А если я допустим хочу с 5-го элемента по 9-ый в порядке возрастания сделать, как это написать?
Можно ещё добавить про сложность алгоритма. И сказать пару слов про О-большое и как оно определяется
Сложность данного алгоритма: O(n^2)
Какой алгоритм нахождения самого минимального j?
Не понятно зачем здесь заводить переменную m, каждый раз ей присваивать значение a[i] и сравнивать ? Лишняя операция. Если можно сразу писать: if a[i] > a[j]: ….
Сергей, реализация программы из книги "Грокаем алгоритмы" в два раза быстрее по скорости, почему не использовали её в данном уроке?
Здесь учебная реализация. И кроме того эту книгу я не читал ) Надо будет посмотреть. Спасибо!
@@selfedu_rus да, посмотрите. Забавное пособие)) Но, к сожалению, там не так много алгоритмов разбирается, и они не самые сложные
@@user-bw4xg8tb9r спасибо, уже скачал )
@@selfedu_rus вам спасибо за уроки)
получается что даже последний условный оператор выполняет 3 действия которые можно было показать одним множественным присваиванием > a[p], a[i] = a[i], a[p]. Есть ли у этого метода какие то плюсы по сравнению с пузырьком? С первого взгляда это кажется усложнением пузырька, но я возможно чего то не понимаю еще.
в общем, одно и то же, вычислительная сложность O(n^2) - медленный алгоритм
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)
Можно проще решить
Но это не сортировка выбором, а пузырьковая
А сам sort в питоне как сортирует?
Определенно реализован один из быстрых алгоритмов, но какой именно не скажу.
Timsort
А обмен значение можно делать без временный переменные???
Нет, нужна одна или две переменные.
Можно. i, j = j, i
@@suddenname нет там никаких скрытых переменных
@@MuratAstrakhan Это и есть через две временные переменные
@@suddenname super
вот самое обидное. Я прекрасно понимаю логику проведения. Но, блин, не могу понять, как это описано... Вот вообще...
Реализация программы плохая, но хорошее объяснение общего принципа
я все расписал в учебных целях, не более того
Почему данный алгоритм не сортирует если есть дубли? a = [10, 21, 1, -10, 10, 0, -2]
отсортировал, получилось: [-10, -2, 0, 1, 10, 10, 21]
Разобрался. блок с последним if сдвинул и он зашёл в зону видимость цикла. Спасибо!
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
Говнокод если честно
Код на 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}"));
}