8 mavzu: Murakkab saralash algoritmlari. Amaliy dasturlash Reja



Download 184,65 Kb.
bet10/14
Sana06.08.2022
Hajmi184,65 Kb.
#846556
1   ...   6   7   8   9   10   11   12   13   14
Bog'liq
8-m

Saralash algoritmlari taqqoslash. Buning uchun barcha yaaratilgan saralash algoritmlarini bir faylga joylashtiramiz. Bularni taqqoslash uchun elementlar soni navbat bilan oshirib boramiz va natijalari sonli, grafikli keltiramiz.
8.1-jadval. Saralash algoritmlar ro‘yxati.



Saralash algoritmning nomi

funksiyasi

1

Havo sharcha kabi saralash

void bubblesort(int* l, int* r)

2

Shaker saralash

void shakersort(int* l, int* r)

3

Taroqsimon caralash

void combsort(int* l, int* r)

4

Qo‘shish orqali saralash

void insertionsort(int* l, int* r)

5

Shell caralash

void shellsort(int* l, int* r)
void shellsorthib(int* l, int* r)







void shellsortpratt(int* l, int* r) void myshell_one(int* l, int* r) void myshell_two(int* l, int* r)
void myshell_three(int* l, int* r)

6

Iearxik saralash

void treesort(int* l, int* r)

7

Nav saralash

void gnomesort(int* l, int* r)

8

Tanlash orqali saralash

void selectionsort(int* l, int* r)

9

Piramida kabi saralash

void heapsort(int* l, int* r)

10

Tezkor saralash

void quicksort(int* l, int* r)
void quickinssort(int* l, int* r)

11

Birlashtirish orqali saralash

void mergesort(int* l, int* r)
void mergeinssort(int* l, int* r)

12

Blok orqali saralash

void newbucketsort(int* l, int* r)

13

Bitli saralash (LSD)

void radixsort(int* l, int* r)

14

Bitli saralash (MSD)

void radixsortmsd(int* l, int* r)

15

Bitonik saralash

void bitonicsort(int* l, int* r)

16

Timsort saralash

void timsort(int* l, int* r)

Bu algoritmlarni vaqt bo‘yicha taqqoslash uchun tasodifiy sonlar bilan massivni to‘ldiramiz, tasodifiy sonlarni ham guruhlarga ajratamiz, xonalar bo‘yicha, massiv elementlar sonini ham 100 ta dan 100000 tagacha tanlab olamiz.

Birinchi test. Massiv elementlari soni 100, 1000, 10000 ta va tasodifiy sonlarning eng kattasi 1000:Elementlar soni:100
Random eng katta soni:1000
bubblesort(a,b) => 189949
shakersort(a,b) => 9912
combsort(a,b) => 10017
insertionsort(a,b) => 9962
shellsort(a,b) => 9996
shellsorthib(a,b) => 9983
shellsortpratt(a,b) => 10001
myshell_one(a,b) => 10013
myshell_two(a,b) => 10000
myshell_three(a,b) => 9983
treesort(a,b) => 600071
gnomesort(a,b) => 6510
selectionsort(a,b) => 29963
heapsort(a,b) => 160055
quicksort(a,b) => 10013

Elementlar soni:1000 Random eng katta soni:1000
bubblesort(a,b) => 509917
shakersort(a,b) => 8523
combsort(a,b) => 9949
insertionsort(a,b) => 12012
shellsort(a,b) => 12536
shellsorthib(a,b) => 9983
shellsortpratt(a,b) => 10039
myshell_one(a,b) => 10026
myshell_two(a,b) => 9951
myshell_three(a,b) => 10056
treesort(a,b) => 940049
gnomesort(a,b) => 10044
selectionsort(a,b) => 79987
heapsort(a,b) => 190026
quicksort(a,b) => 10001

Elementlar soni:10000 Random eng katta soni:1000
bubblesort(a,b) => 12229978
shakersort(a,b) => 10000
combsort(a,b) => 19984
insertionsort(a,b) => 25365
shellsort(a,b) => 20009
shellsorthib(a,b) => 10026
shellsortpratt(a,b) => 40028
myshell_one(a,b) => 10044
myshell_two(a,b) => 9996
myshell_three(a,b) => 20044
treesort(a,b) => 7690211
gnomesort(a,b) => 120041
selectionsort(a,b) => 2090445
heapsort(a,b) => 460513
quicksort(a,b) => 10462

