Metode de sortare – insertie directa (Direct Insertion Sort)

În cazul acestei variante de inserţie, căutarea poziţiei în care se inserează elementul curent se face decrementai, prin parcurgerea “Părţii stânga” de la dreapta spre stânga, până la găsirea poziţiei de inserare.

3 | 7 4 9 2 8 Se porneşte de la i=1, locul elementului a[1]=7 ramane neschimbat
3 7 | 4 9 2 8 Pentru i=2, a[2]=4 va ajunge pe poziţia a[1] iar elementul a[1]=7 va fi decalat la dreapta cu o poziţie
3 4 7 | 9 2 8 Pentru i=3, locul elementului a[3]=9 ramane neschimbat
3 4 7 9 | 2 8 Pentru i=4, locul elementului a[4]=2 este pe poziţia a[0], iar elementele a[3], a[2], a[1] si a[0] se vor decala la dreapta cu o poziţie
2 3 4 7 9 | 8 Pentru i=5, locul elementului a[5]=8 este pe poziţia a[4], iar elementul a[4] va fi decalat la dreapta cu o poziţie
2 3 4 7 8 9 | Şirul este sortat


#include "stdio.h"
#include "conio.h"
void insertie(int a[], int n)
{
  int i,j,elem;
  for(i=1;i < n;i++)
  //pentru toate elementele de la al doilea până la ultimul
  {
    elem=a[i];
    //pentru elementul a[i]
    j=i-1;
    //îi căutăm locul în secvenţa a[o]..a[i-1]
    while((j >= 0) &&(elem < a[j]))     //atât timp cât nu ajungem pe prima poziţie şi elementul de inserat este mai mic     //decât a [j]     { .       a[j+1]=a[j];       //mutăm elementul a[j] pe poziţia j+1       j--;       //decrementăm indicele j pentru a ajunge la precedentul element     }     a[j+1]=elem;     //la ieşirea din ciclul while, elementul trebuie inserat pe poziţia i+1   } } void main(void) {   int n,a[100],i;   printf("Introdu dim şirului:");   scanf("%d",&n);   printf("Introdu elem şirului: \n");   for(i=0;i

Leave a Reply

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

2 + 9 =

Time limit is exhausted. Please reload CAPTCHA.