C++ Metode de sortare Metoda bulelor, insertiei, selectiei, numararii

// Bubble Sort – Sortarea unui tablou unidimensional

#include<iostream.h>
int v[25], i, n, ok, aux;

void main()

{cout<<„n=”; cin>>n;

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

{cout<<„v[„<<i<<„]=”; cin>>v[i]; }

for(i=1;i<=n;i++) cout<<v[i]<<” „;

//Sortarea crescatoare

do

{

ok=1;

for(i=1;i<=n-1;i++)

if(v[i]>v[i+1])

{

//Interschimbare

aux=v[i];

v[i]=v[i+1];

v[i+1]=aux;

ok=0;

}

}while(ok!=1);

cout<<endl;

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

cout<<v[i]<<” „;

}

 

 

/* SORTAREA PRIN INSERTIE

Fie un tablou unidimensional care contine n valori intregi.

Realizati un program care ordoneaza crescator elementelor vectorului folosind „algoritmul de insertie”.

Solutia:  Elementele vectorului sunt impartite in doua liste: sortata si nesortata.

La fiecare pas primul element al listei nesortate este transferat in lista sortata, exact pe pozitia prin care se respecta  ordinea crescatoare a elementelor.

Aceasta operatie se va realize  prin deplasarea cu o pozitie spre dreapta a tuturor elementelor  mai mari decat el.

 

Exemplu:

Fie vectorul a=(3,2,1,6,4).

Lista ordonata va fi formata initial din primul element iar lista neordonata de celelalte (n-1) elemente

Pas 1: Se cauta locul lui 2 in lista ordonata (3) si se va deplasa cu o pozitie spre  dreapta primul element ==> se obtine vectorul a=(2,3,1,6,4)

Pas 2: Se cauta locul lui 1 in lista ordonata (2,3)  si se va deplasa cu o pozitie spre  dreapta elementele 2 si 3 ==> se obtine vectorul a=(1,2,3,6,4)

Pas 3: Pentru ca 6>3 nu se vor realiza deplasari, vectorul a ramane acelasi  a=(1,2,3,6,4)

Pas 4: Se cauta locul lui 4 in lista ordonata (1,2,3,6)  si se va deplasa cu o pozitie spre dreapta elementul 6 ==> se obtine vectorul a=(1,2,3,4,6)

*/

// Sortarea prin insertie – Sortarea unui tablou unidimensional

#include<iostream.h>

int v[25],i,j,n,x;

void main()

{

cout<<„n=”; cin>>n;

 

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

{ cout<<„v[„<<i<<„]=”; cin>>v[i]; }

 

for(i=1;i<=n;i++) cout<<v[i]<<” „;

 

// Sortarea prin INSERTIE

for(i=2;i<=n;i++)    // parcurg vectorul nesortat de la a 2-lea element pana la sfarsit

  if (v[i]<v[i-1])   // primul element din vectorul nesortat se plaseaza pe pozitia corespunzatoare

      { x=v[i];      // valoarea lui v[i] se pierde din vectorul nesortat

            j=i-1;

while (j>=0 && v[j]>x) // mut cu o pozitie spre dreapta toate elementele mai mari decat x=v[i]

               {

               v[j+1]=v[j];

               j–;

               }

       v[j+1]=x; // insertia primului element pe pozitia corespunzatoare in vectorul sortat

      }

cout<<endl;

 

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

cout<<v[i]<<” „;}

//Sortarea prin selectie

/*  Fiecare element v[i] se compara cu toate aflate dupa el. Daca se gaseste un element mai mic decat v[i] atunci acestea se vor interschimba. Cand v[i] si-a incheiat rolul de pivot, partea din vector pana la acesta inclusiv, este sortata crescator. */

#include<iostream.h>
int v[25],n,i,j,aux;
void main()
{cout<<„nr de elemente=”;

cin>>n;

for(i=0;i<n;i++)

{cout<<„v[„<<i<<„]=”;

cin>>v[i];}

for(i=0;i<n;i++)

cout<<v[i]<<” „;

for(i=0;i<n-1;i++)

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

if(v[i]>v[j])

{ aux=v[j];  v[j]=v[i]; v[i]=aux; }

cout<<endl;

for(i=0;i<n;i++)

cout<<v[i]<<” „;

}

 

/*Sortarea prin numarare

Enunt:

 

Fie un tablou unidimensional care contine n valori intregi.

Realizati un program care ordoneaza crescator elementelor  vectorului folosind „algoritmul de numarare”.

Solutia:

Consideram vectorul A. Algorituml de sortare prin numarare consta in gasirea pentru fiecare element A[i] a numarului de elemente din vector mai mici decat el.

Numerele obtinute sunt memorate  intr-un alt vector B.

Elementele vectorului A vor fi initial salvate in vectorul auxiliar C.

La finalul algoritmului se vor rescrie in ordine crescatoare elementele vectorului A pe baza valorilor memorate in B si C

Exemplu:

Fie vectorul A=(30,20,1,6,4).

Pas 1: Se realizeaza o copie a vectorului A in C.  Se va obtine vectorul C=(30,20,1,6,4).

Pas 2: Se determina elementele vectorului B astfel:

B[i]=cate elemente mai mici decat A[i] sunt in vectorul A  Se va obtine vectorul B=(4,3,0,2,1).

Pas 3: Se completeaza elementele vectorului A astfel:  A[B[i]]=C[i].  Se va obtine A=(1,4,6,20,30).

*/

#include<iostream.h>

int a[25],b[25],c[25],n,i,j;

 

void main()

{

cout<<„nr de elemente=”; cin>>n;

 

for(i=0;i<n;i++) { cout<<„v[„<<i<<„]=”; cin>>a[i]; }

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

// Sortarea prin numarare

// Pasul 1 fac o copie a vectorului a in vectorul c

for(i=0;i<n;i++)

c[i]=a[i];

 

// Pas 2 crearea vectorului b[i]

// determinam pentru fiecare element cate elemente sunt mai mici

 

for(i=0;i<n;i++)

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

if (a[i]<a[j])

b[j]++;

else b[i]++;

 

// Pasul 3 Se rescriu elementele lui a in ordine crescatoare

for(i=0;i<n;i++)

a[b[i]]=c[i];

cout<<endl;

// Afisarea vectorului sortat

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

}