Սկիզբ » Ուսումնական նյութեր » Ծրագրավորում » Ծրագրավորման լեզուներ » C և C++ » Մի քանի տարածված ալգորիթմների իրականացում C/C++ -ով:

Մի քանի տարածված ալգորիթմների իրականացում C/C++ -ով:

Հոդվածում  բերված են ծրագրավորման պրակտիկայում հաճախ կիրառվող մի քանի ալգորիթմներ: Ալգորիթմները փաստացի գրված են C լեզվով, բայց քանի որ դրանք համատեղելի լեզուներ են, ուստի նմանապես կկոմպիլացվեն նաև C++ կոմպիլյատորներով :

Binary Find երկուական որոնման ալգորիթմը իրենից ներկայացնում է տրված տարրի փնտրում նախապես տեսակավորված բազմության մեջ, երբ մեկ իտերացիայի ընթացքում բազմությունը կիսվում է երկու ենթաբազմությունների, այնպես, որ փնտրվող տարրը գտնվի դրանցից մեկում: Փնտրումը շարունակվում է քանի դեռ տրված տարրը և տրոհված երկու ենթաբազմությունների հատման տարրը չեն համընկել: Ալգորիթմի առավելություններից է փնտրման համեմատական արագությունը, իսկ թերությունն այն է, որ պահանջում է նախապես տեսակավորված բազմություն: Ալգորիթմն ունի լոգարիթմական բարդություն՝ O( log n):

int BinarFind(int* a, int size, int v)
{
    int temp = 0;
    int r = size - 1;
    int m;

    for(int l = 0; r < size; l <= r)
    {
        m = (l + r)/2;
        if(a[m] == v)
        {
            return l;
        }
        if(a[m] < v)
        {
            l = m + 1;
        }
        if(a[m] > v)
        {
            r = m - 1;
        }
     }
     return -1;
}

Linear find գծային փնտրման ալգորիթմը իրենից ներկայացնում է տրված բազմության մեջ տրված տարրի փնտրում, տարրի՝ բազմության մնացած տարրերի հետ հաջորդական համեմատումների միջոցով: Փնտրումը կատարվում է, քանի դեռ տրված տարրը չի համընկել բազմության որևէ տարրի հետ:  Առավելություններն են`

1. չի պահանջվում է հավելյալ հիշողություն,

2. չի պահանջվում նախապես տեսակավորված բազմություն,

3. չի պահանջում հավելյալ նախնական մշակումներ:

Թերություններն են`

1. փնտրման արդյունավետությամբ զիջում է այլ փնտրման ալգորիթմներին:

Գծային փնտրման ալգորիթմի ալգորիթմական բարդությունը O(n) է:

int LinearSearch(char *items, int count, char key)
{
  int t;

  for(t=0; t < count; ++t)
  {
    if(key == items[t])
    {
      return t;
    }
  }
  return -1;
}

Select Sort տեսակավորման ալգորիթմ է, երբ տեսակավորման ամեն քայլի ընթացքում բազմությունից ընտրվում է նվազագույն տարրը և կատարվում է տեղափախություն, այդ տարրի և դեռ չտեսակավորված ենթաբազմության առաջին տարրի միջև: Կատարվում է այնքան, քանի դեռ ամբողջ բազմությունը տեսակավորված չէ: Ալգորիթմի հիմնական բնութագրիչն այն է, որ տեսակավորման ընթացքում ունենում ենք երկու միմյանցից անկախ ենթաբազմություների բազմություն, որը բաղկացած է արդեն տեսակավորված և չտեսակավորված ենթաբազմություններից: Ալգորիթմի ալգորիթմական բարդությունը O(n^2) Է:

