Հաշվողական տեսակավորում

Հաշվողական տեսակավորումը տեսակավորման ալգորիթմ է, որում օգտագործվում է տեսակավորվող զանգվածի թվերի շարքը` համընկնող էլեմենտների տեսակավորման համար: Հաշվողական տեսակավորման կիրառությունը ամբողջական է միայն այն ժամանակ, երբ տեսակավորվող թվերն ունեն հնարավոր նշանակության շարքեր, որը բավականին փոքր է տեսակավորվող բազմության հետ համեմատած, օրինակ` 1000-ից փոքր միլիոն բնական թվեր: Ալգորիթմի արդյունավետությունը նվազում է, եթե մի քնի տարբեր էլեմենտների մեկ բջջի մեջ ընկնելու դեպքում անհրաժեշտ է լինում դրանք կրկին տեսակավորել: Բջջի ներսում տեսակավորման անհրաժեշտությունը կորցնում է ալգորիթմի իմաստը, քանի որ յուրաքանչյուր էլեմենտ ստիպված կլինենք դիտարկել մեկ անգամից ավելի: Ենթադրենք, որ մուտքային զանգվածը բաղկացած է $n$ հատ ամբողջ թվերից`0-ից $k - 1$ միջակայքում, որտեղ $k \in \mathbb N$: Հետագայում ալգորիթմը կընդհանրացվի կամայակն ամբողջ թվերի շարքի համար: Գոյություն ունեն մի քանի հաշվողական տեսակավորման ձևեր. ներքևում դիտարկված են երեք գծային և մեկ քառակուսային ձևեր: Վերջինս օգտագործում է այլ մոտեցում, բայց ունի նույն իմաստը:

Պարզ ալգորիթմ

Սա ալգորիթմի պարզագույն տեսակն է: Ստեղծել զրոներից բաղկացած օժանդակ C[0..k - 1] զանգված, այնուհետև հաջորդականությամբ կարդալ մուտքային A մատրիցի էլեմենտները, յուրաքանչյուր A[i] համար ընդլայնել C[A[i]] մեկ միավորով: Այժմ բավարար է անցնել C մատրիցով, յուրաքանչյուր $j \in \{0, ..., k - 1\}$ համար A մատրիցում համապատասխանաբար գրել j թիվը C[j] անգամ:

SimpleCountingSort
    for i = 0 to k - 1
        C[i] = 0;
    for i = 0 to n - 1
        C[A[i]] = C[A[i]] + 1;
    b = 0;
    for j = 0 to k - 1
        for i = 0 to C[j] - 1
            A[b] = j;
            b = b + 1;

Ցուցակով ալգորիթմ

Այս տարբերակը (անգլ.՝ pigeonhole sorting, count sort) օգտագործվում է, երբ մուտքին տրվում է տվյալների ստրուկտուրային զանգված, որն անհրաժեշտ է տեսակավորել ըստ բանալիների (key): Անհրաժեշտ է ստեղծել օժանդակ C[0..k - 1] զանգված, հետագայում յուրաքանչյուր C[i] կպարունակի մուտքային զանգվածի էլեմենտների ցանկը: Այնուհետև հերթականությամբ կարդալ մուտքային A զանգվածի էլեմենտները, յուրաքանչյուր A[i] ավելացնել C[A[i].key] զանգվածի մեջ: Վերջում անցնել C զանգվածով, յուրաքանչյուր $j \in \{0, ..., k - 1\}$ համար A զանգվածում համապատասխանաբար գրել C[j] էլեմենտները: Ալգորիթմը կայուն է.

ListCountingSort
    for i = 0 to k - 1
        C[i] = NULL;
    for i = 0 to n - 1
        C[A[i].key].add(A[i]);
    b = 0;
    for j = 0 to k - 1
        p = C[j];
        while p != NULL
            A[b] = p.data;
            p = p.next();
            b = b + 1;

Կայուն ալգորիթմ

Այս տարբերակում բացի մուտքային A զանգվածից անհրաժեշտ կլինեն երկու օժանդակ զանգվածներ` C[0..k - 1] հաշվիչի համար, և B[0..n - 1]` տեսակավորված զանգվածի համար: Սկզբում պետք է C զանգվածում լրացնել զրոներ, և յուրաքանչյուր A[i] համար C[A[i]] մեծացնել մեկով: Այնուհետև հաշվարկվում է էլեմենտների թիվը` ընթացիկից փոքր կամ հավասար: Դրա համար յուրաքանչյուր C[j], սկսած C[1]-ից, ընդլայնում են C[j - 1]-ով: Ալգորիթմի վերջին քայլում կարդում են մուտքային զանգվածը վերջից, C[A[i]] նշանակությունը փոքրացվում է մեկով, և յուրաքանչյուր B[C[A[i]]]-ում գրանցվում է code>A[i]: Ալգորիթմը կայուն է:

StableCountingSort
    for i = 0 to k - 1
        C[i] = 0;
    for i = 0 to n - 1
        C[A[i]] = C[A[i]] + 1;
    for j = 1 to k - 1
        C[j] = C[j] + C[j - 1];
    for i = n - 1 to 0
        C[A[i]] = C[A[i]] - 1;
        B[C[A[i]]] = A[i];

Կամայական ամբողջ թվերի շարքի ընդհանրացում

