Սանրաձև տեսակավորում

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Սանրաձև տեսակավորում
Տեսակտեսակավորման ալգորիթմ
Տվյալների կառուցվածք
Վատագույն դեպքում կատարումը[1]
Լավագույն դեպքում կատարումը
Օգտագործում էզանգված

Սանրային դասակարգում

Սանրային դասակարգումը (Անգլ. comb sort), դա ալգորիթմի բավականին պարզունակ դասակարգում է, ի սկզբանե նախագծված 1980 թվականին Վլադզիմեժ Դարիսեվիչի կողմից։ Ավելի ուշ այն վերաբացվեց և հայտնի դարձավ Ստիվեն Լեյսի և Ռիչարդ Բոկսի հոդվածում Byte Magazine ամսագրում 1991 թվականի ապրիլին։ Սանրային դասակարգումը շատ ավելի է բարելավում պղպջակային դասակարգումը, մրցում է ալգորիթմների հետ, արագ դասակարգման նման։ Հիմնական մտահղացումը, վերացնել կրիաներին, կամ ցածր արժեքները ցուցակի վերջում, որոնք ծայրահեղ դանդաղեցնում են պղպջակային դասակարգումը (նապաստակներ, մեծ արժեքներ ցուցակի սկզբում, խնդիրներ չեն առաջացնում պղպջակային դասակարգման համար)։

Երբ երկու էլեմենտներ համեմատվում են, ժամանակամիջոցը (հեռավորությունը յուրաքանչյուրից) հավասար է։ Սանրային տեսակավորման հիմնական գաղափարն այն է, որ այդ ժամանակահատվածը կարող է լինել ավելի երկար, քան միավոր (Շելլի դասակարգումը նույնպես հիմնված է այդ գաղափարի հիման վրա, բայց այն հանդիսանում է ներդրումների դասակարգման մոդիֆիկացիա, այլ ոչ թե պղպջակային դասակարգում)։

Ջավա[խմբագրել | խմբագրել կոդը]

  public static <E extends Comparable<? super E» void sort(E[] input) {
    int gap = input.length;
    boolean swapped = true;
    while (gap > 1 || swapped) {
        if (gap > 1) 
            gap = (int) (gap / 1.247330950103979);
 
        int i = 0;
        swapped = false;
        while (i + gap < input.length) {
            if (input[i].compareTo(input[i + gap]) > 0) {
                E t = input[i];
                input[i] = input[i + gap];
                input[i + gap] = t;
                swapped = true;
            }
            i++;
        }
    }
}

C[խմբագրել | խմբագրել կոդը]

  void combsort(int *arr, int size) {
    float shrink_factor = 1.247330950103979;
    int gap = size, swapped = 1, swap, i;
 
    while ((gap > 1) || swapped) {
        if (gap > 1) 
           gap = gap / shrink_factor;
 
        swapped = 0; 
        i = 0;
 
        while ((gap + i) < size) {
            if (arr[i] - arr[i + gap] > 0) {
                swap = arr[i];
                arr[i] = arr[i + gap];
                arr[i + gap] = swap;
                swapped = 1;
            }
            ++i;
        }
    }
}

C++[խմբագրել | խմբագրել կոդը]

  template<class ForwardIterator>
  void combsort ( ForwardIterator first, ForwardIterator last )
  {
    static const double shrink_factor = 1.247330950103979;
    typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_type;
    difference_type gap = std::distance(first, last);
    bool swaps = true;
 
    while ( (gap > 1) || (swaps == true) ){
        if (gap > 1)
            gap = static_cast<difference_type>(gap/shrink_factor);
 
        swaps = false;
        ForwardIterator itLeft(first);
        ForwardIterator itRight(first); std::advance(itRight, gap);
 
        for ( ; itRight!=last; ++itLeft, ++itRight ){
            if ( (*itRight) < (*itLeft) ){
                std::iter_swap(itLeft, itRight);
                swaps = true;
            }
        }
    }
}

Ծանոթագրություններ[խմբագրել | խմբագրել կոդը]

  1. Brejová B. Analyzing variants of Shellsort // Inform. Process. Lett.Elsevier BV, 2001. — Vol. 79, Iss. 5. — P. 223—227. — ISSN 0020-0190; 1872-6119doi:10.1016/S0020-0190(00)00223-4

Նշումներ[խմբագրել | խմբագրել կոդը]

↑ Lacey S., Box R. A Fast, Easy Sort: A novel enhancement makes a bubble sort into one of the fastest sorting routines (англ.) // Byte. — Апрель 1991. — Vol. 16. — № 4. — P. 315—320. — ISSN 0360-528.