SPECYFIKACJA Problem: Wyszukiwanie największego elementu w nieuporządkowanym ciągu liczb. DANE WEJŚCIOWE Ciąg n liczb umieszczonych w tablicy L. DANE WYJŚCIOWE Pozycja (indeks) elementu największego w ciągu L.
Zadanie znajdowania elementu maksymalnego (minimalnego) jest typowym zadaniem wyszukiwania, które rozwiązujemy przy pomocy algorytmu wyszukiwania liniowego. Za tymczasowy maksymalny (minimalny) element przyjmujemy pierwszy element zbioru. Następnie element tymczasowy porównujemy z kolejnymi elementami. Jeśli któryś z porównywanych elementów jest większy (mniejszy) od elementu tymczasowego, to za nowy tymczasowy element maksymalny (minimalny) przyjmujemy porównywany element zbioru. Gdy cały zbiór zostanie przeglądnięty, w elemencie tymczasowym otrzymamy element maksymalny (minimalny) w zbiorze. Algorytm jest optymalny (Ira Pohl, 1972).
Możliwe są dwa podejścia: zwracamy indeks największego elementu (dane w tablicy) lub zwracamy sam element największy (dane w tablicy lub w pliku). Jeżeli dostęp do danych jest sekwencyjny, to lepiej jest zwracać sam element największy (a raczej jego kopię).
Zajmiemy się implementacją funkcji zwracającej indeks największego elementu na liście (w zadanym przedziale indeksów). Dla zbioru n liczb musimy wykonać (n-1) porównań. Wyszukiwanie elementu najmniejszego jest analogiczne.
min(arg1, arg2, *args, *[, key]) # dwa lub więcej argumentów min(iterable[, key=func]) # Py2, jeden argument min(iterable, *[, key, default]) # Py3.4, jeden argument max(arg1, arg2, *args, *[, key]) # dwa lub więcej argumentów max(iterable[, key=func]) # Py2, jeden argument max(iterable, *[, key, default]) # Py3.4, jeden argument # The 'default' argument specifies an object to return if the provided # iterable is empty. If the iterable is empty and default is not provided, # a ValueError is raised.
def find_max(L, left, right):
"""Wyszukiwanie indeksu elementu największego."""
k = left
i = left + 1
while i <= right:
if L[i] > L[k]:
k = i
i += 1
return k
def find_min(L, left, right):
"""Wyszukiwanie indeksu elementu najmniejszego."""
k = left
i = left + 1
while i <= right:
if L[i] < L[k]:
k = i
i += 1
return k
# Pythonowa symulacja wyszukiwania elementu największego w pliku.
def find_max(afile):
best = None
for item in afile:
if best is None:
best = item
elif item > best:
best = item
return best
Algorytm wyszukiwania liniowego jest wykorzystywany w algorytmie sortowania przez wybór. W sposób ciągły wybieramy najmniejszy element z coraz mniejszego zbioru danych.