Այստեղ ծագում են մի քանի հարցեր. ինչ անել, եթե արժեքների (min и max) շարքերը նախապես հայտնի չեն: Ինչ անել, եթե մինիմալ արժեքները մեծ են զրոյից կամ տեսակավորվող տվյալներում առկա են բացասական թվեր: Առաջին հարցը կարելի է որոշել min-ի և max-ի գծային փնտրմամբ, որը չի ազդի ալգորիթմի ասիմետրիկայի վրա: Երկրորդ հարցը մի փոքր ավելի բարդ է: Եթե min-ը մեծ է զրոյից, ապա անհրաժեշտ է C զանգվածի հետ աշխատելիս A[i]-ից դուրս բերել min-ը, իսկ հակառակ դեպքում` ավելացնել: Բացասական թվերի առկայության դեպքում C զանգվածի հետ աշխատանքի ժամանակ պետք է A[i]-ին ավելացնել |min|, իսկ հակառակ գրանցման դեպքում` դուրս բերել:

Վերլուծություն

Առաջին երկու ալգորիթմերում առաջին երկու ցիկլերը աշխատում են համապատասխանաբար $\Theta(k)$ և $\Theta(n)$ համար, կրկնակի ցիկլը` $\Theta(n + k)$ համար: Երրորդ ալգորիթմում ցկլը զբաղեցնում են համապատասխանաբար $\Theta(k)$, $\Theta(n)$, $\Theta(k)$ և $\Theta(n)$: Արդյունքում` բոլոր երեք ալգորիթմերն էլ ունեն գծային ժամանակավոր $\Theta(n + k)$ աշխատունակություն: Առաջին երկու ալգորիթմերում օգտագործվող հիշողությունը հավասար է $\Theta(k)$, իսկ երրորդում` $\Theta(n + k)$:

Հաշվողական տեսակավորման քառակուսային ալգորիթմ

Այստեղ օգտագործվում են մուտքային A զանգվածը և B օժանդակ զանգվածը` տեսակավորված բազմության համար: Ալգորիթմում անհրաժեշտ է A[i] մուտքյին զանգվածի յուրաքանչյուր էլեմենտի համար հաշվարկել $c_1$-ից փոքր էլեմենտների թիվը, և դրան հավասար, բաըց $c_2$ ($c = c_1 + c_2$)-ից առաջ գտնվող էլեմենտների թիվը: Այնուհետև B[c] փոխանցել A[i]: Ալգորիթմը կայուն է:

SquareCountingSort
    for i = 0 to n - 1
        c = 0;
        for j = 0 to i - 1
            if A[j] <= A[i]
                c = c + 1;
        for j = i + 1 to n - 1
            if A[j] < A[i]
                c = c + 1;
        B[c] = A[i];

Վերլուծություն

Ակնհայտ է, որ ալգորիթմի ժամաննակավոր գնահատականը հավասար ը $\Theta(n^2)$, հիշողությունը` $\Theta(n)$:

Իրագործման օրինակներ

C

Պարզ ալգորիթմ:

void CountingSort (int *a, int n, int min, int max)
{
  int i, j, c;
  int *b;
  assert(n > 0);
  assert(min <= max);
  b = (int *)calloc(max - min + 1, sizeof(int));
  assert(b != NULL);
  for (i = 0; i <= n - 1; ++i) ++b[a[i] - min];
  for (j = min; j <= max; ++j)
  {
    c = b[j - min];
    while (c > 0)
    {
      *a = j; ++a; --c;
    }
  }
  free(b);
}

Բաղադրիչային Պասկալ

Պարզ ալգորիթմ

PROCEDURE CountingSort (VAR a: ARRAY OF INTEGER; min, max: INTEGER);
  VAR
    i, j, c: INTEGER;
    b: POINTER TO ARRAY OF INTEGER;
BEGIN
  ASSERT(min <= max);
  NEW(b, max - min + 1);
  FOR i := 0 TO LEN(a) - 1 DO INC(b[a[i] - min]) END;
  i := 0;
  FOR j := min TO max DO
    c := b[j - min];
    WHILE c > 0 DO
      a[i] := j; INC(i); DEC(c)
    END
  END
END CountingSort;

C#

Հաշվողական տեսակավորման քառակուսային ալգորիթմ

using System;
    class Program
    {
        static void Main(string[] args)
        {
            //զանգվածի գեներացում օրինակի համար
            Random rnd=new Random();
            int[] arr=(new int[100]).Select(x => rnd.Next(10)).ToArray();
            int[] b = new int[100];
            //ինքը` ալգորիթմը
            for (int i = 0; i < arr.Length ; i++)
            {
                int c = 0;
 
                for (int j = 0; j < i ; j++)
                {
                    if (arr[j] <= arr[i])
                    {
                        c++;
                    }
 
                }
 
                for (int j = i + 1; j < arr.Length ; j++)
                {
                    if (arr[j] < arr[i])
                    {
                        c++;
                    }
                }
 
                b[c] = arr[i];
            }
        }
    }

Դիտեք նաև

• Տեսակավորման ալգորիթմ
• O-մեծ
• Ալգորիթմի ժամանակավոր բարդություն

Գրականություն

• Ананий В. Левитин // Գլուխ 7. ժամանակավոր փոխզիջում: Հաշվողական տեսակավորում // Ալգորիթմեր: ներածություն և վերլուծություն // Կաղապար:Մ.: «Վիլյամս». — ISBN 5-8459-0987-2.

• Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд // Գլուխ 8. Տեսակավորում գծային ժամանակի համար // Ալգորիթմեր: ներածություն և վերլուծություն — 2-րդ հրատարակություն. // Կաղապար:Մ.: «վիլյամս». — ISBN 5-8459-0857-4.

Հղումներ

• visualiser1 — Java-аплет.
• visualiser2 — Java-аплет.