void SelectSort(int* a ,int size)
{
    int min = 0;
    int temp = 0;
    int c = 0;
    int j = 0;

    for(int i = 0; i < size; i++)
    {
        min = i;
        for(j = i + 1; j < size; j++)
        {
            if(a[j] < a[min])
            {
                min = j;
            }
         }
      c = a[min];
      a[min] = a[i];
      a[i] = c;
      }            
}

 Insert Sort տեսակավորման ալգորիթմ է, որի հիմնական իմաստը կայանում է հետևյալում. ունենք արդեն տեսակավորված մաս, որում հերթական տարրը տեղադրվում է այնպես, որպեսզի չխախտվի տեսակավորումը: Սկզբում տեսակավորվում է բազմության առաջին երկու տարրերը, այնուհետև այդ՝ արդեն տեսակավորված բազմության մեջ է տեղադրվում երրորդ էլէմենտը և այդպես մինչև բազմության վերջը: Ի տարբերություն նախորդ ալգորիթմի (select sort -ի ) տեսակավորման ընթացքում տարրերի՝ միմյանց հետ համեմատումների քանակը կախված է բազմության նախնական տեսակավորման աստիճանից: Ալգորիթմի ալգորիթմական բարդությունը O(n^2) Է:

void InsertSort(int*a, int size)
{
    int i = 0;
    int j = 0;
    int temp; = 0;
    for (i = 1; i < size; i++)
    {
        temp = a[i];
        for (j = i - 1; j >= 0; j--)
        {
            if (a[j] < temp)
            {
                break;
            }
            a[j+1] = a[j];
            a[j]= temp;
        }
     }     
}

Shell Sort Շելի տեսակավորման ալգորիթմը իրենից ներկայացնում է հետևյալը. մուտքային բազմությունը տրոհվում է m ենթաբազմությունների, որոնցից յուրաքանչյուրի տարրերն միմյանց նկատմամբ ունեն n քայլի հեռավորություն: Սկզբում տրոհումից առաջացած յուրաքանչյուր ենթաբազմություն տեսակավորվում է առանձին օգտագործելով օրինակ insert sort – ալգորիթմը, այնուհետև ընտրվում է ավելի փոքր քայլ և ալգորիթմը կրկնվում է: Սովորաբար քայլերի վեկտորը ընտրվում է հետևյալ տարրերից և հաջորդականությամբ՝ {9, 5, 3, 2, 1}: Այսինքն սկզբում մուտքային բազմությունից ընտրվում է միմյանցից 9 քայլ հեռավորությամբ տարրերի ենթաբազմություն և տեսակավորվում է օրինակ insert sort – ալգորիթմով, հետո նույնը կրկնվում է 5, 3, 2, 1 քայլերի համար: Վատագույն դեպքում ալգորիթմի բարդությունը O(n3/2) Է: Ալգորիթմի բարդության լրիվ վերլուծության մասին կարող էք կարդալ Կնուտի -ի երրորդ հատորում 😉 :

void ShellSort(int* a, int size)
{
    int temp = 0;
    int step = 0;
    int b[] = {9, 5, 3, 2, 1};

    for(int i = 0; i < 5; i++)
    {
        step = b[i];
        for(int j = step; j < size; j++)
        {
            temp = a[j];
            for(int k = j - step; k >= 0; k = k - step)
            {
                if(a[k] < temp)
                {
                    break;
                }
                a[k + step] = a[k];
                a[k] = temp;
            }

         }
    }    
}

Quick Sort տեսակավորման ալգորիթմը ներկայումս համարվում է ամենալավ տեսակավորման ալգորիթմներից մեկը: Հիմնական գործողությունը կայանում է հենակետային տարրի ընտրման և դրա միջոցով մուտքային բազմությունը երկու մասի տրոհելու մեջ: Բոլոր տարրերը, որոնք փոքր կամ հավասար են հենակետային տարրից տեղափոխվում են ելքային բազմության մի մաս, իսկ այն տարրերը, որոնք մեծ են՝ տեղափախվում են ելքային բազմության մյուս մաս: Այնուհետև այդ գործընթացը կրկնվում է յուրաքանչյուր առանձին վերցրած ենթաբազմության համար, որոնք առաջացել էին նախորդ քայլում հենակետային տարրի ընտրմամբ  և բազմության տրոհմամբ: Գործընթացը շարունակվում է այնքան, քանի դեռ մուտքային բազմությունը տեսակավորված չէ: Օրինակ եթե մուտքային բազմությունն է՝ 4, 8, 5, 7, 3, 10, 1 և հենակետային տարր ենք ընտրում մեջտեղի տարրը, ապա առաջին քայլից հետո կունենանք՝  4, 1, 5, 3, 7, 10, 8: Տեսակավորման ալգորիթմի միջին բարդությունը O(n log n) -է: Վատագույն դեպքում, երբ ամեն քայլի ընթացքում հենակետային տարր է ընտրվում ամենամեծ կամ ամենափոքր տարրը տեսակավորման ալգորիթմի բարդությունը ստացվում է O(n^2):

