Student: A
ukasz Rychter Warszawa, 21.11.2009
Nr indeksu: 218882
Grupa studencka: 3M2
Data lab. 13.11.2009 (dzieo PW) 14.15-16.15
Prowadzący: dr inż. Adam Wojtasik
Laboratorium AISDE
Sprawozdanie z dwiczenia 2:
Badanie złożoności obliczeniowej algorytmów
Na przykładzie algorytmów sortowania
1) Zadanie
Na laboratorium należało zbadad podanym programem(z możliwością własnych zmian w kodzie w
razie potrzeby) różne algorytmy sortowania. Do moich zadao należało przetestowanie algorytmów
Wstawiania w wersjach 2,4,5, algorytmów sortowania Bąbelkowego i Shella oraz wykonanie poleceo
1,2,3,5,7 z instrukcji do laboratorium.
2) Wykonanie zadania
Zgodnie z poleceniem 7 program uzupełniłem o 3 dodatkowe procedury generujące dane do
posortowania (ich szczegółowy opis jest zawarty w dalszej części tekstu) i dla 5 różnych algorytmów
generujących ciągi danych (2 były już zawarte w programie) zbierałem dane dla każdego zadanego
algorytmu dla dwóch typów elementów  INT i typu złożonego tzw. BI oraz dla różnych liczności danych do
posortowania, zwiększając krok wraz ze zwiększaniem rozmiaru problemu. Gdy przy danej liczności czas
działania algorytmów stawał się zbyt długi dla większych liczności pomijałem badanie algorytmów
najwolniejszych  o największej złożoności obliczeniowej. Badanie algorytmów dla większych liczności
zostało też pominięte dla typu danych BI przy założeniu, że algorytmy zachowają złożonośd obliczeniową
taką jak dla danych typu INT, natomiast zwiększenie czasu obliczeo dla BI względem INT będzie można
zaobserwowad dla mniejszych liczności.
Dla ułatwienia zbierania danych i uniknięcia błędów użyłem skryptu w dużym stopniu
automatyzującego proces badania algorytmów, natomiast do obróbki danych, ich zebrania w tabele -
napisanego przez siebie niewielkiego programu parsującego. Ich opis jednak pomijam, jako nieistotny.
Zebrane dane zostały poddane analizie jak niżej, według poleceo zawartych w instrukcji do
laboratorium.
4) Wykonanie poleceo
I) Zad 1.  Przeanalizowad działanie poszczególnych algorytmów sortowania
a) Algorytm Wstawianie2
for(i=L+1; i<=R; i++){ this->ZA.LiPor++;
for(j=i; (j>L)&&!(this->Dane[j-1]Dane[j]); j--){ this->ZA.LiPor++;
Zamien(this->Dane[j-1],this->Dane[j]);
}
}
Algorytm działa na zasadzie podziału zbioru danych na dane posortowane  po lewej stronie tablicy danych
(o niższych indeksach) i dane nieposortowane  po prawej (o wyższych indeksach). Początkowo do części
posortowanej należy tylko 1 element, pierwszy z danych do posortowania. Do części nieposortowanej 
cała reszta.
Pierwsza pętla przesuwa indeks pierwszego z elementów z części nieposortowanej, od elementu 2 do
ostatniego. Oznacza to, że z każdym jej obiegiem częśd posortowana zwiększa się o 1 element,
nieposortowana zmniejsza o 1 (element pierwszy z części nieposortowanej).
Wewnętrzna pętla wraz z funkcją Zamien powoduje wstawienie nowego elementu dołączonego do części
posortowanej na odpowiednią pozycję poprzez jego przesuwanie w stronę niższych indeksów tablicy aż do
jej początku(warunek 1 pętli) lub do miejsca docelowego, gdzie element wcześniejszy będzie ostro
mniejszy od rozważanego(warunek 2 pętli). Za każdym krokiem elementy są zamieniane, a więc
następuje(nadmiarowe) kopiowanie danych. Mankament ten poprawiają dalsze wersje algorytmu
Wstawiania.
Wykresy dynamiczne działania algorytmu. Na osi odciętych kolejne elementy, na osi rzędnych wartości.
Wykresy wykonane dla liczności 200 i podstawowego algorytmu generującego dane do posortowania
(losowe wartości). Krokiem pomiędzy wykresami jest zakres pierwszej pętli, podzielony na równe odcinki.
b) Algorytm Wstawianie4
for(i=R; i>L; i--){ this->ZA.LiPor++;
this->ZamienWarunkowo(this->Dane[i-1],this->Dane[i]);
}
for(i=L+2; i<=R; i++){ this->ZA.LiPor++;
j=i;
Element=this->Dane[i]; this->ZA.LiZam++;
InsertPoint=BisekcjaDoWstawiania(0,i-1,this->Dane[i]);
this->ZA.LiPor++;
while(j>InsertPoint){ this->ZA.LiPor++;
this->Dane[j]=this->Dane[j-1]; this->ZA.LiZam++;
j--;
}
this->Dane[j]=Element; this->ZA.LiZam++;
}
Pierwsza pętla wstępnie sortuje dane na zasadzie pojedynczego przebiegu sortowania bąbelkowego, od
strony indeksów wyższych do niższych. Kolejne pary elementów są porównywane i jeśli trzeba zamieniane.
Tym sposobem pierwszy element danych jest po tym przebiegu elementem globalnie najmniejszym, a
reszta danych jest nieco uporządkowana.
Następnie mamy algorytm wstawiania podobny do algorytmu Wstawianie2 (z tą różnicą, że zaczynamy od
elementu 3, a nie 2)  podział danych na częśd posortowaną i nieposortowaną. Element przenoszony do
części posortowanej nie jest jednak przesuwany jak wcześniej poprzez zamienianie z kolejnymi
elementami. Jest zapamiętywany w zmiennej Element (dla szybszego działania przy częstych odwołaniach
do niego, aby nie wykonywad operacji -> oraz *+). Następnie znajdowany jest docelowy punkt wstawienia
tego elementu za pomocą funkcji BisekcjaDoWstawiania.
Nie zagłębiając się w szczegóły implementacyjne tej funkcji można jednak stwierdzid, że działa ona na
zasadzie połowienia zbioru (części posortowanej). Ma więc złożonośd pesymistyczną rzędu log2n, w
najlepszym przypadku rozwiązanie może zostad znalezione w pierwszym kroku, czyli jest dośd szybka w
przeciętnym przypadku.
Po znalezieniu punktu wstawienia wszystkie elementy z części posortowanej na prawo od tego punktu są
przesuwane o 1 w prawo(pętla while), a na koocu element jest wstawiany na docelową pozycję.
W porównaniu do algorytmu Wstawianie2 w przeciętnym przypadku algorytm ten jest szybszy, gdyż
wymagana jest mniejsza liczba porównao (wyszukiwanie bisekcją zamiast liniowego przeszukiwania jak w
wersji 2 algorytmu) oraz wstawieo danych  element docelowy jest wstawiany jednokrotnie, a w
algorytmie Wstawianie2 podczas każdej zamiany danych, a do tego element przesuwany jest jeszcze
zapisywany do zmiennej tymczasowej.
Jednak w przypadku danych wejściowych optymistycznych (uporządkowanych) algorytm Wstawianie4
może byd wolniejszy, ponieważ BisekcjaDoWstawiania będzie potrzebowała większej liczby kroków niż
przeszukiwanie liniowe, które zakooczy się już w pierwszym kroku (lub bliskim pierwszemu dla danych nie
idealnie uporządkowanych). Podsumowując BisekcjaDoWstawiania w średnim przypadku daje znaczny zysk
wydajności jednak istnieją dane wejściowe dla których jest mniej wydajna niż rozwiązanie zastosowane w
algorytmie Wstawianie2.
Wykresy dynamiczne nie różnią się zauważalnie od tych z algorytmu Wstawianie2 (pierwsza pętla wstępnie
sortująca różni te algorytmy, jednak wynik jej działania jest praktycznie niewidoczny na wykresach
dynamicznych, natomiast reszta algorytmu różni się jedynie sposobem implementacji, a nie techniką
działania).
c) Algorytm Wstawianie5
for(i=R; i>L; i--){ this->ZA.LiPor++;
this->ZamienWarunkowo(this->Dane[i-1],this->Dane[i]);
}
for(i=L+2; i<=R; i++){ this->ZA.LiPor++;
j=i;
Element=this->Dane[i]; this->ZA.LiZam++;
InsertPoint=BisekcjaDoWstawiania(0,i-1,this->Dane[i]);
memcpy((void*)&(this->Dane[InsertPoint+1]),
(void*)&(this->Dane[InsertPoint]),(i-InsertPoint)*sizeof(Element));
this->ZA.LiZam++;
this->Dane[InsertPoint]=Element; this->ZA.LiZam++;
}
Algorytm ten różni się od poprzedniego jedynie sposobem przesuwania danych w części posortowanej dla
wstawienia nowego elementu. W algorytmie Wstawianie4 w pętli while przepisywane były kolejne
elementy. W tym algorytmie poprzez wytłuszczoną w kodzie wyżej funkcję memcpy kopiowany jest
jednorazowo cały blok danych. Jest to rozwiązanie znacznie bardziej wydajne zwłaszcza dla przy dużych
ilościach elementów do kopiowania. Poza tą różnicą algorytmy działają identycznie.
d) Algorytm sortowania Bąbelkowego
for(i=L; iZA.LiPor++;
for(j=R; j>i; j--){ this->ZA.LiPor++;
ZamienWarunkowo(this->Dane[j-1],this->Dane[j]);
}
}
Jest to najprostszy z algorytmów sortowania i nie zawiera żadnych optymalizacji. Pierwsza pętla przechodzi
od elementu pierwszego do przedostatniego. Tym samym przesuwa znacznik w tablicy danych
rozdzielający dane już uporządkowane (w ostatecznej kolejności, nie jak w algorytmach wstawiania gdzie
pomiędzy te dane były jeszcze wstawiane kolejne elementy) od części sortowanej.
Druga pętla przebiega od elementu ostatniego do pierwszego za tym znacznikiem. Kolejne wartości
(bąbelki) są zamieniane miejscami aby spełniały względem siebie relację nierówności. Tym samym w
każdym przebiegu pętli zewnętrznej do prawego skraju części posortowanej tablicy dodawany jest element
najmniejszy pozostały w części nieposortowanej oraz rośnie ogólne uporządkowanie w części jeszcze nie
całkowicie posortowanej.
Wykresy dynamiczne działania algorytmu, wykonane analogicznie jak dla algorytmu Wstawiania. Krok
dobrany w taki sam sposób (zakres pierwszej pętli podzielony na równe odcinki).
e) Algorytm Shella
for(h=1; h<=(R-L)/9; h=3*h+1) this->ZA.LiPor++;
for( ;h>0; h=h/3){ this->ZA.LiPor++;
for(i=L+h; i<=R; i++){ this->ZA.LiPor++;
j=i;
Element=this->Dane[i]; this->ZA.LiZam++;
this->ZA.LiPor++;
while((j>=L+h)&&(ElementDane[j-h])){ this->ZA.LiPor++;
this->Dane[j]=this->Dane[j-h]; this->ZA.LiZam++;
j-=h;
}
this->Dane[j]=Element; this->ZA.LiZam++;
}
}
W ogólnej teorii algorytm sortowania Shella polega na wielokrotnym podziale zbioru danych na h
podzbiorów, gdzie h dąży od pewnej wartości do 1 według zadanego ciągu, który w istotny sposób wpływa
na wydajnośd algorytmu. Dla każdej z wartości h każdy z podciągów jest oddzielnie sortowany. Tym
sposobem duży problem jest dzielony na wiele mniejszych  jest to podejście  Dziel i zwyciężaj .
Opis implementacji tego algorytmu zawartej w podanym programie:
Pierwsza pętla wyznacza maksymalną wartośd parametru h, tak aby w pojedynczym podciągu znajdowało
się początkowo około 9 elementów (początkowa liczba podciągów mniejsza lub równa liczności zbioru
podzielonej przez 9). Kolejne wartości h wyznaczane są za pomocą ciągu Knutha (hi+1 = 3hi + 1).
Kolejna pętla powoduje za każdym obiegiem trzykrotne zmniejszanie liczby podciągów, aż do 1 ciągu. Nie
jest to zgodne z ciągiem Knutha (aby było wartości h powinny byd obliczane według odwrotnego jak
podano wyżej, czyli hi-1=(hi-1)/3 ). Przewidywalnie nie jest to wiec rozwiązanie optymalne.
Trzecia pętla for powoduje przechodzenie od 2 elementu w pierwszym podciągu do ostatniego w ostatnim
podciągu. Przy ogólnym spojrzeniu widad, że 3 pętla for wraz ze swoją zawartością działa jak wymieszanie
algorytmów Wstawianie2 i Wstawianie4 (docelowy element jest wstawiany na miejsce jednokrotnie,
jednak miejsce wstawienia jest wyszukiwane liniowo, nie przez bisekcję) dla elementów o h odległych w
tablicy danych (stanowiących oddzielone podciągi).
Teoretycznie trudno określid czy zastosowanie bisekcji spowodowałoby zmniejszenie złożoności
obliczeniowej algorytmu, gdyż dla małej liczności podciągów (początkowe duże wartości h) bisekcja
mogłaby powodowad jedynie dodatkowy narzut operacji względem przeszukiwania liniowego, natomiast
dla zmniejszającego się h (zwiększających się liczności podciągów) uporządkowanie rośnie, mamy więc
przypadek coraz bliższy optymistycznemu, co jak podkreślono przy analizie algorytmu Wstawianie4 może
powodowad przewagę rozwiązania z przeszukiwaniem liniowym.
Wykresy dynamiczne działania algorytmu, wykonane analogicznie jak wcześniejsze. Dla liczności 200
algorytm dobiera wartości h równe kolejno 40, 13, 4, 1. Wykresy 2,3,4 i 5 to wyniki działania sortowao dla
tych wartości h.
II) Zad. 2  Zbadad złożonośd obliczeniową wskazanych algorytmów sortowania
100000000
Wstawianie2
1000000
10000
100
1
10 100 1000 10000
Liczności
100000000
Wstawianie2
1000000
10000
100
1
10 100 1000 10000
Liczności
100000000
Wstawianie2
1000000
10000
100
1
10 100 1000 10000
Liczności
1000000
Wstawianie2
100000
10000
1000
100
10
1
10 100 1000 10000
0,1
Liczności
Przerywanymi liniami zaznaczono krzywe aproksymacyjne. Dla pierwszego wykresu y=0,77*n2 , dla
drugiego y=0,27*n2, dla trzeciego y=1,03*n2, dla czwartego y=0,001*n2, gdzie n to licznośd. Złożonośd
obliczeniowa jest więc rzędu n2.
Dla czasu przy małych licznościach linia aproksymacyjna odbiega od pomiaru, ponieważ czas jest silnie
skwantowany (dochodzimy do granicy rozdzielczości pomiaru) i możliwie zaburzony przez czynniki
pasożytnicze jak np. inne procesy działające w systemie.
Liczba kopiowao
Liczba porównao
kopiowania + porównania
Czas
100000000
Wstawianie4
1000000
10000
100
1
10 100 1000 10000
Liczności
100000000
Wstawianie4
1000000
10000
100
1
10 100 1000 10000
Liczności
100000000
Wstawianie4
1000000
10000
100
1
10 100 1000 10000
Liczności
1000000
100000 Wstawianie4
10000
1000
100
10
1
0,1
10 100 1000 10000
0,01
Liczności
Linie aproksymacyjne: dla pierwszego wykresu y=0,29*n2 , dla drugiego y=0,42*n2, dla trzeciego y=0,71*n2,
dla czwartego y=0,0008*n2. Złożonośd obliczeniowa jest więc rzędu n2.
Względem pierwszego algorytmu algorytm ten wykonuje więcej porównao, jednak nie jest to czynnik
dominujący wpływający na ogólną wydajnośd. Pod względem zsumowanej liczby operacji i czasu
wykonywania wypada nieznacznie lepiej (około 45% dla sumy operacji).
Liczba kopiowao
Liczba porównao
kopiowania + porównania
Czas
1000000
Wstawianie5
100000
10000
1000
100
10
1
10 100 1000 10000 100000
Liczności
10000000
Wstawianie5
1000000
100000
10000
1000
100
10
1
10 100 1000 10000 100000
Liczności
10000000
Wstawianie5
1000000
100000
10000
1000
100
10
1
10 100 1000 10000 100000
Liczności
1000000
Wstawianie5
10000
100
1
10 100 1000 10000 100000
0,01
Liczności
Linie aproksymacyjne: dla pierwszego wykresu y=5,85*n , dla drugiego y=11,86*n1,1, dla trzeciego
y=22,58*n1,05, dla czwartego y= 0,00026*n1,95. Złożonośd obliczeniowa zależy więc od parametru jaki
wez
miemy pod uwagę. Biorąc pod uwagę sumę działao jest to n1,05 w przybliżeniu liniowa n. Względem
czasu działania złożonośd to n1,95 w przybliżeniu n2 jednak ta nieznaczna różnica jest istotna dla dużych
liczności oraz przy porównywaniu algorytmów. Różnica w wartości złożoności obliczeniowej wyznaczanej
dla liczby operacji i dla czasu jest spowodowana tym, że polecenie memcpy jest liczone jako jedna
operacja, wewnętrznie natomiast długośd jej działania zależy od liczności. Jej złożonośd jest nieco poniżej
liniowej.
Względem algorytmu Wstawianie4 algorytm Wstawianie5 charakteryzuje się zupełnie inną złożonością
biorąc pod uwagę liczbę operacji porównywania i wstawiania i nieco niższego rzędu złożonością czasową co
jest istotne dla dużych zbiorów danych.
Liczba kopiowao
Liczba porównao
kopiowania + porównania
Czas
100000000
Bąbelkowe
1000000
10000
100
1
10 100 1000 10000
Liczności
100000000
Bąbelkowe
1000000
10000
100
1
10 100 1000 10000
Liczności
100000000
Bąbelkowe
1000000
10000
100
1
10 100 1000 10000
Liczności
10000000
1000000 Bąbelkowe
100000
10000
1000
100
10
1
0,1
10 100 1000 10000
Liczności
Linie aproksymacyjne: dla pierwszego wykresu y=0,75*n2 , dla drugiego y=0,75*n2, dla trzeciego y=1,5*n2,
dla czwartego y= 0,0026*n2. Złożonośd obliczeniowa to więc n2.
Algorytm ten jest więc najwolniejszym z rozważanych, o największej złożoności obliczeniowej pod każdym
względem (algorytm Wstawianie2 wykonuje minimalnie więcej kopiowao, jest to jednak różnica zwykle
zaniedbywalna). Pod względem sumy operacji jest około 46% wolniejszy od algorytmu Wstawianie2. Pod
względem czasu działania aż 10 krotnie.
Liczba kopiowao
Liczba porównao
kopiowania + porównania
Czas
100000000
10000000
Shella
1000000
100000
10000
1000
100
10
1
10 100 1000 10000 100000 1000000
Liczności
100000000
10000000
Shella
1000000
100000
10000
1000
100
10
1
10 100 1000 10000 100000 1000000
Liczności
100000000
Shella
1000000
10000
100
1
10 100 1000 10000 100000 1000000
Liczności
1000000
Shella
100000
10000
1000
100
10
1
10 100 1000 10000 100000 1000000
0,1
Liczności
Linie aproksymacyjne: dla pierwszego wykresu y=5,38*n1,19 , dla drugiego y=5,38*n1,19 (liczby kopiowao i
porównao są prawie identyczne), dla trzeciego y=10,76*n1,19, dla czwartego y= 0,03*n1,16. Złożonośd
obliczeniowa jest więc rzędu n1,19 dla liczby operacji i nieco lepsza n1,16 dla czasu (co jednak może zależed
od sprzętu, optymalizacji przy kompilacji itp.). Uzyskaliśmy więc wynik bliski teoretycznej możliwej
najniższej złożoności pesymistycznej tego algorytmu  n1,15.
Algorytm ten jest więc zdecydowanie najszybszym z rozważanych, o najmniejszej złożoności obliczeniowej.
Algorytm Wstawianie5 wykazuje mniejszą złożonośd pod względem liczby operacji, jest to jednak
spowodowane pewnym niedopatrzeniem przy jego badaniu (opisanym w podpunkcie alg. Wstawianie5). W
praktyce pod względem czasu działania algorytm Shella jest o rzędy wielkości szybszy.
Liczba kopiowao
Liczba porównao
kopiowania + porównania
Czas
Zestawienie badanych algorytmów
100000000
Zestawienie
Wstawianie2
1000000
Wstawianie4
10000
Wstawianie5
Bąbelkowe
100
Shella
1
10 100 1000 10000 100000 1000000
Liczności
100000000
Zestawienie
Wstawianie2
1000000
Wstawianie4
10000
Wstawianie5
Bąbelkowe
100
Shella
1
10 100 1000 10000 100000 1000000
Liczności
100000000
Zestawienie
Wstawianie2
1000000
Wstawianie4
10000
Wstawianie5
Bąbelkowe
100
Shella
1
10 100 1000 10000 100000 1000000
Liczności
10000000
Wstawianie2
Zestawienie
1000000
Wstawianie4
100000
10000 Wstawianie5
1000
Bąbelkowe
100
Shella
10
1
10 100 1000 10000 100000 1000000
Liczności
1200000
Wstawianie2 Zestawienie
1000000
Wstawianie4
800000
Wstawianie5
600000
Bąbelkowe
400000
Shella
200000
0
0 2000 4000 6000 8000 10000 12000 14000 16000 18000 20000
Liczności
Liczba kopiowao
Liczba porównao
kopiowania + porównania
Czas - skala logarytmiczna
Czas - skala liniowa
Wnioski:
Wydajnośd algorytmów można uszeregowad w kolejności od najgorszej do najlepszej: Bąbelkowe,
Wstawianie2, Wstawianie4, Wstawianie5, Shella.
Algorytmy Bąbelkowe, Wstawianie2, Wstawianie4 charakteryzują się złożonością rzędu n2 jednak algorytm
sortowania Bąbelkowego posiada znacznie większy współczynnik dla tej złożoności przez co jest wyraz
nie
najwolniejszy (co widad na wykresach). Algorytmy Wstawianie2 i Wstawianie4 są podobnej wydajności
jednak przewaga algorytmu 4 jest zauważalna.
Małą złożonośd pod względem ilości operacji alg. Wstawianie5 należy uznad za pewnego rodzaju błąd w
założeniach przy pomiarze i za czynnik miarodajny dla wydajności brad czas obliczeo.
Dla liczności zbiorów poniżej 50 pomiary czasu są niedokładne więc nie należy ich uznawad za miarodajne.
III) Zad.3  Określid stabilnośd wskazanych algorytmów sortowania
Stabilny algorytm sortowania powinien zachowywad względną kolejnośd uporządkowania elementów o
tych samych kluczach z danych wejściowych. Stabilnośd będę wiec obserwowad na postawie danych typu
złożonego BI, gdzie kluczem według którego elementy są sortowane jest liczba, natomiast drugą wartością,
rozróżniającą elementy jest litera.
Przy badaniu stabilności do generowania danych wejściowych używam algorytmu 2, który produkuje wiele
powtarzających się kluczy liczbowych, co ułatwia obserwację.
Początkowo Wstawianie2 Wstawianie4 Wstawianie5 Bąbelkowe Shella
0 C 0 L 0 L 0 L 0 C 0 C
0 C 0 B 0 B 0 B 0 C 0 C
3 J 0 P 0 P 0 P 0 J 0 N
2 C 0 B 0 B 0 B 0 E 0 B
0 J 0 L 0 L 0 L 0 N 0 J
0 E 0 K 0 K 0 K 0 B 0 E
0 N 0 G 0 G 0 G 0 R 0 N
0 B 0 N 0 N 0 N 0 N 0 D
0 R 0 H 0 H 0 H 0 D 0 R
0 N 0 L 0 L 0 L 0 L 0 N
3 G 0 D 0 D 0 D 0 H 0 G
0 D 0 N 0 N 0 N 0 N 0 P
0 L 0 R 0 R 0 R 0 G 0 L
0 H 0 B 0 B 0 B 0 K 0 H
0 N 0 N 0 N 0 N 0 L 0 B
1 R 0 E 0 E 0 E 0 B 0 L
1 P 0 J 0 J 0 J 0 P 0 K
1 M 0 C 0 C 0 C 0 B 0 L
0 G 0 C 0 C 0 C 0 L 0 B
1 C 1 D 1 D 1 D 1 R 1 A
0 K 1 R 1 R 1 R 1 P 1 R
0 L 1 A 1 A 1 A 1 M 1 M
0 B 1 C 1 C 1 C 1 C 1 C
0 P 1 M 1 M 1 M 1 A 1 P
0 B 1 P 1 P 1 P 1 R 1 D
2 C 1 R 1 R 1 R 1 D 1 R
1 A 2 C 2 C 2 C 2 C 2 C
0 L 2 C 2 C 2 C 2 C 2 C
1 R 3 G 3 G 3 G 3 J 3 J
1 D 3 J 3 J 3 J 3 G 3 G
Jak widad jedynie sortowanie Bąbelkowe jest stabilne.
IV) Zad. 7  Napisad procedury generujące różne rozkłady danych do sortowania
Oprócz domyślnej procedury generującej dane wykorzystywałem zawartą już w podanym kodzie procedurę
WypelnijINT_2(), która generuje mały zakres możliwych wartości, a więc wiele powtarzających się
kluczy. Oprócz tego dopisałem 3 własne procedury:
//dane prawie posortowane (przypadek bliski optymistycznemu)
void WypelnijINT_3(){
int licznosc = SortINT->GetLicznosc();
for(int i=0;iSortINT->GetDaneKopia()[i]= i;
if (rand()%10==0) SortINT->GetDaneKopia()[i] += (int)((rand()/(double)RAND_MAX-0.5)*licznosc);
}
memcpy(SortINT->GetDane(),SortINT->GetDaneKopia(),SortINT->GetLicznosc()*sizeof(int));
}
//dane prawie posortowane w odwrotnej kolejności (przypadek bliski pesymistycznemu)
void WypelnijINT_4(){
int licznosc = SortINT->GetLicznosc();
for(int i=0;i SortINT->GetDaneKopia()[i]= licznosc-i;
if (rand()%10==0) SortINT->GetDaneKopia()[i] += (int)((rand()/(double)RAND_MAX-0.5)*licznosc);
}
memcpy(SortINT->GetDane(),SortINT->GetDaneKopia(),SortINT->GetLicznosc()*sizeof(int));
}
//dane prawie posortowane, jednak z mniejszą połową przeniesioną na koniec
void WypelnijINT_5(){
int licznosc = SortINT->GetLicznosc();
for(int i=0;iSortINT->GetDaneKopia()[i]= i > licznosc/2 ? i - licznosc/2 : i + licznosc/2;
if (rand()%10==0) SortINT->GetDaneKopia()[i] += (int)((rand()/(double)RAND_MAX-0.5)*licznosc);
}
memcpy(SortINT->GetDane(),SortINT->GetDaneKopia(),SortINT->GetLicznosc()*sizeof(int));
}
Procedura 3 generuje ciąg rosnący, 4 malejący, 5 rosnący, jednak z ze skokiem w środku  w drugiej
połowie wszystkie wartości są mniejsze od najmniejszej wartości w 1 połowie.
Oprócz tego wszystkie ciągi zaburzyłem w ten sam sposób przez zmianę średnio co 10 elementu o wartośd
losową z zakresu +- 0.5*licznośd (w przypadku pierwszej procedury  aby ciąg nie był już całkiem
uporządkowany, w przypadku 2 następnych  aby zachowad korelację z pierwszą).
Procedury zostały poddane testowaniu, którego nie przytaczam jako nieistotne.
Analogiczne algorytmy zostały zastosowane również dla złożonego typu danych BI.
V) Zad. 5  Wskazad przyczyny potencjalnych ograniczeo wydajności badanych algorytmów
sortowania
10000000
INT
Wstawianie2
1000000
Wstawianie4
100000
Wstawianie5
10000
Bąbelkowe
1000
Shella
100
10
1
10 100 1000 10000
Liczności
10000000
BiData
Wstawianie2
1000000
Wstawianie4
100000
Wstawianie5
10000
Bąbelkowe
1000
Shella
100
10
1
10 100 1000 10000
Liczności
Dla typu złożonego BiData wszystkie algorytmy charakteryzują się dłuższym czasem działania, jednak
wyraz
ne największy spadek wydajności odnotowujemy dla algorytmu Wstawianie2 ponieważ cechuje się
on dużą liczbą kopiowao danych. W przypadku dużych rozmiarów sortowanych elementów jego wydajnośd
jest więc znacznie ograniczona i zbliża się do wydajności sortowania Bąbelkowego.
Liczba operacji kopiowao i wstawieo nie zależy od typu elementu danych.
Czas
Czas
10000000
Wstawianie2
WypelnijINT_1
1000000
Wstawianie4
100000
10000 Wstawianie5
1000
Bąbelkowe
100
Shella
10
1
10 100 1000 10000
Liczności
10000000
Wstawianie2
1000000 WypelnijINT_2
100000 Wstawianie4
10000
Wstawianie5
1000
Bąbelkowe
100
Shella
10
1
0,1
10 100 1000 10000
Liczności
1000000
Wstawianie2
WypelnijINT_3
100000
Wstawianie4
10000
Wstawianie5
1000
Bąbelkowe
100
Shella
10
1
10 100 1000 10000
Liczności
1000000
Wstawianie2
WypelnijINT_4
100000
Wstawianie4
10000
Wstawianie5
1000
Bąbelkowe
100
Shella
10
1
10 100 1000 10000
Liczności
1000000
Wstawianie2
WypelnijINT_5
100000
Wstawianie4
10000
Wstawianie5
1000
Bąbelkowe
100
Shella
10
1
10 100 1000 10000
Liczności
Czas
Czas
Czas
Czas
Czas
1000000
Wypelnij_INT1
Wstawianie2
100000
Wypelnij_INT2
10000
Wypelnij_INT3
1000
Wypelnij_INT4
100
Wypelnij_INT5
10
1
10 100 1000 10000
Liczności
1000000
Wypelnij_INT1
Wstawianie4
100000
Wypelnij_INT2
10000
Wypelnij_INT3
1000
Wypelnij_INT4
100
Wypelnij_INT5
10
1
10 100 1000 10000
Liczności
1000000
Wypelnij_INT1
Wstawianie5
100000
Wypelnij_INT2
10000
Wypelnij_INT3
1000
Wypelnij_INT4
100
Wypelnij_INT5
10
1
10 100 1000 10000
Liczności
10000000
Wypelnij_INT1
Bąbelkowe
1000000
Wypelnij_INT2
100000
10000 Wypelnij_INT3
1000
Wypelnij_INT4
100
Wypelnij_INT5
10
1
10 100 1000 10000
Liczności
10000
Wypelnij_INT1
Shella
1000
Wypelnij_INT2
100 Wypelnij_INT3
Wypelnij_INT4
10
Wypelnij_INT5
1
10 100 1000 10000
0,1
Liczności
Czas
Czas
Czas
Czas
Czas
Wnioski:
- Wszystkie sortowania Wstawiania maja podobne charakterystyki przy zależności od rodzaju danych
wejściowych. Przypadek pesymistyczny jest tylko niewiele wolniejszy od średniego, natomiast przypadek
bliski optymistycznemu jest od średniego szybszy o około rząd wielkości.
- Wszystkie algorytmy dla procedur 1 i 5 zachowują się prawie identycznie.
- Algorytmy Wstawiania dla wielu powtarzających się elementów z niewielkiego zakresu (procedura
generująca 2) posiadają złożonośd pomiędzy przypadkiem średnim a pesymistycznym.
- Sortowanie Bąbelkowe jest mało czułe na postad danych wejściowych. Najgorszą wydajnośd osiąga dla
powtarzających się elementów.
-Sortowanie Shella najgorszą wydajnośd uzyskuje dla danych losowych (procedury 1) czyli przypadku
średniego, tylko nieco lepszą dla danych już w dużej części uporządkowanych. Dla przypadku danych w
uszeregowanych w odwrotnej kolejności wydajnośd jest bardzo podobna do średniej i przypadku dużego
uporządkowania. Widocznie najlepiej algorytm działa dla często powtarzających się wartości kluczy.
-Dla danych wejściowych prawie posortowanych i jednocześnie małych liczności najszybszy okazuje się
algorytm Wstawianie2. W szczególności jest szybszy od algorytmu Wstawianie4, co zostało przewidziane
teoretycznie.
-Oprócz powyższej uwagi uszeregowanie pod względem wydajności algorytmów pozostaje niezmienione
pomimo zmiany danych wejściowych (pomiary poniżej liczności 100 pomijam, gdyż są obarczone zbyt
dużym błędem, aby na ich podstawie wyciągad wnioski). Zmieniają się jednak stosunki wydajności
pomiędzy algorytmami co przy dodatkowych uwarunkowaniach (np. elementy o dużym rozmiarze) może
decydowad o wyższości danego algorytmu nad innym.
5) Podsumowanie całości
W zasadzie wszystko zostało już powiedziane we wcześniejszych punktach. Jako najważniejsze
spostrzeżenia powtórzyd możne, iż:
1. Praktycznie w każdym przypadku najbardziej wydajnym z algorytmów jest sortowanie Shella.
Posiada złożonośd obliczeniową bliską liniowej, podczas gdy inne algorytmy bliską kwadratowej.
2. Sortowanie Bąbelkowe jest najmniej wydajnym z algorytmów jednak ma pewne zalety  małą
wrażliwośd na postad danych wejściowych, stabilnośd sortowania oraz samą prostotę algorytmu.
3. Różne implementacje tego samego algorytmu  Wstawiania posiadają odmienne charakterystyki ze
względu na różne badane parametry. Wyróżnid można np. mała wydajnośd algorytmu Wstawianie2
dla złożonego typu elementów, ale dużą dla przypadku danych optymistycznych i małych liczności.
Algorytm Wstawianie5 różniący się od alg. Wstawianie4 jedynie techniką kopiowania danych w
większości przypadków jest od niego znacznie wydajniejszy.
4. Stabilne okazało się jedynie sortowanie Bąbelkowe. Należy jednak zauważyd, że możliwe jest
sprawienie, aby algorytmy Wstawiania były stabilne poprzez zastosowanie nierówności nieostrej
zamiast ostrej.
6) Tabele zebranych danych (pominięto dane dla wykresów dynamicznych i wszelkie opracowania danych)
INT algorytm generujący 1
Liczność
Wstawianie2 Wstawianie4 Wstawianie5 Bąbelkowe Shella
Czas Kopiowania Porównania Czas Kopiowania Porównania Czas Kopiowania Porównania Czas Kopiowania Porównania Czas Kopiowania Porównania
10 2 84 38 2 54 106 3 39 75 1 48 71 1 38 42
20 2 198 86 2 130 281 2 96 211 9 168 266 4 98 102
30 2 582 224 14 304 557 4 165 362 3 534 643 3 197 201
40 4 1296 472 4 586 951 5 231 520 5 1230 1230 4 345 351
50 5 1941 697 5 837 1344 6 285 696 8 1881 1902 4 466 472
60 6 2571 917 6 1085 1728 7 342 869 10 2487 2659 4 583 589
70 6 3594 1268 8 1466 2253 7 402 1053 13 3495 3650 5 694 700
80 8 4533 1591 9 1817 2742 8 459 1228 21 4398 4706 5 808 814
90 8 5913 2061 11 2317 3400 10 519 1426 23 5790 6025 5 935 941
100 10 7674 2658 12 2948 4173 11 585 1614 30 7539 7563 7 1101 1107
200 32 29550 10050 35 10636 13506 29 1179 3653 104 29247 29849 13 2575 2583
300 75 64620 21840 72 22724 27388 42 1776 5844 243 64113 66521 22 4289 4297
400 132 117111 39437 119 40617 47199 67 2370 8156 409 116496 119032 32 6320 6330
500 191 181716 61072 174 62552 71104 97 2970 10526 648 180933 185561 41 8555 8565
600 272 257994 86598 243 88378 98948 108 3570 12944 927 257040 265980 51 10419 10429
700 365 359205 120435 331 122515 135183 142 4170 15442 1255 358185 364745 59 12465 12475
800 466 470319 157573 405 159953 174747 166 4770 17968 1631 469116 476772 69 14844 14854
900 588 598809 200503 517 203183 220127 207 5370 20518 2075 597462 604604 79 17084 17094
1000 708 737856 246952 612 249932 269082 257 5970 23124 2570 736404 745968 88 19183 19193
2000 2882 3003960 1003320 2364 1009302 1051590 810 11973 50265 10356 3000930 3001310 200 43302 43314
3000 6560 6793383 2267461 5280 2276441 2343363 1569 17970 78896 23361 6788907 6764469 326 73742 73754
4000 11580 12038319 4016773 9337 4028749 4121342 2868 23964 108561 41695 12032493 12012831 473 105108 105122
5000 18005 18773004 6262668 14509 6277642 6396589 3995 29961 138912 64614 18765687 18757729 598 134657 134671
6000 26054 27154656 9057552 20892 9075524 9221505 5776 35958 169943 93431 27145752 27051584 758 170972 170986
7000 36163 36778605 12266535 28219 12287517 12461004 7508 41973 201464 126239 36768345 36759615 892 202494 202508
8000 45968 47923407 15982469 36719 16006443 16207744 9713 47961 233266 165098 47911668 47974556 1049 242876 242890
9000 58153 60567717 20198239 46439 20225207 20454676 12059 53952 265425 208937 60554445 60689315 1173 273494 273508
10000 72350 75271182 25100394 57714 25130370 25388375 16229 59964 297973 258127 75256389 75090463 1342 309454 309470
11000 87183 90781761 30271587 69512 30304565 30591454 18137 65967 330860 313180 90765624 90760708 1508 342887 342903
12000 104388 108524247 36186749 83627 36222729 36538752 21525 71970 363997 372822 108506529 108174843 1668 382586 382602
13000 122517 126842970 42293990 97347 42332962 42678403 25278 77958 397403 438252 126823722 126781074 1823 416349 416365
14000 141935 146996541 49012847 112863 49054821 49429896 29589 83961 431040 509334 146975604 146998868 2036 457174 457190
15000 162073 168399705 56148235 129409 56193217 56597827 33576 89973 464587 583188 168377469 168633323 2130 486643 486659
16000 184418 191675046 63907682 146915 63955650 64390364 38368 95952 498670 662553 191651625 191891875 2338 536041 536057
17000 208845 216869085 72306695 166128 72357663 72822469 43058 101952 532762 749316 216843900 216789800 2485 580743 580759
18000 233268 242605683 80886561 185824 80940537 81435499 48659 107964 566930 840690 242578917 242868639 2662 624210 624226
19000 260149 270053598 90036866 207268 90093846 90619344 53716 113970 601472 936691 270025203 270517901 2794 648027 648043
20000 288349 299274537 99778179 229520 99838159 100394234 60690 119970 636049 1038021 299244879 299758293 2990 686959 686975
21000 253406 110132989 110719792 65472 125967 670774 3150 733985 734001
22000 277932 120763334 121381089 72485 131967 705726 3343 785334 785350
23000 305283 132335591 132984414 79072 137958 740785 3487 816190 816206
24000 332882 144110751 144790714 85885 143955 775922 3659 858079 858095
25000 360089 156073310 156784653 94471 149958 811305 3843 904782 904798
26000 390092 168904772 169647461 100640 155949 846642 4012 937284 937300
27000 419962 181917900 182692199 111369 161955 882258 4193 986882 986898
28000 452830 195979302 196785159 118177 167973 917834 4362 1031922 1031938
29000 484238 209736360 210573877 125649 173961 953482 4516 1062559 1062575
30000 517592 224191412 225060658 136645 179964 989214 4763 1116206 1116224
31000 142811 185964 1025134 4962 1169225 1169243
32000 152392 191964 1061034 5128 1205028 1205046
33000 162586 197967 1097031 5332 1262036 1262054
34000 177263 203976 1133212 5512 1296405 1296423
35000 183171 209943 1169263 5700 1341959 1341977
36000 194595 215958 1205596 5873 1391154 1391172
37000 205662 221973 1242011 6099 1434796 1434814
38000 218679 227961 1278513 6276 1484087 1484105
39000 229477 233970 1315229 6485 1549545 1549563
40000 239112 239958 1351807 6709 1598777 1598795
41000 253940 245964 1388585 6814 1619203 1619221
42000 263317 251976 1425475 6986 1656668 1656686
43000 275729 257952 1462335 7184 1707108 1707126
44000 289522 263952 1499346 7389 1761354 1761372
45000 306024 269952 1536280 7639 1808523 1808541
46000 315507 275961 1573431 7829 1861496 1861514
47000 328899 281967 1610737 8013 1915468 1915486
48000 348096 287958 1647832 8195 1963789 1963807
49000 356741 293943 1685105 8389 2016608 2016626
50000 377743 299955 1722533 8581 2070786 2070804
60000 535610 359967 2098590 10708 2602651 2602669
70000 736626 419958 2478379 12679 3085209 3085227
80000 963001 479946 2863571 14889 3674640 3674658
90000 1211690 539931 3252702 17182 4275665 4275685
100000 1495120 599955 3645051 19369 4827411 4827431
110000 21937 5548012 5548032
120000 24619 6292634 6292654
130000 27160 7042271 7042291
140000 29276 7560402 7560422
150000 32568 8566516 8566536
160000 34816 9148259 9148279
170000 37658 9979549 9979569
180000 39865 10585106 10585126
190000 42240 11216502 11216522
200000 44870 11872358 11872378
300000 69092 18012208 18012230
400000 98824 25601747 25601769
500000 122908 32067292 32067314
600000 155447 41345073 41345095
700000 181446 47956804 47956826
800000 211318 56510056 56510080
900000 243488 64904446 64904470
1000000 275776 73253160 73253184
INT algorytm generujący 2
Liczność
Wstawianie2 Wstawianie4 Wstawianie5 Bąbelkowe Shella
Czas Kopiowania Porównania Czas Kopiowania Porównania Czas Kopiowania Porównania Czas Kopiowania Porównania Czas Kopiowania Porównania
10 3 105 45 2 55 111 2 30 70 2 33 66 1 35 39
20 2 378 146 2 178 335 3 78 199 2 117 249 1 86 90
30 2 732 274 3 324 605 5 120 345 5 234 543 4 135 139
40 4 1446 522 6 594 998 5 168 496 6 552 1004 3 237 243
50 6 2436 862 7 950 1490 6 207 651 9 978 1601 3 320 326
60 8 3840 1340 9 1446 2116 7 249 803 12 1584 2358 3 389 395
70 8 5175 1795 9 1917 2735 8 288 970 18 2121 3192 4 483 489
80 8 6660 2300 10 2438 3420 9 327 1153 16 2697 4139 4 553 559
90 10 7980 2750 12 2914 4044 10 381 1335 20 3204 5163 4 639 645
100 12 10056 3452 14 3638 4924 11 429 1519 24 4095 6415 5 731 737
200 43 41658 14086 40 14456 17443 24 855 3446 95 16869 25723 8 1770 1778
300 110 94515 31805 93 32371 37206 42 1299 5538 225 39273 58241 12 2831 2839
400 201 171972 57724 157 58472 65281 64 1722 7735 402 71688 104096 16 4170 4180
500 286 270126 90542 235 91470 100273 86 2142 9949 628 111675 162475 19 5324 5334
600 418 395673 132491 334 133597 144510 116 2559 12276 912 162534 234478 23 6506 6516
700 534 516600 172900 431 174214 187279 144 3021 14690 1205 210165 315405 27 7667 7677
800 686 662814 221738 554 223256 238485 176 3477 17110 1581 269946 410382 31 8912 8922
900 857 847290 283330 709 285034 302455 220 3906 19531 1983 346929 521093 35 10188 10198
1000 1045 1044219 349073 841 350977 370594 258 4356 21977 2441 427692 643064 40 11500 11510
2000 4069 4171032 1392344 3272 1396184 1439383 900 8760 47963 9915 1739616 2580872 85 26225 26237
3000 9055 9332934 3113978 7199 3119796 3188246 1904 13227 75681 22625 3947133 5817211 132 40918 40930
4000 16403 16952841 5654947 13048 5662635 5756959 3339 17532 103860 40720 7222200 10409400 178 58636 58650
5000 25159 26096136 8703712 19978 8713376 8834740 5041 21996 133364 63485 11119038 16208846 227 74745 74759
6000 35858 37211073 12409691 28411 12421367 12570215 7123 26514 163366 90972 15866343 23291781 276 90702 90716
7000 48548 50466498 16829166 38521 16842846 17019434 10089 31020 193612 123645 21587634 31699378 329 107331 107345
8000 63163 65720382 21914794 50005 21930474 22135026 12440 35520 224076 161673 28196571 41402857 396 124854 124868
9000 80590 83661174 27896058 63599 27913670 28147108 15885 39918 255360 205133 36074079 52529193 446 141999 142013
10000 100252 103291773 34440591 78685 34460181 34722895 19856 44385 287103 254087 44618253 64877751 491 165986 166002
11000 121417 125870625 41967875 96092 41989369 42281587 24286 48741 318963 309571 54555216 78690572 546 183704 183720
12000 144061 149153628 49729876 113949 49753368 50075170 28766 53238 351044 367951 64676043 93564681 605 201785 201801
13000 168994 175285848 58441616 134454 58467058 58818561 33885 57663 383170 431250 76125405 109881635 656 219859 219875
14000 196352 203474658 67838886 155411 67866252 68247635 39372 62049 415436 501412 88544706 127521902 719 238018 238034
15000 226898 234529251 78191417 179243 78220679 78631950 48390 66393 447668 578450 102214518 146579006 773 256333 256349
16000 257866 266702436 88916812 203859 88948050 89389233 52712 70857 480044 657340 116215038 166746346 820 274484 274500
17000 291759 301552494 100534498 230592 100567658 101039481 60583 75240 513067 743422 131492220 188339240 876 292807 292823
18000 326441 338230545 112761515 259219 112796617 113299564 65640 79653 546604 833825 147525123 211184041 930 310751 310767
19000 364079 376979667 125678889 289105 125715947 126250190 74474 84087 580334 928867 164401428 235309976 989 329547 329563
20000 403879 418266780 139442260 320531 139481236 140046831 81591 88464 614063 1030666 182484678 260838226 1045 348507 348523
21000 353666 153710579 154307568 90120 92898 647891 1098 367061 367077
22000 389075 168663640 169292243 100602 97308 681915 1168 386135 386151
23000 425366 184473415 185133546 108431 101739 715874 1230 405405 405421
24000 461965 200512302 201203979 118051 106233 749914 1289 424130 424146
25000 501578 217231136 217954499 129342 110733 784100 1374 442278 442294
26000 542956 235118909 235873998 138217 115137 818230 1398 461254 461270
27000 585546 253405623 254192482 149796 119592 852455 1495 480405 480421
28000 629984 272667100 273485749 163816 124020 886673 1527 500198 500214
29000 675086 292290894 293141437 174140 128481 921028 1579 518861 518877
30000 721768 312272276 313154719 187412 132984 955431 1626 557451 557469
31000 197112 137433 989794 1679 576266 576284
32000 210299 141903 1024216 1728 595857 595875
33000 223379 146352 1058923 1811 615801 615819
34000 236668 150738 1094385 1849 635491 635509
35000 254581 155142 1129927 1899 655334 655352
36000 266800 159639 1165606 1981 675316 675334
37000 280579 164067 1201260 2021 695199 695217
38000 298732 168537 1236950 2078 715308 715326
39000 312493 173013 1272712 2152 736220 736238
40000 327666 177402 1308477 2206 755857 755875
41000 345878 181803 1344200 2262 775526 775544
42000 363171 186258 1380023 2333 795074 795092
43000 380467 190641 1415846 2380 815746 815764
44000 399621 195051 1451772 2442 835472 835490
45000 422503 199482 1487825 2511 855886 855904
46000 436937 203841 1523790 2573 875677 875695
47000 459503 208230 1559777 2618 895841 895859
48000 474389 212628 1595827 2686 916559 916577
49000 496436 217038 1631899 2740 937223 937241
50000 520518 221574 1668117 2809 957205 957223
60000 742403 266331 2030912 3421 1162779 1162797
70000 1010537 310737 2399962 4041 1371977 1371995
80000 1317231 355026 2777309 4683 1583283 1583301
90000 1674027 399384 3156457 5262 1852325 1852345
100000 2055981 443790 3537317 5897 2069580 2069600
110000 6533 2289977 2289997
120000 7194 2512968 2512988
130000 7823 2730978 2730998
140000 8476 2953359 2953379
150000 9131 3179411 3179431
160000 9784 3400650 3400670
170000 10486 3627771 3627791
180000 11136 3851240 3851260
190000 11799 4078294 4078314
200000 12459 4303570 4303590
300000 19127 6805897 6805919
400000 26037 9211032 9211054
500000 35588 11639269 11639291
600000 40426 14109121 14109143
700000 50651 16619529 16619551
800000 56981 19682877 19682901
900000 64895 22238176 22238200
1000000 69489 24849454 24849478
INT algorytm generujący 3
Liczność
Wstawianie2 Wstawianie4 Wstawianie5 Bąbelkowe Shella
Czas Kopiowania Porównania Czas Kopiowania Porównania Czas Kopiowania Porównania Czas Kopiowania Porównania Czas Kopiowania Porównania
10 2 6 12 0 19 77 1 27 69 2 3 56 1 31 35
20 2 27 29 2 53 224 2 66 201 2 24 218 2 78 82
30 2 87 59 2 111 404 2 123 360 2 75 490 1 132 136
40 3 186 102 3 194 605 3 198 533 4 168 876 2 255 261
50 2 270 140 4 250 811 3 240 705 5 243 1356 3 334 340
60 3 399 193 4 331 1025 4 297 875 7 375 1955 3 425 431
70 3 585 265 4 437 1265 5 363 1055 9 546 2667 4 511 517
80 3 687 309 5 493 1494 9 396 1241 10 651 3457 4 583 589
90 3 822 364 5 574 1730 6 450 1430 12 789 4358 4 669 675
100 3 1014 438 6 666 1990 6 492 1620 15 969 5373 5 758 764
200 7 3216 1272 20 1802 4741 12 1095 3638 53 3153 21151 9 1926 1934
300 11 6201 2367 17 3203 7927 17 1704 5832 115 6117 47189 15 3148 3156
400 15 10929 4043 26 5217 11880 23 2361 8228 203 10842 83814 22 5016 5026
500 20 15462 5654 33 7104 15778 29 2925 10603 314 15357 130369 28 6519 6529
600 27 21855 7885 41 9647 20267 36 3543 12967 448 21738 187546 34 7953 7963
700 39 27930 10010 50 12030 24763 50 4080 15417 607 27789 254613 41 9365 9375
800 46 40200 14200 63 16536 31313 49 4704 17885 792 40026 333742 48 10986 10996
900 54 50892 17864 75 20502 37416 57 5307 20425 1002 50694 422348 55 12572 12582
1000 65 61452 21484 86 24438 43603 65 5931 23100 1232 61236 520912 62 14231 14241
2000 249 245205 83735 266 89685 132047 178 11925 50291 4930 244755 2082585 149 34540 34552
3000 534 538941 182647 533 191547 258892 316 17850 79199 11059 538269 4680923 245 54260 54272
4000 1000 1006485 339495 927 351315 443921 486 23730 108340 19572 1005612 8337204 360 81673 81687
5000 1519 1549974 521658 1389 536590 655550 653 29898 138862 30508 1548912 13018804 463 106830 106844
6000 2172 2184849 734283 1900 752179 898520 843 35844 170189 43795 2183559 18730853 575 131752 131766
7000 2874 2885376 968792 2485 989608 1163141 1076 41724 201261 59385 2883864 25464788 683 156707 156721
8000 3706 3775122 1266374 3202 1290272 1491673 1306 47847 233252 77492 3773442 33261814 792 182299 182313
9000 4759 4842207 1623069 4066 1649911 1879595 1594 53763 265451 98639 4840299 42117933 912 208407 208421
10000 5869 5966331 1998777 4957 2028551 2286854 1877 59661 297968 121383 5964216 51993072 1066 250007 250023
11000 7011 7142934 2391978 5908 2424886 2711389 2201 65862 330369 147140 7140675 62885725 1182 276636 276652
12000 8374 8552625 2862875 7023 2898783 3215114 2538 71862 364197 174943 8550120 74856040 1308 305610 305626
13000 9823 9990954 3343318 8130 3382206 3727543 2884 77832 397173 205390 9988260 87835920 1440 335502 335518
14000 11437 11718114 3920038 9480 3961898 4337409 3293 83790 431305 237904 11715180 101912060 1573 366414 366430
15000 13191 13521774 4522258 10896 4567142 4971569 3713 89826 464257 274262 13518573 117013691 1701 394489 394505
16000 14986 15408495 5152165 12387 5200021 5634268 4153 95784 498035 311659 15405138 133143046 1836 424620 424636
17000 16876 17370123 5807041 13884 5857923 6322497 4597 101823 532401 352405 17366523 150297341 1962 455779 455795
18000 18770 19324530 6459510 15409 6513250 7009416 5113 107610 567780 394247 19320696 168449232 2109 485238 485254
19000 20791 21423216 7160072 17080 7216840 7743025 5552 113652 601841 439612 21419232 187649244 2233 516737 516753
20000 23067 23754948 7938316 18929 7998192 8553810 6092 119814 635436 486381 23750742 207926914 2366 547634 547650
21000 20832 8834574 9421214 6637 125766 670410 2504 579934 579950
22000 22809 9703446 10320748 7224 131784 705090 2658 612622 612638
23000 25030 10625744 11275085 7875 137331 740676 2781 645393 645409
24000 27119 11537936 12217511 8452 143793 775372 2913 675911 675927
25000 29765 12523425 13234660 9104 149703 810942 3069 708892 708908
26000 31681 13514487 14257309 9747 155736 846562 3197 742400 742416
27000 34240 14618898 15393779 10406 161778 882663 3343 774098 774114
28000 36892 15782686 16588918 11189 167586 917822 3469 803322 803338
29000 39593 16941615 17779532 11924 173589 953510 3602 837221 837237
30000 42794 18311281 19181323 13232 179763 989809 3885 908417 908435
31000 13668 185733 1025830 3989 945924 945942
32000 14330 191676 1060607 4142 977714 977732
33000 15190 197748 1095859 4286 1012223 1012241
34000 16432 203466 1133699 4458 1045397 1045415
35000 16856 209751 1168538 4587 1081092 1081110
36000 17737 215709 1205382 4745 1120342 1120360
37000 18667 221727 1242407 4902 1156466 1156484
38000 19645 227697 1279684 5056 1189266 1189284
39000 21001 233592 1314149 5184 1229845 1229863
40000 21605 239592 1352800 5367 1265655 1265673
41000 22963 245706 1389736 5528 1311220 1311238
42000 24120 251616 1424165 5698 1343824 1343842
43000 24783 257643 1462745 5838 1374919 1374937
44000 26295 263727 1500045 5958 1401113 1401131
45000 27279 269535 1537245 6098 1434104 1434122
46000 28400 275709 1573411 6264 1474075 1474093
47000 29196 281622 1610176 6412 1513575 1513593
48000 30338 287694 1648105 6577 1555526 1555544
49000 31584 293610 1685410 6747 1595472 1595490
50000 33112 299592 1721495 6966 1636189 1636207
60000 46320 359610 2097444 8468 1997096 1997114
70000 61386 419664 2477704 10050 2352612 2352630
80000 79360 479550 2862365 11623 2708529 2708547
90000 99798 539550 3250833 13721 3256524 3256544
100000 122756 599601 3646202 15404 3651854 3651874
110000 17205 4085935 4085955
120000 18928 4513657 4513677
130000 20726 4928851 4928871
140000 22662 5408796 5408816
150000 24357 5779313 5779333
160000 26136 6204988 6205008
170000 28082 6694821 6694841
180000 29991 7170609 7170629
190000 31903 7654979 7654999
200000 33812 8078928 8078948
300000 54913 13174631 13174653
400000 77735 18524260 18524282
500000 100285 23677498 23677520
600000 122634 29517511 29517533
700000 142712 35563121 35563143
800000 170832 43039336 43039360
900000 197816 50533594 50533618
1000000 223203 57328952 57328976
INT algorytm generujący 4
Liczność
Wstawianie2 Wstawianie4 Wstawianie5 Bąbelkowe Shella
Czas Kopiowania Porównania Czas Kopiowania Porównania Czas Kopiowania Porównania Czas Kopiowania Porównania Czas Kopiowania Porównania
10 3 132 54 2 78 122 2 51 79 2 129 98 1 42 46
20 2 531 197 2 251 383 2 111 207 2 522 384 2 133 137
30 3 1215 435 3 517 769 3 168 364 3 1203 866 2 223 227
40 4 2142 754 4 866 1237 4 228 523 5 2124 1528 2 331 337
50 5 3336 1162 5 1304 1801 5 288 689 7 3315 2380 3 440 446
60 7 4896 1692 7 1864 2487 6 348 855 8 4869 3453 3 566 572
70 8 6723 2311 8 2513 3282 7 408 1041 11 6690 4715 4 674 680
80 11 8751 2997 9 3229 4140 8 468 1223 18 8712 6144 5 784 790
90 31 11019 3763 12 4023 5082 9 525 1408 17 10977 7754 5 972 978
100 16 13737 4679 15 4973 6174 36 591 1596 20 13689 9613 5 1119 1125
200 57 56964 19188 47 19780 22655 24 1188 3667 75 56919 39073 11 2628 2636
300 160 127842 42914 120 43802 48467 42 1782 5851 169 127755 87735 18 4189 4197
400 265 228720 76640 200 77830 84403 70 2385 8162 288 228612 156404 24 5815 5825
500 397 359352 120284 309 121776 130351 101 2988 10567 444 359232 244994 31 7512 7522
600 551 517578 173126 425 174918 185455 135 3588 12929 641 517419 352773 40 9724 9734
700 736 703326 235142 572 237230 249697 165 4182 15253 881 703173 479741 46 11271 11281
800 966 920505 307635 742 310023 324626 208 4782 17789 1093 920328 627176 55 13503 13513
900 1184 1164954 389218 941 391908 408769 266 5385 20450 1400 1164783 793711 62 15481 15491
1000 1444 1435587 479529 1144 482517 501576 307 5982 23045 1728 1435338 978946 71 17923 17933
2000 5643 5765610 1923870 4486 1929856 1972297 1137 11979 50424 6822 5765208 3922736 161 40049 40061
3000 12580 12972120 4327040 9966 4336022 4402665 2482 17973 78620 15491 12971475 8825325 277 66015 66027
4000 22081 23026872 7679624 17524 7691602 7784263 4343 23967 108632 27703 23025957 15677319 370 90433 90447
5000 34461 36047457 12020819 27359 12035809 12155154 6726 29985 139334 43272 36046398 24517966 471 115594 115608
6000 49634 51945297 17321099 39454 17339087 17484778 9667 35982 169677 63199 51944067 35317689 583 142519 142533
7000 67674 70726818 23582606 53611 23603584 23777087 13095 41967 201474 85174 70725438 48078646 706 172384 172398
8000 88144 92282490 30768830 69755 30792820 30994023 16993 47985 233192 111609 92280861 62764287 829 205047 205061
9000 111768 116778096 38935032 88477 38962018 39191149 21717 53979 265114 141181 116776251 79429917 950 236170 236184
10000 138730 144090762 48040254 109355 48070238 48328421 27139 59976 298163 175055 144088737 98034579 1077 264766 264782
11000 167355 174323154 58118718 132742 58151708 58438965 33340 65985 331246 212326 174320820 118612440 1235 291179 291195
12000 199658 207526038 69187346 158516 69223338 69539349 40593 71988 364003 253813 207523473 141180491 1322 323770 323786
13000 234340 243472842 81170614 185604 81209598 81554169 47560 77976 396551 297343 243470091 165663197 1469 365789 365805
14000 272200 282388671 94143557 215432 94185537 94559348 55538 83970 429785 344945 282385680 192135560 1584 387442 387458
15000 313090 324247725 108097575 247291 108142565 108546684 64158 89985 464108 395846 324244602 220589034 1725 421504 421520
16000 356892 368992209 123013403 281515 123061393 123496378 73816 95985 498974 450508 368988897 251004299 1863 462784 462800
17000 402312 416394768 138815256 316218 138866244 139330537 85601 101982 532279 518756 416391180 283305560 2019 489021 489037
18000 452620 466751259 155601753 356560 155655739 156149958 96395 107979 566202 585068 466747539 317591513 2142 520920 520936
19000 508070 520169205 173408735 396799 173465721 173991230 106058 113979 601492 652082 520165188 353897896 2284 559387 559403
20000 560641 576301473 192120491 440046 192180477 192736376 112956 119979 635882 704988 576297228 392109076 2431 595100 595116
21000 487119 211820748 212406275 126145 125979 669510 2561 628110 628126
22000 535282 232442432 233061023 136409 131970 706565 2726 678461 678477
23000 585429 253990862 254640111 152180 137973 741226 2942 727571 727587
24000 638094 276590690 277271699 165256 143985 776998 2992 744889 744905
25000 692753 300051235 300762144 178558 149982 810895 3170 787237 787253
26000 748827 324390587 325133490 192413 155982 846889 3332 839954 839970
27000 808388 349844103 350619232 209222 161982 883115 3463 857587 857603
28000 871012 376211318 377016303 227214 167982 916971 3657 896652 896668
29000 933126 403484914 404322113 237610 173982 953185 3753 935083 935099
30000 998194 431643964 432512699 254372 179985 988724 3855 948922 948940
31000 272006 185976 1024587 3969 983724 983742
32000 294056 191979 1060174 4129 1018062 1018080
33000 310350 197973 1095576 4252 1051446 1051464
34000 327704 203979 1132610 4373 1073186 1073204
35000 349765 209982 1168535 4553 1127750 1127768
36000 369992 215976 1204853 4798 1180549 1180567
37000 391990 221982 1241993 4851 1192932 1192950
38000 411446 227979 1276578 5030 1237815 1237833
39000 436903 233985 1315240 5220 1295435 1295453
40000 455422 239979 1352172 5397 1317329 1317347
41000 476444 245970 1389413 5475 1333628 1333646
42000 504183 251976 1423815 5599 1372466 1372484
43000 525000 257976 1462177 5785 1423963 1423981
44000 553349 263985 1499634 5916 1449581 1449599
45000 574251 269973 1535924 6150 1492763 1492781
46000 603636 275976 1571925 6286 1560208 1560226
47000 631610 281976 1608617 6395 1588229 1588247
48000 657647 287976 1647057 6622 1647516 1647534
49000 680136 293976 1684967 6818 1690115 1690133
50000 714571 299967 1721520 6923 1723129 1723147
60000 1029853 359970 2098199 8615 2147842 2147860
70000 1394804 419973 2480292 10264 2584192 2584210
80000 1830909 479979 2861278 12015 3006885 3006903
90000 2299872 539982 3252773 13641 3400457 3400477
100000 2845696 599982 3643637 15273 3781169 3781189
110000 17116 4226338 4226358
120000 18916 4692770 4692790
130000 20554 5100210 5100230
140000 22581 5595762 5595782
150000 24288 6051365 6051385
160000 26105 6517063 6517083
170000 28149 7053482 7053502
180000 30047 7514064 7514084
190000 32029 8065510 8065530
200000 34372 8680400 8680420
300000 54364 13742078 13742100
400000 77546 19546182 19546204
500000 98824 25107720 25107742
600000 121233 31060109 31060131
700000 143164 37371099 37371121
800000 168584 44397799 44397823
900000 191647 50061110 50061134
1000000 217446 56747647 56747671
INT algorytm generujący 5
Liczność
Wstawianie2 Wstawianie4 Wstawianie5 Bąbelkowe Shella
Czas Kopiowania Porównania Czas Kopiowania Porównania Czas Kopiowania Porównania Czas Kopiowania Porównania Czas Kopiowania Porównania
10 2 78 36 2 54 104 2 42 76 2 75 80 2 41 45
20 2 312 124 2 164 320 2 90 210 3 303 311 2 112 116
30 3 705 265 3 335 599 3 150 358 3 696 697 2 189 193
40 3 1254 458 4 560 942 4 213 519 5 1233 1231 5 292 298
50 5 1956 702 5 820 1358 5 252 694 10 1926 1917 3 398 404
60 5 2895 1025 7 1169 1843 5 306 864 8 2874 2788 3 497 503
70 6 4077 1429 7 1613 2429 6 381 1061 11 4044 3833 4 612 618
80 7 5139 1793 9 1991 2956 6 417 1226 11 5097 4939 7 730 736
90 10 6417 2229 11 2451 3572 8 468 1413 15 6387 6224 5 883 889
100 10 7920 2740 10 2976 4256 9 504 1588 18 7881 7677 5 980 986
200 32 31860 10820 33 11358 14292 20 1107 3645 81 31809 30703 11 2351 2359
300 86 70347 23749 68 24595 29307 34 1719 5835 152 70260 68570 18 3954 3962
400 137 127485 42895 116 44081 50665 50 2379 8167 253 127365 122655 24 5637 5647
500 198 197076 66192 173 67654 76256 71 2943 10549 405 196956 190902 30 7083 7093
600 276 281871 94557 236 96331 106999 102 3561 13033 542 281733 274211 39 9231 9241
700 370 380565 127555 315 129585 142299 116 4095 15413 742 380403 372151 45 10871 10881
800 486 504816 169072 408 171418 186209 144 4719 17914 957 504630 488610 54 12924 12934
900 641 639126 213942 527 216590 233509 182 5322 20445 1252 638916 618422 62 14730 14740
1000 764 786696 263232 623 266198 285365 228 5949 23120 1516 786459 762653 73 17267 17277
2000 3100 3154398 1053466 2550 1059430 1101773 829 11946 50293 6412 3153948 3052316 170 39511 39523
3000 6844 7076067 2361689 5465 2370611 2437703 1517 17883 78979 13337 7075398 6859966 266 62482 62494
4000 12125 12601869 4204623 9704 4216465 4309258 2598 23763 108560 23717 12600954 12202318 382 90166 90180
5000 18987 19743405 6586135 15085 6601091 6720044 4023 29934 138891 36997 19742403 19083301 484 116790 116804
6000 27263 28344717 9454239 21723 9472159 9618237 5612 35880 169962 53259 28343502 27450834 598 142389 142403
7000 37010 38530734 12850578 29442 12871422 13044872 7592 41766 201220 72258 38529249 37346583 723 171104 171118
8000 48441 50233125 16752375 38271 16776301 16977633 9702 47889 233225 94111 50231424 48747808 837 199870 199884
9000 61001 63670827 21232609 48402 21259479 21488870 12190 53805 265200 119452 63668904 61727468 955 228225 228239
10000 75536 78639666 26223222 59927 26253032 26511103 15074 59715 297790 147914 78637503 76217501 1108 265723 265739
11000 91101 95086206 31706402 72228 31739346 32026240 18057 65916 330814 180582 95083857 92200119 1236 294346 294362
12000 109143 113282370 37772790 86304 37808736 38124951 21416 71919 364138 214250 113279799 109765933 1366 326945 326961
13000 127326 132770847 44269949 100995 44308879 44654102 25148 77895 397122 252041 132768036 128762512 1481 353021 353037
14000 148138 154078242 51373414 117387 51415316 51790117 29985 83853 430658 293606 154075293 149365431 2056 391639 391655
15000 170447 176975826 59006942 135008 59051868 59456297 34683 89889 464322 343133 176972580 171498360 1794 422702 422718
16000 196737 201365193 67137731 156770 67185631 67620167 40262 95850 498390 384942 201361836 195128612 1922 452341 452357
17000 223711 227054994 75701998 180287 75752924 76217551 47444 101889 532520 436327 227051400 220192300 2041 486773 486789
18000 247847 254572125 84875375 200367 84929163 85424742 53674 107682 567265 494556 254568270 246865090 2206 523545 523561
19000 278315 283625592 94560864 222188 94617682 95143905 59776 113727 601954 551433 283621539 275050013 2329 550565 550581
20000 305799 314124927 104728309 242585 104788239 105343754 65215 119895 635414 598146 314120628 304716876 2434 576646 576662
21000 266810 115476165 116062890 71269 125853 670582 2634 629910 629926
22000 292016 126675312 127293187 76260 131877 705756 2764 664194 664210
23000 318852 138427876 139076987 83179 137427 740542 2919 699002 699018
24000 347511 150770011 151449740 91156 143895 775628 3059 730538 730554
25000 376669 163452181 164163641 98107 149811 811275 3230 777520 777536
26000 407851 176625493 177368476 106083 155841 846828 3318 791793 791809
27000 439915 190655191 191429508 115150 161886 882207 3502 836013 836029
28000 474218 205119991 205926416 125246 167697 918126 3665 886032 886048
29000 508683 220040461 220878736 132451 173703 953982 3793 914168 914184
30000 545099 235661326 236531413 144141 179874 989965 4000 974607 974625
31000 151669 185847 1025829 4127 999153 999171
32000 161391 191799 1060648 4291 1025141 1025159
33000 172407 197871 1096314 4409 1056569 1056587
34000 184309 203595 1132919 4536 1091793 1091811
35000 192283 209880 1168790 4653 1105789 1105807
36000 203540 215835 1205771 4878 1181635 1181653
37000 217910 221856 1242034 5003 1199707 1199725
38000 226344 227826 1279203 5149 1228911 1228929
39000 238216 233721 1314983 5309 1273925 1273943
40000 253849 239721 1351502 5485 1303123 1303141
41000 262892 245838 1389214 5677 1374368 1374386
42000 280022 251751 1424845 5876 1390203 1390221
43000 290727 257778 1462343 5940 1426462 1426480
44000 303064 263865 1499184 6117 1474856 1474874
45000 317456 269676 1537767 6284 1508851 1508869
46000 331335 275847 1573671 6436 1537330 1537348
47000 349167 281763 1610618 6649 1619990 1620008
48000 358875 287838 1647808 6779 1644730 1644748
49000 378163 293754 1684350 6990 1695341 1695359
50000 389126 299733 1722692 7161 1745576 1745594
60000 564177 359763 2097724 8704 2087182 2087200
70000 774474 419820 2477887 10469 2535579 2535597
80000 1001323 479721 2862606 12192 2992870 2992888
90000 1261884 539736 3251648 14181 3486834 3486854
100000 1564198 599793 3644146 15918 3883891 3883911
110000 17656 4331994 4332014
120000 19411 4763362 4763382
130000 21387 5266993 5267013
140000 23288 5685491 5685511
150000 25199 6197523 6197543
160000 26935 6600107 6600127
170000 28986 7083336 7083356
180000 30635 7504744 7504764
190000 33015 8143288 8143308
200000 35113 8647836 8647856
300000 59509 13897230 13897252
400000 78564 19975262 19975284
500000 100303 25117910 25117932
600000 123415 31020609 31020631
700000 148240 37701317 37701339
800000 174271 45240677 45240701
900000 198534 51824015 51824039
1000000 226077 58363366 58363390
BI algorytm generujący 1
Liczność
Wstawianie2 Wstawianie4 Wstawianie5 Bąbelkowe Shella
Czas Kopiowania Porównania Czas Kopiowania Porównania Czas Kopiowania Porównania Czas Kopiowania Porównania Czas Kopiowania Porównania
10 2 69 33 7 49 105 3 39 79 2 39 68 4 41 45
20 7 342 134 9 184 332 13 105 217 7 294 308 4 118 122
30 9 633 241 12 319 579 7 162 366 10 600 665 5 187 191
40 15 1281 467 14 575 953 8 222 524 25 1209 1223 7 350 356
50 29 2094 748 24 888 1400 14 285 701 45 2028 1951 9 436 442
60 33 3159 1113 24 1283 1924 15 345 870 38 3051 2847 10 531 537
70 42 3831 1347 34 1539 2334 16 393 1052 49 3702 3719 11 669 675
80 51 4746 1662 33 1892 2824 19 465 1241 62 4635 4785 13 772 778
90 60 5880 2050 44 2308 3386 23 522 1424 79 5730 6005 15 906 912
100 74 7044 2448 46 2732 3973 26 576 1621 86 6891 7347 17 1055 1061
200 296 29508 10036 141 10622 13493 66 1179 3654 359 29208 29836 39 2576 2584
300 632 63411 21437 274 22315 26991 117 1767 5847 789 62928 66126 61 4276 4284
400 1178 119025 40075 463 41263 47843 209 2382 8166 1451 118383 119661 89 6223 6233
500 1841 183486 61662 697 63142 71682 269 2970 10514 2209 182682 186144 117 8168 8178
600 2639 260919 87573 1008 89353 99929 366 3570 12950 3170 259938 266946 150 10239 10249
700 3594 358239 120113 1304 122199 134830 478 4179 15414 4344 357225 364425 180 12253 12263
800 4721 473112 158504 1692 160890 175649 602 4779 17942 5684 471894 477698 213 14598 14608
900 6003 608733 203811 2274 206499 223432 788 5382 20519 7328 607401 607917 248 17012 17022
1000 7520 757260 253420 2673 256404 275511 904 5976 23087 9030 755778 752426 270 19008 19018
2000 29097 2946198 984066 10008 990048 1032329 3145 11973 50258 35549 2943294 2982098 640 45141 45153
3000 67165 6790872 2266624 22751 2275586 2342554 7054 17943 78915 81988 6786645 6763715 1015 71860 71872
4000 118116 11909637 3973879 39743 3985847 4078441 12676 23952 108550 143671 11903916 11969972 1507 107614 107628
5000 185907 18781260 6265420 62757 6280396 6399318 19217 29964 138890 225751 18773892 18760464 1895 134294 134308
6000 269596 27206175 9074725 92115 9092705 9238667 28132 35970 169936 327218 27197271 27068757 2352 166142 166156
7000 365662 36814599 12278533 122197 12299511 12472863 38317 41967 201323 444573 36804201 36771567 2840 201816 201830
8000 474847 47869257 15964419 158542 15988399 16189551 48367 47970 233126 578280 47857461 47956487 3336 237781 237795
9000 599145 60464655 20163885 200469 20190863 20420159 60943 53967 265267 730132 60451128 60654876 3907 276772 276786
10000 738622 74502033 24844011 248516 24873997 25131803 76201 59979 297789 903730 74487111 74834037 4453 318138 318154
11000 893096 89988285 30007095 298574 30040071 30326809 90397 65964 330706 1090787 89972025 90496175 4925 351767 351783
12000 1068373 107643183 35893061 358305 35929047 36244963 108004 71979 363899 1300591 107625327 107881109 5284 373092 373108
13000 1251136 126260112 42099704 417581 42138682 42483872 126123 77967 397161 1525756 126241128 126586876 5922 418202 418218
14000 1456306 146769897 48937299 486674 48979277 49354069 147364 83967 430763 1772568 146748654 146923218 6593 465748 465764
15000 1663382 168015876 56020292 555104 56065272 56469782 167164 89970 464484 2030336 167993973 168505491 7097 501834 501850
16000 1898220 191476794 63841598 633218 63889574 64324034 191023 95964 498428 2317527 191452974 191825658 7820 555178 555194
17000 2148530 216714018 72255006 715952 72305980 72770372 215295 101961 532357 2614889 216688773 216738091 8265 586141 586157
18000 2410017 243169227 81074409 805592 81128385 81623073 241866 107964 566656 2931661 243142449 243056483 8732 620369 620385
19000 2689699 271368369 90475123 900041 90532093 91057245 269386 113955 601111 3278349 271340187 270956229 9342 662361 662377
20000 2985337 301555662 100538554 994570 100598522 101154262 298503 119952 635696 3630176 301525986 300518662 9854 702824 702840
Zebrano również dane dla typu danych BI dla procedur generujących 2-5. Dane te nie były jednak
wykorzystywane w sprawozdaniu, jako że nie prowadziły do żadnych nowych wniosków, dlatego
pomijam ich tabele.