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

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

Սանրաձև տեսակավորում
Տեսակ	տեսակավորման ալգորիթմ
Տվյալների կառուցվածք	$O(1)$
Վատագույն դեպքում կատարումը	$O(n^{2})$
Լավագույն դեպքում կատարումը	$O(n\log n)$
Օգտագործում է	զանգված

Սանրային դասակարգումը (Անգլ. 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;
            }
        }
    }
}

Նշումներ

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