void QuickSort(int* a, int first, int last)
{
    int i = first, j = last, x = a[(first + last) / 2];
    do {
        while (a[i] < x)
        {
            i++;
        }
        while (a[j] > x)
        {
            j--;
        }
        if(i <= j) 
        {    
           swap(a[i], a[j]);
            i++;
            j--;
        }
    } 
    while (i <= j);    
    if (i < last)
    {
        QuickSort(a, i, last);
    }
    if (first < j)
    {
        QuickSort(a, first,j);
    }
}

Կապակցված ցուցակի մեջ ցիկլի որոնում: Կապակցված ցուցակում ցիկլի որոնման խնդիրն է՝ գտնել միմյանց վրա հղվող ցուցակի հանգույցներ: Ալգորիթմի իմաստը կայանում է հետևյալում. ՈՒնենք երկու ցուցիչ՝ մեկը արագ, մյուսը դանդաղ: Դրանց միջոցով հաջորդաբար շրջանցում ենք ցուցակը: Եթե ցուցակում կա ցիկլ, ապա արդյունքում արագ և դանդաղ ցուցիչները կհանդիպեն միմյանց: Ալգորիթմի բարդությունն է O(N):

template <class T>
bool list<T>::FindCycle()
{
    Node<T>* slow = first;
    Node<T>* fast = first;

    while(slow != 0 && fast != 0 && fast->next != 0)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            return true;
        }
    }
    return false;
}

.P.S
Կայքում նախորդ հոդվածների հրապարակումից հետո, ոմանք բավական կոշտ նկատողություններ արեցին, թե իբր օգտագործվող տերմինաբանությունը այդքան էլ հայկական չէ: ՈՒրեմն սիրելի ընթերցողներ տտ տերմինաբանությունը հայերենով երբեք էլ ոչ մեկի համար այդքան հասկանալի ու ըմբռնելի չի լինի որքան ընդունված միջազգային տերմինաբանությունն է, եթե իհարկե մի օր էլ մենք մի այնպիսի բան չստեղծենք, որ աշխարհը ստիպված լինի մեր տերմինաբանությունը օգտագործել: Դրա համար պետք է մի քիչ ըմբռնումով մոտենալ նման տերմինաբանությանը, գուցե երբեմն նաև անուշադրության արդյունք հանդիսացող տառասխալներին: Ի վերջո սա տեխնիկական բնույթի կայք է, որտեղ պահպանվում է մայրենի ուղղագրությունը, իսկ այդ նկատողությունների հեղինակ զազրախոսները, որոնք չեն հասկանում վերը գրվածը և նշվածից բացի դնում են նաև դասական ուղղագրություն և նման ցուցադրական և կեղծ հայրենասիրական մղումներով տոգորված պահանջներ կարող են չկարդալ 😉 :

Մի քանի տարածված ալգորիթմների իրականացում C/C++ -ով:, 10.0 out of 10 based on 18 ratings

Նշագրեր: , , , , ,

Բաժին: C և C++, Ալգորիթմներ, Ծրագրավորում

Կիսվել , տարածել , պահպանել

VN:F [1.9.20_1166]
Rating: 10.0/10 (18 votes cast)

Մեկնաբանություններ (3)

Թրեքբեք հղում | Մեկնաբանությունների RSS ժապավեն

Sites That Link to this Post

  1. Bookmarks from diigo 05/18/2013 (p.m.) | Diigo bookmarks blog | Մայիս 18, 2013
  1. Hayk

    Ես ցանկանում եմ դառնալ ծրագրավորող : Մի հարց , սա ո՞ր թարգամիչով պետք է գրեմ:

Մեկնաբանեք

Կհաստատվեն միայն մեսրոպատառ հայերենով գրած մեկնաբանությունները

255