Podstawowe operacje algorytmu Ameba:
- uporządkowanie
F(x0)>F(x1)>…>F(xn)
- odbicie
xr = x + (x - xn)
- F(xr)
a) F(xr)>F(x0) dokonujemy ekspansji
xs = xr + (x - xn)
F(xs)>F(xr)
xs xr
F(xs)<F(xr)
xr xs
b) F(xr)<F(xn-1) kontrakcja
xc = x + (x - xn)
xc xn
- skurczanie
xi = x0 + (xi - x0)
Złożoności obliczeniowe
F(n) = O(g(n)) pesymistyczny wariant złożoności obliczeniowej
0<f(n)<cg(n)
F(n) = (g(n)) optymistyczne ograniczenie od dolu
0<cg(n)<f(n)
F(n) = (g(n)) ograniczona z góry i z dołu jednocześnie
0<c1g(n)<f(n)<c2g(n)
F(n) = o(g(n)) dla dowolnych c>0
0<f(n)<cg(n))
F(n) = w(g(n)) dla dowolnych c>0
0<cg(n)<f(n)
Sortowanie bąbelkowe (bubblesort)
Sprawdzamy całą tablicę od końca, jeżeli trafimy na parę elementów, w której większy poprzedza mniejszy to zamieniamy je miejscami i znów zaczynamy przeszukiwać tą tablicę od końca. Czynność powtarzamy tak długo aż podczas sprawdzania całej tablicy, nie zajdzie ani jedna zamiana elementów.
void b_sort(int tablica[10], int ile_liczb)
{
int temp,i,zmiana;
do
{
zmiana=0;
i=ile_liczb-1;
do
{
i--;
if (tablica[i+1]< tablica[i])
{
temp=tablica[i];
tablica[i]=tablica[i+1];
tablica[i+1]=temp;
zmiana=1;
}
}
while (i!=0);
}
while (zmiana!=0);
Sortowanie szybkie (quicksort)
Zbiór danych zostaje podzielony na dwa podzbiory i każdy z nich jest sortowany niezależnie od drugiego. Dla zadanej tablicy a[l..p] wybieramy element v=a[l] i przeszukujemy resztę tablicy (tzn. a[l+1..p]) tak długo, aż nie znajdziemy elementu nie większego niż a[l]. Następnie przeszukujemy tą tablicę od strony prawej póki nie znajdziemy elementu nie większego niż a[l]. Gdy to osiągniemy, zamieniamy miejscami te dwa elementy i zaczynamy cały proces od początku. Algorytm działa tak długo, aż wskaźnik poruszający się w lewo i wskaźnik poruszający się w prawo spotkają się. Należy wówczas zamienić element v=a[l] z ostatnim elementem lewej części tablicy.
void quicksort(int tablica[10], int x, int y)
{
int i,j,v,temp;
i=x;
j=y;
v=tablica[div(x+y,2).quot];
do
{
while (tablica[i]<v) i++;
while (v<tablica[j]) j--;
if (i<=j)
{
temp=tablica[i];
tablica[i]=tablica[j];
tablica[j]=temp;
i++;
j--;
}
}
while (i<=j);
if (x<j) quicksort(tablica,x,j);
if (i<y) quicksort(tablica,i,y);
}
Sortowanie przez wstawianie (insertionsort)
Pierwszy element pozostaje na swoim miejscu. Następnie bierzemy drugi i sprawdzamy, w jakiej relacji jest on z pierwszym. Jeśli jest niemniejszy, to zostaje na drugim miejscu, w przeciwnym wypadku wędruje na pierwsze miejsce. Dalej sprawdzamy trzeci element (porównujemy go do dwóch pierwszych i wstawiamy w odpowiednie miejsce), czwarty (porównujemy z trzema pierwszymi), piąty itd. Idea działania algorytmu opiera sięna podziale ciągu na dwie części: pierwsza jest posortowana, druga jeszcze nie. Wybieramy kolejną liczbę z drugiej części i wstawiamy ją do pierwszej. Ponieważ jest ona posortowana, to szukamy dla naszej liczby takiego miejsca, aby liczba na lewo była niewiększa a liczba na prawo niemniejsza.
void insertionsort(int tablica[10], int ile_liczb)
{
int i,j,v;
for (i=1;i<ile_liczb;i++)
{
j=i;
v=tablica[i];
while ((tablica[j-1]>v)&&(j>0))
{
tablica[j]=tablica[j-1];
j--;
}
tablica[j]=v;
}
Sortowanie przez wymianę/wybór (selectionsort)
Metoda ta nazywana jest sortowaniem przez wymianę gdyż na początku szukany jest najmniejszy element, po znalezieniu go jest on zamieniany z pierwszym elementem tablicy.
Następnie szukany jest znów najmniejszy element, ale począwszy od elementu drugiego (pierwszy - najmniejszy jest już wstawiony na odpowiednie miejsce), po jego znalezieniu jest on zamieniany z drugim elementem. Czynność tą powtarzamy kolejno na elementach od trzeciego, czwartego, aż do n-tego.
void selectionsort(int tablica[10], int ile_liczb)
{
int min,i,j,temp;
for (i=0;i<ile_liczb-1;i++)
{
min=i;
for (j=i+1;j<ile_liczb;j++)
if (tablica[j]<tablica[min]) min=j;
temp=tablica[min];
tablica[min]=tablica[i];
tablica[i]=temp;
}