Is selection sort efficient?

Question

Algorithms

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

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

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))       # тестируем , все работает

The code is given, which was slightly altered, but the fact is the same as from the book.
Selection sort is touted as an efficient sort.
The question is, how can it be efficient in terms of resource costs, if when you start the first function, it automatically starts the second one?

Answer 1

There is no single answer to your question in this formulation.
On large arrays, selection sort will be extremely inefficient, because it has quadratic complexity. There are more efficient sorts - merge, quicksort, radixsort, etc.
On small arrays, selection sort can be one of the most efficient if looped in the right direction and is very cache friendly. Another difference with selection sort is that there is very little data movement. Insertion sort, for example, will shovel the entire array at each iteration.
Calling one function from another is not at all an indicator of the effectiveness of the algorithm (or its implementation).
There is not even recursion here - you can expand the function call if you don’t like it so much (just insert its code with minor edits instead of calling), but this will not greatly improve this sorting.
The bigger problem is that instead of sorting in place, you create a new array. At the same time, at each iteration, you have a lot of data moving, due to the removal of an element from the array.
If instead the minimum element is put in its place, it will be much faster. In this case, instead of removing an element from the array, you need to remember how many elements you have already put in their place. The search for the minimum each time start from the next position.