Technologia Informacyjna Temat 8: Przykłady algorytmów
Algorytm Euklidesa Algorytm Euklidesa – pozwala znaleźć największy wspólny dzielnik dwóch liczb naturalnych.
Algorytm Euklidesa Function NWD(a, b) As Integer While b <> 0
c = a mod b
a = b
b = c
Loop
NWD = a
End Function
Przeszukiwanie liniowe Zwane też wyszukiwaniem sekwencyjnym.
Pozwala znaleźć pierwsze wystąpienie zadanego elementu w podanym ciągu danych.
Przeszukiwanie liniowe Function Znajdz(klucz)
i = 1
While i <= n do
if tablica[i] = klucz then znaleziony = i
break
End if
i = i + 1
Loop
Znajdz = znaleziony
End Function
Przeszukiwanie binarne Zwane też wyszukiwaniem metodą połowienia.
Pozwala znaleźć pierwsze wystąpienie zadanego elementu w podanym ciągu danych.
Jest znacznie szybsze niż przeszukiwanie liniowe, ale zbiór przeszukiwanych danych musi być posortowany.
Przeszukiwanie liniowe Function Znajdz(klucz)
p = 1
k = n
While p < k do
c = (p+k)/2
if tablica[c] = klucz then znaleziony = c
break
else if tablica[c] < klucz p = c
else
k = c
End if
Loop
Znajdz = znaleziony
End Function
Sortowanie bąbelkowe Jedna z najprostszych metod sortowania.
Polega na sukcesywnym porównywaniu sąsiadujących elementów i ich zamianie gdy jest to konieczne.
Sortowanie bąbelkowe A = lista elementów do posortowania n = liczba_elementów(A) do
for i = 0 to n-1
if A[i] > A[i+1] then swap(A[i], A[i+1])
end if
Next i
n = n-1
while n > 1
Sortowanie szybkie Zwane także QuickSort.
Jest to algorytm rekurencyjny, jeden z najszybszych, choć nie w każdych warunkach.
Sortowanie szybkie Sub QuickSort(l, r)
If l<r then
i = PodzielTablice(l, r) QuickSort(l, i-1)
QuickSort(i, r)
End if
End Sub
Sortowanie szybkie Pojawiająca się w przykładzie funkcja PodzielTablice ma na celu wyznaczenie tzw. elementu osiowego, a następnie rozdzielenie danych w tablicy tak aby mniejsze niż element osiowy znajdowały się po lewej stronie, a większe po prawej. Wartością zwracaną jest indeks elementu osiowego w tablicy A.