Sortarea prin Insertie

          Sortarea prin insertie se bazeaza pe aceleasi principii ca si cele aplicate de majoritatea jucatorilor de carti, adica dupa ridicarea unei carti de pe masa, aceasta se aseaza in pachetul din mina la locul potrivit. Cu alte cuvinte in limbaj natural consideram ca avem vectorul sortat a, iar la ivirea unui nou element care se va adauga vectorului, va fi pus pe locul potrivit printr-o insertie in interiorul vectorului.

          Insertia directa. Este cea mai simpla implementare a algoritmului si se face in felul urmator: Se considera ca primele i elemente al vectorului sunt deja sortate. Pentru elementul al i+1-lea, din tabloul initial, se va gasi pozitia in care trebuie inserat printre primele i elemente. Toate elementele tabloului de la aceasta pozitie si pina la i vor fi deplasate cu o pozitie mai la dreapta iar in pozitia eliberata va fi ocupata de elementul i+1.

          Inserarea rapida. Acest algoritm foloseste aceeasi impartire a vectorului in doi subvectori (sursa si destinatie), la fel ca si metoda inserarii directe. Deoarece vectorul destinatie este un vector ordonat crescator, cautarea pozitiei in care va fi inserat a[i] se poate face nu secvential (ca in cazul inserarii directe) ci prin algoritmul de cautare binara. Subvectorul destinatie este impartit in doi subvectori, se examineaza relatia de ordine dintre elementul de la mijlocul subvectorului si elementul a[j] si se stabileste daca elementul a[i] va fi inserat in prima jumatate sau in a doua jumatate. Operatia de divizare a subvectorului se continua pina se gaseste pozitia in care urmeaza sa fie inserat a[i].

//Sortarea prin insertie;

#include<iostream.h>;

void main()

{

int i,j,n,aux,a[50];

cout<<"dati n"<<endl; cin>>n;

cout<<"Dati elementele sirului"<<endl;

for(i=0;i<n;i++) cin>>a[i];

for(j=1;j<n;j++)

   {

   aux=a[j];

   i=j-1;

   while ( aux < a[i] && i>=0 )

      { a[i+1]=a[i]; i--; };

   a[i+1]=aux;

   }

for(i=0;i<n;i++) cout<<a[i]<<" ";

}