Простой алгоритм сортировки списка и линейный поиск на Python

Если бы вам дали лист бумаги со списком из 1000 имен, и вы захотели бы найти конкретное имя, но список не был бы отсортирован ни по какому признаку (например, в алфавитном порядке), это было бы очень тяжело, не так ли?

Сортировка этого списка, даже если она может занять много времени, облегчает поиск нужного имени.

Поэтому упорядоченность вещей – это естественное желание, которое есть у каждого человека. А поиск в таком списке требует меньше усилий, чем, очевидно, в неупорядоченном.

Говоря компьютерным языком, списки, по которым нам приходится искать, часто бывают гигантскими. И это может повлиять на производительность даже на быстрых компьютерах.

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

В этой статье я опишу простой алгоритм сортировки и алгоритм линейного поиска.

Алгоритм сортировки

Данный алгоритм сортировки основан на последовательном выборе минимального или максимального значения.

Предположим, у нас есть список, который мы хотим отсортировать в порядке возрастания (от наименьшего к наибольшему). Самый маленький элемент будет первым в списке, а самый большой элемент – последним в списке.

Допустим, исходный список выглядит следующим образом:

| 7 | 5 | 3.5 | 4 | 3.1 |

Первое, что мы делаем, это находим минимальное значение в списке, которое в нашем случае равно 3,1.

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

| 3.1 | 5 | 3.5 | 4 | 7 |

Теперь, когда мы уверены, что первый элемент находится в правильном положении в списке, мы повторяем предыдущий шаг (нахождение минимального значения), начиная со второго элемента в списке. Мы видим, что следующее минимальное значение в списке (начиная со второго элемента) – 3,5. Поэтому теперь мы изменим 3,5 на 5. Теперь список будет выглядеть так:

| 3.1 | 3.5 | 5 | 4 | 7 |

На этом этапе мы уверены, что первый элемент и второй элемент находятся в правильном положении.

Теперь мы проверяем минимальное значение остатка списка, который начинается с третьего элемента, 5. Минимальное значение остатка списка равно 4, и мы меняем его на 5:

| 3.1 | 3.5 | 4 | 5 | 7 |

Итак, теперь мы уверены, что первые три элемента находятся в правильном положении. Для остальных элементов мы повторим вышеописанный процесс.

Давайте посмотрим, как реализовать данный алгоритм сортировки в Python:

def selectionSort(aList):
    for i in range(len(aList)):
        least = i
        for k in range(i+1, len(aList)):
            if aList[k] < aList[least]:
                least = k
        swap(aList, least, i)
def swap(A, x, y):
    temp = A[x]
    A[x] = A[y]
    A[y] = temp
Code language: HTML, XML (xml)

Проверим алгоритм:

my_list = [5.76,4.7,25.3,4.6,32.4,55.3,52.3,7.6,7.3,86.7,43.5]
selectionSort(my_list)
print my_list
Code language: PHP (php)

В этом случае вы должны получить следующий результат:

[4.6, 4.7, 5.76, 7.3, 7.6, 25.3, 32.4, 43.5, 52.3, 55.3, 86.7]
Code language: JSON / JSON with Comments (json)

Алгоритм линейного поиска (Linear Search)

Алгоритм линейного поиска – это простой алгоритм, в котором каждый элемент списка (начиная с первого) перебирается до тех пор, пока не будет найден нужный элемент или пока не будет достигнут конец списка.

Алгоритм линейного поиска на языке Python выглядит следующим образом:

def linearSearch(item,my_list):
    found = False
    position = 0
    while position < len(my_list) and not found:
        if my_list[position] == item:
            found = True
        position = position + 1
    return found
Code language: PHP (php)

Давайте протестируем код.

bag = ['книга','карандаш','ручка','блокнот','точилка','ластик']
item = input('Какой предмет вы хотите найти в сумке?')
itemFound = linearSearch(item,bag)
if itemFound:
    print 'Предмет находится в сумке.'
else:
    print 'Предмета в сумке нет.'
Code language: PHP (php)

Если вы введете, например, ‘ручка’, вы получите следующий результат:

Предмет находится в сумке.