Przeszukiwanie liniowe tablicy.
Dane: A, n, x,
gdzie: A - tablica n-elementowa,
x - wartość poszukiwana (x jest wartością tego samego typu co
elementy tablicy A).
Wyniki: Liczba całkowita ind taka, że:
1 ≤ ind ≤ n wtedy A[ind] = x,
ind = 0 wtedy brak elementu o wartości x w tablicy.
Search (A, n, x) // A-tablica indeksowana od 1 do n
{
// warunek początkowy: α: n ≥ 1;
1. ind := 1;
// niezmiennik pętli γ: ind=k ∧ A[i] ≠ x dla i=1,2,...,k-1
2. DOPOKI ( ind ≤ n and A[ind] ≠ x) {
3. ind := ind + 1
4. }
5. JEZELI (ind > n) {
6. ind :=0
}
// warunek końcowy β: (ind=0 ∧ A[i] ≠ x dla i =1,2,...n) ∨
// (ind=i ∧ A[i]=x dla 1≤ i ≤ n);
}
Dla każdego k=1,2,...,n+1, jeśli sterowanie dociera do linii 2 po raz k-ty, to
spełniony jest następujący niezmiennik pętli:
ind = k ∧ A[j] ≠x dla j=1,2,...,k-1.
1. Przypadek podstawowy:
Niech k=1. Wowczas ind=k=1 i nie istnieje i<k, dla ktorego A[i]=x.
2. Krok indukcyjny:
Jeżeli warunki te są spełnione dla pewnego k<n+1, to zachodzą rownież dla k+1.
Na podstawie założenia indukcyjnego, gdy linia 2 wykonywana jest po raz k-ty to:
ind=k ∧ A[i] ≠x dla 1≤i< k,
Jeśli warunki w linii 2 sprawdzane są po raz (k+1)-szy to wnioskujemy, że były one
spełnione poprzednio (ind=k+1), zatem:
A[ind] ≠x ∧ A[k] ≠x.
Nazwa algorytmu |
Klasa złożoności |
||
|
optymistyczna |
typowa |
Pesymistyczna |
BOMBELKOWE |
O(n2) |
O(n2) |
O(n2) |
WYBÓR |
O(n2) |
O(n2) |
O(n2) |
WSTAWIANIE |
O(n) |
O(n2) |
O(n2) |
SHELLA |
O(n1,14) |
O(n1,15) |
O(n1,15) |
SCALANIE |
O(n•log n) |
O(n•log n) |
O(n•log n) |
QUICK SORT |
O(n•log n) |
O(n•log n) |
O(n2) |
KUBEŁKOWE |
O(m + n) |
O(m + n) |
O(m + n) |
Najszybsze algorytmy sortujące to algorytmy sortowania dystrybucyjnego. Jednakże szybkość ich działania jest okupiona dużym zapotrzebowaniem na pamięć. Algorytmy te mają liniową klasę czasowej złożoności obliczeniowej. Z algorytmów sortujących w miejscu najszybszym w typowych warunkach jest algorytm sortowania szybkiego. Posiada liniowo logarytmiczną klasę czasowej złożoności obliczeniowej. Jednakże dla niekorzystnych danych może się degradować do klasy kwadratowej. W klasie kwadratowej złożoności obliczeniowej zalecany jest do stosowania algorytm sortowania przez wstawianie. Jest bardzo prosty w implementacji i jednocześnie wystarczająco szybki. Dla zbiorów w znacznym stopniu uporządkowanych wykazuje liniową klasę złożoności obliczeniowej.
Lista (List) - skończona sekwencją elementow ułożonych w liniowym porządku.
L = (a1, a2, ..., an)
• Głowa listy (head): lewy koniec a1,
• Ogon listy (tail): prawy koniec an,
• Długością listy:L=n
Szczegolnym przypadkiem listy jest lista pusta L=( ).
Lista - przykłady ADT (Abstract Data Types):
1. L = (I, II, III, ..., XII) - lista miesięcy,
2. L = (hel, neon, argon, krypton, ksenon, radon) - lista gazow
szlachetnych uporządkowanych zgodnie z masą atomową,
3. L = ((0, 0), (1, 0), (1, 1)) - lista list wspołrzędnych wierzchołkow figury geometrycznej:
L1 = (a1, a2, ..., an)
L2 = (b1, b2, ..., bm), 0 ≤ i ≤ j ≤ n, m
Pozycja na liście, wystąpienie (occurence) elementu:
L[i] = ai
Podlista:
L[i..j] = (ai, ai+1, ..., aj)
Złożenie (konkatenacja)(concatenate):
L1 & L2 = (a1, a2, ..., an, b1, b2, ..., bm)
Podstawowe operacje listy jednokierunkowej.
Wstawianie elementu x na początek listy L:
INSERT_1LIST (L, x)
{
x.next := L.head;
L.head := x;
}
Usuwanie elementu x z początku listy L:
DELETE_1LIST (L, x)
{
L.head := x.next;
}
Wyszukiwanie elementu x o kluczu k na liście L:
SEARCH_1LIST (L, k)
{
x := L.head;
DOPOKI (x≠ NIL ∩ x.key ≠ k) {
x := x.next;
}
ZWROC ( x )
}
Podstawowe operacje listy dwukierunkowej.
Wstawianie elementu x na początek listy L.
INSERT_2LIST (L, x)
{
x.next := L.head;
JEZELI( L.head ≠ NIL ) {
L.head.prev := x;
}
L.head := x;
x.prev := NIL;
}
Wyszukiwanie elementu x o kluczu k na liście L.
SEARCH_2LIST (L, k)
{
x := L.head;
DOPOKI (x≠ NIL ∩ x.key ≠ k) {
x := x.next;
}
ZWROC ( x )
}
Usuwanie elementu x z listy L:
DELETE_2LIST (L, x)
{
JEZELI ( x.prev ≠NIL ) {
x.prev.next := x.next;
} WPP {
L.head := x.next;
JEZELI(x.next ≠NIL ) {
x.next.prev := x.prev;
}
}
Stos (Stack) - struktura liniowo uporządkowanych danych określonego typu, gdzie
wszystkie dostępne operacje wykonywane są na jednym końcu tej struktury,
zwanym szczytem stosu (top).
Stos działa według zasady LIFO (Last-in-First-out).
Podstawowe operacje:
• Wstawianie elementu x do struktury danych (PUSH).
• Usuwanie elementu ze struktury danych (POP).
• Sprawdzenie czy stos jest pusty (EMPTY), pełny (FULL).
Wstawianie elementu na stos.
PUSH (S, x)
{
S.top:= S.top+1
S.A[S.top]:=x
}
Usuwanie elementu ze stosu.
POP (S)
{
JEśELI ( EMPTY(S) ) {
ZWROC (”Błąd”)
} WPP {
S.top:= S.top-1
ZWROC (S.top)
}
}
Kolejka (Queue)- dynamiczna struktura danych, oparta na modelu listy,
zorganizowana według reguły FIFO (First-in First-out).
Podstawowe operacje dla kolejki:
• DEQUEUE - usuwanie elementu z początku kolejki,
• ENQUEUE - wstawianie elementu na koniec,
• EMPTY - sprawdzenie czy kolejka jest pusta,
• FRONT - zwracanie pierwszego elementu,
• CLEAR - tworzenie kolejki pustej
Wstawianie elementu na koniec kolejki:
ENQUEUE (Q, x)
{
Q.rear.next :=x;
x.next := NIL;
Q.rear:=x;
}
Usuwanie elementu z początku kolejki:
DEQUEUE ( Q )
{
JEZELI ( EMPTY ( Q) ) {
ZWROC (0);
} WPP {
Q.front:= Q.front.next;
}
}