quickinssort(a,b) => 9979
mergesort(a,b) => 10120
mergeinssort(a,b) => 9975
newbucketsort(a,b) => 20014
radixsort(a,b) => 10060
radixsortmsd(a,b) => 19992
bitonicsort(a,b) => 29988
timsort(a,b) => 149973

quickinssort(a,b) => 9992
mergesort(a,b) => 20005
mergeinssort(a,b) => 10004
newbucketsort(a,b) => 19967
radixsort(a,b) => 30057
radixsortmsd(a,b) => 20031
bitonicsort(a,b) => 69974
timsort(a,b) => 190021

quickinssort(a,b) => 10020
mergesort(a,b) => 29924
mergeinssort(a,b) => 9979
newbucketsort(a,b) => 19959
radixsort(a,b) => 19980
radixsortmsd(a,b) => 20249
bitonicsort(a,b) => 220502
timsort(a,b) => 140443


8.1-rasm. Saralash algoritmlarini taqqoslash.
Ushbu rasmda keltirilgan taqqoslash natijariga Shaker, blok orqali, bitli (MSD), bitonik saralash algoritmlarining elementlarning sonini o‘zgarish bilan saralash uchun sarflanadigan vaqtni o‘zgarishini kuzatishimiz mumkin.
Ikkinchi test. Massiv elementlari soni 100, 1000, 10000 ta va tasodifiy sonlarning eng kattasi 10000:

Elementlar soni:100
Random eng katta soni:10000
bubblesort(a,b) => 230011
shakersort(a,b) => 9889
combsort(a,b) => 10018
insertionsort(a,b) => 9562
shellsort(a,b) => 10018
shellsorthib(a,b) => 10000
shellsortpratt(a,b) => 8452
myshell_one(a,b) => 10022
myshell_two(a,b) => 9988
myshell_three(a,b) => 12001
treesort(a,b) => 660039
gnomesort(a,b) => 7563
selectionsort(a,b) => 29997
heapsort(a,b) => 170016
quicksort(a,b) => 9562
quickinssort(a,b) => 9996
mergesort(a,b) => 10069
mergeinssort(a,b) => 8996
newbucketsort(a,b) => 20060
radixsort(a,b) => 10005

Elementlar soni:1000
Random eng katta soni:10000
bubblesort(a,b) => 509982
shakersort(a,b) => 9956
combsort(a,b) => 10009
insertionsort(a,b) => 9986
shellsort(a,b) => 9992
shellsorthib(a,b) => 10021
shellsortpratt(a,b) => 9992
myshell_one(a,b) => 10025
myshell_two(a,b) => 10360
myshell_three(a,b) => 15201
treesort(a,b) => 1030011
gnomesort(a,b) => 8624
selectionsort(a,b) => 99992
heapsort(a,b) => 210079
quicksort(a,b) => 10009
quickinssort(a,b) => 10005
mergesort(a,b) => 10000
mergeinssort(a,b) => 9996
newbucketsort(a,b) => 20040
radixsort(a,b) => 10018

Elementlar soni:10000 Random eng katta soni:10000
bubblesort(a,b) => 12139952
shakersort(a,b) => 10056
combsort(a,b) => 20001
insertionsort(a,b) => 10009
shellsort(a,b) => 20001
shellsorthib(a,b) => 20018
shellsortpratt(a,b) => 40006
myshell_one(a,b) => 10017
myshell_two(a,b) => 10005
myshell_three(a,b) => 20018
treesort(a,b) => 7700494
gnomesort(a,b) => 11254
selectionsort(a,b) => 1950542
heapsort(a,b) => 400520
quicksort(a,b) => 10210
quickinssort(a,b) => 10004
mergesort(a,b) => 30318
mergeinssort(a,b) => 20502
newbucketsort(a,b) => 19954
radixsort(a,b) => 30075

