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

Վիքիպեդիայից՝ ազատ հանրագիտարանից

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

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

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

Բովանդակություն

Ջավա[խմբագրել]

  public static <E extends Comparable<? supervoid 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;
            }
        }
    }
}

Նշումներ[խմբագրել]

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