Ներդրումների տեսակավորման և միաձուլման տեսակավորման ալգորիթմների համեմատություն

Մինչ կհասկանանք Insertion տեսակավորման և Merge Sorting-ի աշխատանքը և համեմատենք դրանք, եկեք հասկանանք, թե ինչ է տեսակավորման ալգորիթմը:

Ի՞նչ է տեսակավորման ալգորիթմը:

Տեսակավորման ալգորիթմն օգտագործվում է տվյալ զանգվածը վերադասավորելու կամ տարրերը ցուցակագրելու համար՝ ըստ տարրերի համեմատության օպերատորի: Համեմատության օպերատորն օգտագործվում է տվյալների որոշակի կառուցվածքի համար տարրերի նոր կարգը որոշելու համար:

Օրինակ,

Ենթադրենք, մեզ հանձնարարվել է վերադասավորել 21 այբուբեններից բաղկացած տողը աճման կարգով` հիմնվելով դրանց ASCII (Տեղեկատվության փոխանակման ամերիկյան ստանդարտ կոդ) արժեքի վրա:

Այստեղ ամենաքիչ ASCII արժեք ունեցող տողի այբուբենը կտեղադրվի առաջինը, քան ավելի բարձր ASCII արժեք ունեցող նիշը:

8 ստանդարտ տեսակավորման ալգորիթմներ-ի շուրջ այս հոդվածը պատրաստվում է վերլուծել և համեմատել Տեղադրման տեսակավորման ալգորիթմը և Միաձուլման տեսակավորման ալգորիթմը:

Ի՞նչ է ներդրման տեսակավորումը:

Հիշելով, թե ինչպես է աշխատում ընտրության տեսակավորումը, մենք հասկանում ենք, որ սկզբում ենթազանգվածը տեսակավորված է, սակայն վերջում գտնվող ենթազանգվածը՝ ոչ: Ընտրված տեսակավորումը սկանավորում է չտեսակավորված ենթազանգվածը՝ հաջորդ տարրը ներառելու համար տեսակավորված ենթազանգվածում:

Տեղադրման տեսակավորումը վերաբերում է զանգվածի տարրերի պտտմանը, սկսած զանգվածի ինդեքսից 0: Յուրաքանչյուր նոր անցած դիրքն այն տարրն է, որը պետք է տեղադրվի ճիշտ տեղում՝ դասավորված ենթազանգվածի այդ դիրքից ձախ:

Insertion sort-ում տրված զանգվածը բաժանում ենք երկու մասի՝ տեսակավորված մասի և չտեսակավորված մասի։

Չտեսակավորված մասից վերցնում ենք առաջին տարրը և դասավորված մասում այն ​​դնում ենք իր ճիշտ դիրքում, դա արվում է բոլոր այն տարրերը, որոնք ավելի մեծ են, քան առաջին տարրը մեկ դիրքով:

Այս գործընթացը կրկնվում է այնքան ժամանակ, մինչև չտեսակավորված մասի բոլոր տարրերը տեսակավորվեն

Տեղադրման տեսակավորման կեղծ կոդը

insertionSort( A : array of items )
   int holePosition;
   int valueToInsert;
	
   for i = 1 to length(A) inclusive do:
      valueToInsert = A[i]
      holePosition = i      
		
      while holePosition > 0 and A[holePosition-1] > valueToInsert do:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      end while
		
      /* insert the number at hole position */
      A[holePosition] = valueToInsert
      
   end for
	
end

Կոդերի իրականացում ներդիրների տեսակավորման համար

int array[5];
for(int i = 1 ; i<array;i++)
{
 int temp = array[i];
 int j = i -1;
while(j > = 0 && arr[j] > temp)
 {
array[j + 1] = array[j];
  
  j = j+1;
 }
array[ j + 1 ] = temp;
}

Այժմ եկեք դիտարկենք 5 տարրերից բաղկացած զանգվածի օրինակ և տեսակավորենք այն՝ օգտագործելով Տեղադրման տեսակավորման ալգորիթմը:

Այստեղ առաջին տարրը, որը գտնվում է տեսակավորված մասում, և մնացած տարրերը, որոնք վերևում են, համեմատվում են և համապատասխանաբար տեղադրվում

Նշեք առաջին տարրը (5) որպես տեսակավորված:

Կեղծ կոդի հիման վրա՝

Արտահանեք առաջին չտեսակավորված տարրը, (1):

Այժմ պարզեք, թե որտեղ տեղադրեք արդյունահանված տարրը. համեմատելով տեսակավորված տարր 5-ի հետ:

Քանի որ 5 › 1-ը ճշմարիտ է, հետևաբար ընթացիկ տեսակավորված տարրը (5) տեղափոխեք աջ 1-ով:

Զանգվածի սկզբում (համեմատելու ոչինչ չկա), հետևաբար տարրը տեղադրեք ընթացիկ դիրքում:

Այժմ հանեք առաջին չտեսակավորված տարրը (9):

Այժմ կրկին պատկերացրեք, թե որտեղ տեղադրեք արդյունահանված տարրը և համեմատեք այն հարակից տեսակավորված տարրի հետ 5:

Քանի որ 5 › 9-ը կեղծ է, տեղադրեք տարրը (9) ընթացիկ դիրքում:

Այժմ հանեք առաջին չտեսակավորված տարրը (2):

Այժմ կրկին պատկերացրեք, թե որտեղ տեղադրեք արդյունահանված տարրը և համեմատեք հարակից տեսակավորված տարրի հետ (9):

Քանի որ 9 › 2-ը ճշմարիտ է, ընթացիկ տեսակավորված տարրը (9) տեղափոխեք աջ 1-ով:

Այժմ կրկին պատկերացրեք, թե որտեղ պետք է տեղադրվի արդյունահանված տարրը և համեմատեք այն հարակից տեսակավորված տարրի հետ (5):

Քանի որ 5 › 2-ը ճշմարիտ է, ընթացիկ տեսակավորված տարրը (5) տեղափոխեք աջ 1-ով:

Այժմ կրկին պատկերացրեք, թե որտեղ պետք է տեղադրվի արդյունահանված տարրը և համեմատեք այն հարակից տեսակավորված տարր 1-ի հետ:

Քանի որ 1 › 2-ը կեղծ է, տեղադրեք տարրը (2) ընթացիկ դիրքում:

Այժմ հանեք առաջին չտեսակավորված տարրը (10) և պատկերացրեք, թե որտեղ տեղադրեք հանված տարրը և համեմատեք այն հարակից տեսակավորված տարրի հետ (9):

Քանի որ 9 › 10-ը կեղծ է, տեղադրեք տարրը ընթացիկ դիրքում: Այժմ կառավարումը դուրս է գալիս «for» հանգույցից:

Այժմ մենք վերջապես ստանում ենք տեսակավորված ցուցակ:

Տեղադրման տեսակավորման վերլուծություն

Ենթադրենք, որ կան n թվով մուտքեր, որոնց համար մենք սահմանում ենք

Այստեղ c1, c2 և c3 հաստատուններ են և կախված չեն n-ից

while ցիկլը կատարվում է առավելագույնը j-1 անգամ j-ի տրված արժեքի համար, հետևաբար հանգույցում անցկացրած ժամանակը առավելագույնը կլինի (j-1)c2:

Արտաքին For օղակի ցանկացած կրկնություն տևում է առավելագույնըc1 +(j-1)c2 + c3

Տեղադրման տեսակավորման ընդհանուր գործարկման ժամանակը ∑ [c1 +(j-1)c2 + c3 ]= d1(n²) + d2(n) + d3, քանի որ սա քառակուսի հավասարում է, ֆունկցիայի գերիշխող մասն է n²հետևաբար աճի տեմպը կսահմանվի n² տերմինով:

Այս աճի տեմպը/ժամանակի բարդությունը ներդրման տեսակավորումը կարող է արտահայտվել O(n²):

Այնուհետև Լավագույն դեպքը և Վատագույնը կարող են որոշվել հետևյալ կերպ.

• Լավագույն դեպք. Աճման դասավորված ցուցակի տեսակավորում, որը պահանջում է O(1) ժամանակ:
• Վատագույն դեպք. Ցանկի տեսակավորում աճման կամ նվազման կարգով, ինչը O(n²) ժամանակ է պահանջում։

Ի՞նչ է միավորման տեսակավորումը:

Merge Sorting-ը արտաքին ալգորիթմ է, որը հիմնված է բաժանիր և տիրիր ռազմավարության վրա

Այն բաժանում է մուտքային զանգվածը երկու կեսի, իրեն անվանում է (ռեկուրսիա) երկու կեսերի համար, այնուհետև միավորում է երկու տեսակավորված կեսերը։

Այնուհետև կանչվում էmerge()ֆունկցիան՝ երկու տեսակավորված զանգվածները մեկ զանգվածի մեջ միացնելու համար։

Նախքան միաձուլման տեսակավորումը հասկանալն ու վերլուծելը, եկեք հասկանանք, թե ինչ են «Բաժանիր և տիրիր» ալգորիթմները

Ի՞նչ են «Բաժանիր և տիրիր» ալգորիթմները:

Divide Conquerալգորիթմներն իրենց բնույթով ռեկուրսիվ են և ներառում են.

• Բաժանել.մուտքագրված տվյալները բաժանել S երկու բաժանված ենթաբազմությունների S1 և S2 n
• Ռեկուրսիա. լուծել S 1 և S2 n-ի հետ կապված ենթախնդիրները
• Նվաճել. միավորել S 1-ի և S2-ի լուծումները S-ի լուծման մեջ

Միաձուլման տեսակավորման կեղծ կոդը

procedure mergesort( var a as array )
   if ( n == 1 ) return a
   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]
   l1 = mergesort( l1 )
   l2 = mergesort( l2 )
   return merge( l1, l2 )
end 
merge( var a as array, var b as array )
   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while
   
   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while
   
   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while
   
   return c	
end

Կոդի ներդրում միաձուլման տեսակավորման համար

void mergeSort(int arr[])
{
 int beg = 0;
 int end = sizeof(arr);
 if (beg < end)
 {
  int mid = (beg + end) / 2;
  
  // Sort first and second halves
  mergeSort(arr, beg, mid);
  
  mergeSort(arr, mid+1, end);
  
  merge(arr, beg, mid, end);
}
}
void merge(int arr[], int beg, int mid, int end)
{
    int i, j, k;
    int n1 = mid - beg + 1;
    int n2 = end - m;
  
    /* create temp arrays */
 
    int Beg[n1], End[n2];
  
    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++)
    {
    
        Beg[i] = arr[l + i];
    
    }
    for (j = 0; j < n2; j++)
    {
        End[j] = arr[m + 1 + j];
    }
  
    /* Merge the temp arrays back into arr[l..r]*/
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // Initial index of merged subarray
    
    while (i < n1 && j < n2)
     {
        if (Beg[i] <= End[j])
         {
            arr[k] = Beg[i];
            i++;
        }
        else 
        {
            arr[k] = End[j];
            j++;
        }
        
        k++;
    }
  
    /* Copy the remaining elements of L[], if there
    are any */
    while (i < n1)
     {
        arr[k] = Beg[i];
        i++;
        k++;
    }
  
    /* Copy the remaining elements of R[], if there
    are any */
    while (j < n2)
    {
        arr[k] = End[j];
        j++;
        k++;
    }
}

Այժմ եկեք դիտարկենք 5 տարրերից բաղկացած զանգվածի օրինակ և տեսակավորենք այն՝ օգտագործելով Միաձուլման տեսակավորման ալգորիթմը:

Այժմ զանգվածը բաժանում ենք 1-ի մասերի, հաշվի առնելով 5-րդ և 2-րդ տարրը, նախ միացնում ենք 5-ը և 2-ը:

Քանի որ 5 (ձախ միջնորմ) › 2 (աջ միջնորմ), վերցնում ենք 2, փոխարինում 5-ի տեղում։

Քանի որ աջ միջնորմը դատարկ է, վերցնում ենք 5-ը և տեղադրում 2-ի տեղում։

հիմա նորից զանգվածը բաժանում ենք մեկ այլ մասի և միացնում 9-րդ տարրը դրա մեջ:

Քանի որ 2 (ձախ միջնորմ) ‹= 9 (աջ միջնորմ), վերցնում ենք 2-ը և պահում այն ​​իր տեղում, իսկ 5-ից (ձախ միջնորմ) ‹= 9 (աջ միջնորմ), վերցնում ենք 5 և պահում ենք իր տեղում և վերջապես Քանի որ ձախ միջնորմը դատարկ է, դատարկ տեղին ավելացվում է 9

Մենք նոր զանգվածից տարրերը պատճենում ենք սկզբնական զանգվածի մեջ:

Այժմ զանգվածը բաժանում ենք նոր մասի և դրան ավելացնում տարր [3] և [4] ինդեքսում, այսինքն՝ 4 և 12:

Քանի որ 4 (ձախ միջնորմ) ‹= 12 (աջ միջնորմ), վերցնում ենք 4-ը և պահում այն ​​իր տեղում։

Քանի որ ձախ բաժանումը դատարկ է, դատարկ տարածության մեջ ավելացվում է 12:

Այժմ երկու կիսատեսակավորված զանգվածները միաձուլվել են սկզբնական զանգվածի մեջ

Հիմա նկատի ունենալով կիսադասակարգված զանգվածը, քանի որ 2 (ձախ միջնորմ) ‹= 4 (աջ միջնորմ), վերցնում ենք 2-ը և պահում այն ​​իր տեղում:

Քանի որ 5 (ձախ միջնորմ) › 4 (աջ միջնորմ), վերցնում ենք 4 և փոխարինում 5-ի տեղում։

Քանի որ 5 (ձախ միջնորմ) ‹= 12 (աջ միջնորմ), վերցնում ենք 5-ը և ավելացնում 4-ի կողքին։

Քանի որ 9 (ձախ միջնորմ) ‹= 12 (աջ միջնորմ), մենք վերցնում ենք 9-ը և այն դնում ենք 5-ի կողքին:

Քանի որ ձախ բաժանումը դատարկ է, դատարկ տարածության մեջ ավելացվում է 12:

Ի վերջո, մենք նոր զանգվածից տարրերը պատճենում ենք սկզբնական զանգվածի մեջ, այժմ մենք ունենք տեսակավորված զանգված:

Միաձուլման տեսակավորման վերլուծություն

• ԹողT(N)լինի N տարրերի զանգվածի գործարկման ժամանակը:
• Քանի որ Merge Sort-ը զանգվածը կիսում է կիսով չափ և ինքն իրեն կանչում երկու կեսերի վրա: Վերադառնալուց հետո այն միավորում է երկու կեսերն էլ՝ օգտագործելով ժամանակավոր զանգված:
• Յուրաքանչյուր ռեկուրսիվ զանգ տևում է T(N/2) .
• միաձուլումը պահանջում է O(N):

Ընդհանուր առմամբ ալգորիթմը վերցնում է.

• Տ(n)=2Տ(n/2) + O(n) ժամանակը, եթե n › 1:
• T(n)= O(1) անգամ, եթե n = 1:

Սա ենթադրում է, որ T(n)= O(nlog(n)), այս աճի տեմպը/ ժամանակային բարդությունը ներդրման տեսակավորումը կարող է արտահայտվել O(n log(n)):

Այնուհետև Լավագույն դեպքը և Վատագույնը կարող են որոշվել հետևյալ կերպ.

• Լավագույն դեպք. Ցանկում միայն մեկ տարրի տեսակավորում, որը պահանջում էO(1)ժամանակ:
• Վատագույն դեպք. Ցուցակի տեսակավորումը ցանկացած հերթականությամբ, որը պահանջում է O(n log(n))ժամանակ

Այժմ, քանի որ մենք ստեղծել ենք հիմնական հասկացողություն այն մասին, թե ինչպես են աշխատում Insertion Sort և Merge Sort ալգորիթմները, թույլ տվեք համեմատել և հակադրել այս երկուսի առանձնահատկությունները:

Ներդրումների տեսակավորման և միաձուլման տեսակավորման ալգորիթմների համեմատություն:

Ժամանակի բարդություն.

• Merge Sort-ում ամենավատ դեպքն է O(n log (n))միջին դեպքը O(n log (n)) >իսկ լավագույն դեպքն է O(n log (n)):
• Տեղադրման տեսակավորման մեջ ամենավատ դեպքն է O(n²), միջին գործը` O(n²), իսկ լավագույնը: Գործը` O(n):

Հետևաբար, Միաձուլման տեսակավորումը գերադասելի է զետեղման տեսակավորման փոխարեն, քանի որ վատագույն և լավագույն դեպքում ժամանակային բարդությունները ցանկալի են, այսինքն՝ O(n log (n)):

Տիեզերական բարդություն.

• Քանի որ Merge տեսակավորումը ռեկուրսիվ է, այն վերցնում է O(n)-ի օժանդակ տարածության բարդությունը, հետևաբար այն չի կարող գերադասվել այն վայրից, որտեղ հիշողությունը խնդիր է:
• Տեղադրման տեսակավորումը պահանջում է միայն O(1)օժանդակ տարածության բարդություն: Այն տեսակավորում է ամբողջ զանգվածը՝ օգտագործելով լրացուցիչ փոփոխական:

Հետևաբար, Insertion տեսակավորումը գերադասելի է Merge Sort-ից, երբ հիշողության սահմանափակման խնդիր է առաջանում:

Արդյունավետություն:

• Հաշվի առնելով երկու ալգորիթմների միջին ժամանակային բարդությունը, կարող ենք ասել, որ Merge Sort-ն արդյունավետ է ժամանակի առումով, իսկ Insertion Sort-ը՝ տարածության առումով:

Տեսակավորման մեթոդ.

• Միաձուլման տեսակավորումը արտաքին տեսակավորման մեթոդ է, որի դեպքում տեսակավորվող տվյալները չեն կարող տեղավորվել հիշողության մեջ, և տեսակավորման համար անհրաժեշտ է օժանդակ հիշողություն, հետևաբար Միաձուլման տեսակավորման ալգորիթմը տեղում չէ:
• Տեղադրման տեսակավորումը հիմնված է այն մտքի վրա, որ մուտքագրված տարրերից մեկ տարր սպառվում է յուրաքանչյուր կրկնության մեջ՝ գտնելու իր ճիշտ դիրքը, այսինքն՝ այն դիրքը, որին պատկանում է տեսակավորված զանգվածում, հետևաբար, Տեղադրման տեսակավորման ալգորիթմը տեղում է: em>

Կայունություն:

• Միաձուլման տեսակավորումը կայուն է, քանի որ հավասար արժեք ունեցող երկու տարրեր դասավորված ելքով հայտնվում են նույն հերթականությամբ, ինչ որ մուտքային չտեսակավորված զանգվածում:
• Տեղադրման տեսակավորումը պահանջում է O(n²) ժամանակ, հետևաբար արժեքները նույնն են թվում, բայց տարբեր են:

Գործողության ժամանակը:

Այսպիսով, մենք կարող ենք եզրակացնել, որ Insertion Sort և Merge Sort ալգորիթմները կիրառվում են տարածության և ժամանակի սահմանափակումների հիման վրա, որոնք իրենց հերթին կախված են համակարգից և նրանից, թե ինչպես է ծրագիրը/ծրագրային ապահովումը ներդրվում համակարգում: