Metode de sortare – insertie directa folosind o santinela

Această variantă de inserţie foloseşte în a [0] o valoare foarte mică, mai mică decât oricare din cheile din vector. Această valoare simplifică înaintarea în “Partea stângă” sortată, având garanţia că nu vom depăşi marginea stânga a şirului Rolul santinelei este ca elementul care va fi adus pe prima poziţie să fie comparată cu o valoare sigur mai mică. Pentru această variantă de sortare, elementele şirului vor avea indicii de la 1 la n.


#include "stdio.h"
#include "conio.h"
#include "values.h"
//pentru MAXINT
void insertie_cu_santinela(int a[], int n)
{
  int i,j,elem;
  a[0]=-MAXINT;
  //valoarea minimă pentru tipul int
  for(i=2;i <= n;i++)   //pornim cu elementul a[2] (al doilea element al şirului)   {     elem=a[i];     j=i-1;
    //începem căutarea de la poziţia i-1
    while(a[j] > elem)
    //nu mai este necesară verificarea indicelui j
    {
      a[j+1]=a[j];
      //elementele sunt mutate la dreapta cu o poziţie
      j--;
      //decrementăm indicele j
    }
    a[j+1]=elem;
    //elementul este inserat pe poziţia j+1 (având în vedere că în ultima
    //iseraţie a ciclului while, j a fost decrementat, fiind astfel
    //poziţionaţi pe primul element mai mic decât elementul de inserat,
    //deci inserarea trebuie să se facă pe poziţia succesorului lui a[j]).
    //Vom ajunge cu j=0 doar în cazul în care elementul este minimul din şir
  }
}

void main(void)
{
  int n,a[100],i;
  printf("Introdu dim şirului:");
  scanf("%d",&n);
  printf("Introdu elem sirului:\n");
  for(i=1;i<=n;i++)   {     printf("a[%d]=",i);     scanf("%d",a+i);   }   insertie_cu_santinela(a,n);   printf("Sirul sortat este: ");   for(i=1;i<=n;i++)     printf("%d ",a[i]);   putchar("n");   getch(); }

Leave a Reply

Your email address will not be published. Required fields are marked *

13 + nine =

Time limit is exhausted. Please reload CAPTCHA.