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

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


== Պարզ ալգորիթմ ==
Սա ալգորիթմի պարզագույն տեսակն է։ Ստեղծել զրոներից բաղկացած օժանդակ C[0..k - 1] զանգված, այնուհետև հաջորդականությամբ կարդալ մուտքային A մատրիցի էլեմենտները, յուրաքանչյուր A[i] համար ընդլայնել C[A[i]] մեկ միավորով։ Այժմ բավարար է անցնել C մատրիցով, յուրաքանչյուր 
  
    
      
        j
        ∈
        {
        0
        ,
        .
        .
        .
        ,
        k
        −
        1
        }
      
    
    {\displaystyle 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
        ∈
        {
        0
        ,
        .
        .
        .
        ,
        k
        −
        1
        }
      
    
    {\displaystyle 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|, իսկ հակառակ գրանցման դեպքում՝ դուրս բերել։


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


== Հաշվողական տեսակավորման քառակուսային ալգորիթմ ==
Այստեղ օգտագործվում են մուտքային A զանգվածը և B օժանդակ զանգվածը՝ տեսակավորված բազմության համար։ Ալգորիթմում անհրաժեշտ է A[i] մուտքային զանգվածի յուրաքանչյուր էլեմենտի համար հաշվարկել 
  
    
      
        
          c
          
            1
          
        
      
    
    {\displaystyle c_{1}}
  -ից փոքր էլեմենտների թիվը, և դրան հավասար, բայց 
  
    
      
        
          c
          
            2
          
        
      
    
    {\displaystyle c_{2}}
   (
  
    
      
        c
        =
        
          c
          
            1
          
        
        +
        
          c
          
            2
          
        
      
    
    {\displaystyle 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];


=== Վերլուծություն ===
Ակնհայտ է, որ ալգորիթմի ժամաննակավոր գնահատականը հավասար է 
  
    
      
        Θ
        (
        
          n
          
            2
          
        
        )
      
    
    {\displaystyle \Theta (n^{2})}
  , հիշողությունը՝ 
  
    
      
        Θ
        (
        n
        )
      
    
    {\displaystyle \Theta (n)}
  ։


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


=== C ===
Պարզ ալգորիթմ։


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


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


== Դիտեք նաև ==
Տեսակավորման ալգորիթմ
O-մեծ
Ալգորիթմի ժամանակավոր բարդություն


== Գրականություն ==
Ананий В. Левитин, Գլուխ 7. ժամանակավոր փոխզիջում։ Հաշվողական տեսակավորում,  Ալգորիթմեր։ ներածություն և վերլուծություն, Մ., ««Վիլյամս»» — 307 - 310, էջեր 307 - 310 — 307 - 310 էջ, ISBN 5-8459-0987-2։Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд, Գլուխ 8. Տեսակավորում գծային ժամանակի համար,  Ալգորիթմեր։ ներածություն և վերլուծություն (2-րդ հրատարակություն), Մ., ««վիլյամս»» — 224 - 226, էջեր 224 - 226 — 224 - 226 էջ, ISBN 5-8459-0857-4։


== Հղումներ ==
visualiser1 Archived 2009-08-12 at the Wayback Machine. - Java-аплет.
visualiser2 Archived 2009-08-12 at the Wayback Machine. - Java-аплет.Կաղապար:Տեսակավորման ալգորիթմ