radixsortmsd(a,b) => 10013
bitonicsort(a,b) => 30014
timsort(a,b) => 179974

radixsortmsd(a,b) => 9954
bitonicsort(a,b) => 59934
timsort(a,b) => 150012

radixsortmsd(a,b) => 29680
bitonicsort(a,b) => 229981
timsort(a,b) => 149973


8.2-rasm. Saralash algoritmlarini taqqoslash.
Ushbu rasmda keltirilgan taqqoslash natijariga Shaker, blok orqali, bitli (MSD), bitonik saralash algoritmlarining elementlarning sonini o‘zgarish bilan saralash uchun sarflanadigan vaqtni o‘zgarishini kuzatishimiz mumkin.
Uchinchi test. Massiv elementlari soni 100000 ta va tasodifiy sonlarning eng kattasi 100, 10000, 100000:

Elementlar soni:100000 Random eng katta soni:100
bubblesort(a,b) => 977222383
shakersort(a,b) => 10035
combsort(a,b) => 190531
insertionsort(a,b) => 10514
shellsort(a,b) => 110523
shellsorthib(a,b) => 119988
shellsortpratt(a,b) => 439987
myshell_one(a,b) => 59994
myshell_two(a,b) => 69969
myshell_three(a,b) => 60028
treesort(a,b) => 81039998
gnomesort(a,b) => 10299
selectionsort(a,b) => 249475206
heapsort(a,b) => 7190050
quicksort(a,b) => 340165
quickinssort(a,b) => 209933
mergesort(a,b) => 439970

Elementlar soni:100000 Random eng katta soni:10000
bubblesort(a,b) => 1413069355
shakersort(a,b) => 20103
combsort(a,b) => 589990
insertionsort(a,b) => 30142
shellsort(a,b) => 340080
shellsorthib(a,b) => 299988
shellsortpratt(a,b) => 1020010
myshell_one(a,b) => 150166
myshell_two(a,b) => 159905
myshell_three(a,b) => 140058
treesort(a,b) => 212009993
gnomesort(a,b) => 20014
selectionsort(a,b) => 338029149
heapsort(a,b) => 6460020
quicksort(a,b) => 229943
quickinssort(a,b) => 110074
mergesort(a,b) => 520012

Elementlar soni:100000 Random eng katta soni:100000
bubblesort(a,b) => 1522791244
shakersort(a,b) => 10022
combsort(a,b) => 420097
insertionsort(a,b) => 20130
shellsort(a,b) => 240105
shellsorthib(a,b) => 239879
shellsortpratt(a,b) => 950139
myshell_one(a,b) => 140276
myshell_two(a,b) => 150114
myshell_three(a,b) => 139913
treesort(a,b) => 173539873
gnomesort(a,b) => 29920
selectionsort(a,b) => 346130116
heapsort(a,b) => 7080178
quicksort(a,b) => 200168
quickinssort(a,b) => 110095
mergesort(a,b) => 500015

mergeinssort(a,b) => 259845
newbucketsort(a,b) => 119831
radixsort(a,b) => 349931
radixsortmsd(a,b) => 320020
bitonicsort(a,b) => 4389857
timsort(a,b) => 469881

mergeinssort(a,b) => 340191
newbucketsort(a,b) => 110005
radixsort(a,b) => 400045
radixsortmsd(a,b) => 429952
bitonicsort(a,b) => 5839897
timsort(a,b) => 450090

mergeinssort(a,b) => 289851
newbucketsort(a,b) => 150140
radixsort(a,b) => 349846
radixsortmsd(a,b) => 570139
bitonicsort(a,b) => 5079891
timsort(a,b) => 360411


8.3-rasm. Saralash algoritmlarini taqqoslash.
Ushbu rasmda keltirilgan taqqoslash natijariga Shaker, blok orqali, bitli (MSD) saralash algoritmlarining elementlarning qiymatini o‘zgartirganda saralash uchun sarflanadigan vaqtni o‘zgarishini kuzatishimiz mumkin.


Download 184,65 Kb.

Do'stlaringiz bilan baham:
1   ...   6   7   8   9   10   11   12   13   14




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish