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

**Հաշվողական տեսակավորումը** տեսակավորման ալգորիթմ է, որում օգտագործվում է տեսակավորվող զանգվածի թվերի շարքը՝ համընկնող էլեմենտների տեսակավորման համար։ Հաշվողական տեսակավորման կիրառությունը ամբողջական է միայն այն ժամանակ, երբ տեսակավորվող թվերն ունեն հնարավոր նշանակության շարքեր, որը բավականին փոքր է տեսակավորվող բազմության հետ համեմատած, օրինակ՝ 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;`

## Ցուցակով ալգորիթմ
Այս տարբերակը () օգտագործվում է, երբ մուտքին տրվում է տվյալների ստրուկտուրային զանգված, որն անհրաժեշտ է տեսակավորել ըստ բանալիների (`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
Պարզ ալգորիթմ։

```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);
}
```


### [[Բաղադրիչային Պասկալ]]
Պարզ ալգորիթմ

```pascal
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#
Հաշվողական տեսակավորման քառակուսային ալգորիթմ

```csharp
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-մեծ
* Ալգորիթմի ժամանակավոր բարդություն

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

* 

## Արտաքին հղումներ
* Counting Sort visualization

Կատեգորիա:Դասակարգման ալգորիթմներ