8 mavzu: Murakkab saralash algoritmlari. Amaliy dasturlash Reja

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.