Эффективна ли сортировка выбором?

Question

[Робин Алиханов]

# сортировка наименьшего элемента массива

#Определяем наименьшщий элемент массива
#и возвращаем его индекс

array_example = [100,25,89,63]

def find_small(arr):                
    small = arr[0]                  # кладем в переменную значение нулевого элемента массива
    count = 0                       # переменная в которой будет хран наименьший элемент массива
    size = len(arr)                 # узнаем размер массива
    i = 1                           # счетчик с которого начнем обход массива
    while i < size:                 # пока счетчик не равен длине массива обходим его
        if arr[i] < small:          # если 1 элемент массива меньше 0 элемента массива 
            small = arr[i]          # то в 0 элемент кладем первый
            count = i               # и значение счетчика записываем в спец переменную
        i = i + 1                   # счетчик увеличиваем на единицу
    return count                    # возвращаем индекс минимального элемента массива

print(find_small(array_example))   # проверка работы кода


# Функция сортировки выбором

def select_sort(arr):                   #
    new_arr = []                        # создаем массив новый куда будем класть отсоортированные значения
    for i in range(len(arr)):           # в цикле проходимся по каждому элементу массива
        small = find_small(arr)         # узнаем порядковый номер наименьшего элемента массива
        new_arr.append(arr.pop(small))  # в новый массив добавляем значние наименьшего элемента и одновременно удаляем
    return new_arr                      # это значние со старого массива , возвращаем новый отсортированный массив

print(select_sort(array_example))       # тестируем , все работает

Дан код, который немножко переделал, но факту такой же как с книги.
Сортировка с выбором преподносится ,как эффективная сортировка.

Вопрос, как она может быть эффективна в плане затраты ресурсов, если при запуске первой функции, она автоматически запускает вторую?

Answer 1

[Wataru]

Однозначного ответа на Ваш вопрос в такой формулировке нет.

На больших массивах сортировка выбором будет крайне не эффективна, потому что она имеет квадратичную сложность. Есть более эффективные сортировки - слиянием, quicksort, radixsort, и т.д.

На маленьких массивах сортировка выбором может быть одной из самых эффективных, если в удачном направлении пустить циклы и оказаться очень дружелюбными к кэшу процессора. Еще одним отличием сортировки выбора является очень мало перемещений данных. Сортировка вставкой, например, будет на каждой итерации перелопачивать весь массив.

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

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

Если вместо этого минимальный элемент ставить на свое место, то будет гораздо быстрее. При этом, вместо удаления элемента из массива, надо помнить сколько элементов Вы уже на свое место поставили. Поиск минимального каждый раз начинайте со следующей позиции.