• Birinchi test.
  • Ikkinchi test.
  • Uchinchi test.
  • Tiplarni dinamik tarzda




    Download 1,92 Mb.
    bet79/131
    Sana16.06.2024
    Hajmi1,92 Mb.
    #264063
    1   ...   75   76   77   78   79   80   81   82   ...   131
    Bog'liq
    Tiplarni dinamik tarzda

    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 1,92 Mb.
    1   ...   75   76   77   78   79   80   81   82   ...   131




    Download 1,92 Mb.