Jednoczesne wyszukiwanie max i min

WPROWADZENIE

SPECYFIKACJA
Problem: 
Jednoczesne wyszukiwanie elementu największego i najmniejszego
w nieuporządkowanym ciągu liczb.

DANE WEJŚCIOWE
Ciąg n liczb umieszczonych w tablicy L. 

DANE WYJŚCIOWE
Para indeksów dla elementu najmniejszego i elementu największego w ciągu L.

Chcemy jednocześnie odnaleźć elementy najmniejszy i największy w podanym zbiorze n elementowym. Metoda siłowa polega na znalezieniu najpierw elementu najmniejszego, a następnie największego. Tak działa pierwsza wersja funkcji minimax, która zwraca parę indeksów - dla elementu minimalnego i maksymalnego. Liczba wykonywanych porównań wynosi 2n-2.

def minimax(L, left, right):
    """Wyszukiwanie elementu najmniejszego i największego.
    Zastosowanie metody siłowej."""
    mini = find_min(L, left, right)
    maxi = find_max(L, left, right)
    return (mini, maxi)             # zwraca krotkę indeksów

Lepszym podejściem jest algorytm minimax. Postępujemy wg zasady dziel i zwyciężaj (divide and conquer).

• Dzielimy badany zbiór na dwa podzbiory A i B w następujący sposób. Z badanego zbioru pobieramy elementy parami, a następnie mniejszy z pary wstawiamy do zbioru A, a większy do zbioru B. Jeżeli n jest nieparzyste, to ostatni element dołączamy do obu zbiorów A i B.
• Znajdujemy element najmniejszy w zbiorze A.
• Znajdujemy element największy w zbiorze B.

ZŁOŻONOŚĆ

Dla n = 2k liczba porównań wynosi
P = k+2(k-1) = 3k-2 = (3n-4)//2.

Dla n = 2k+1 liczba porównań wynosi
P = k+2k = 3k = (3n-3)//2.

Złożoność algorytmu jest rzędu (3/2)n.

IMPLEMENTACJA

def minimax(L, left, right):
    """Wyszukiwanie elementu najmniejszego i największego.
    Zastosowanie metody dziel i zwyciężaj."""
    if left == right:     # tylko jeden element w zbiorze
        return (left, left)
    # co najmniej 2 elementy
    if L[left] > L[left+1]:
        maxi = left
        mini = left+1
    else:
        maxi = left+1
        mini = left
    k = left+2            # już może nie istnieć!
    while k < right:   # pobieramy pary
        if L[k] > L[k+1]:
            if L[k] > L[maxi]:
                maxi = k
            if L[k+1] < L[mini]:
                mini = k+1
        else:
            if L[k+1] > L[maxi]:
                maxi = k+1
            if L[k] < L[mini]:
                mini = k
        k = k+2
    if k == right:        # nieparzysta liczba elementów
        if L[k] > L[maxi]:
            maxi = k
        if L[k] < L[mini]:
            mini = k
    return (mini, maxi)