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.
|
