InsertSort cu cautare liniara

Sortarea prin inserţie folosind căutare liniară InsertSort

Informaţii generale:

Vom căuta poziţia pe care se inserează elementul vectorului la pasul i. Se parcurge vectorul de la stânga la dreapta pentru a găsi un element mai mare decât cel curent. Căutarea se face printre elementele deja ordonate (până la poziţia i – 1). Dacă se găseşte un element mai mare, se vor deplasa dreapta cu o poziţie toate elementele de la el până la i-1 pentru a face loc elementului i, care va fi inserat în poziţia corectă. Dacă nu există nici un element mai mare decât elementul i, atunci acesta rămâne pe poziţia lui, subşirul fiind deja ordonat.

Exemplu : şirul iniţial este {5, 3, 4, 7, 6}

i	x[1]	x[2]	x[3]	x[4]	x[5]
i = 2	5	3	4	7	6
Compar 3 cu 5: 3<5, deplasez 5 pe a doua poziţie, inserez 3 pe prima poziţie
i = 3	3	5	4	7	6
Aşez 4 în poziţia finală: deplasez pe 5 o poziţie, în locul lui 5 inserez pe 4
i = 4	3	4	5	7	6
Aşez 7 în poziţia finală: observ că rămâne pe locul lui, subşirul e deja ordonat
i = 5	3	4	5	7	6
Aşez 6 în poziţia finală: deplasez pe 7 o poziţie, în locul lui 7 inserez pe 6
	3	4	5	6	7

Varianta pseudocod a algoritmului:

pentru i ←2,n execută

j←1;

cât timp x_j<x_i şi j

sfârşit cât timp;

aux2←x_j; %atribuire%

pentru k←j,i-1 execută

aux1←x_k₊₁; %atribuire%

x_k₊₁←aux2 ; %atribuire%

aux2←aux1; %atribuire%

sfârşit pentru;

x_j←aux2; %atribuire%

sfârşit pentru;

Observaţii:

Pentru a deplasa elementele avem nevoie, la fiecare pas, de trei atribuiri.
Pentru a găsi cazul cel mai favorabil din punct de vedere al comparărilor, corpul buclei cât timp nu ar trebui să se execute nici o dată, deci elementul curent să fie inserat direct pe prima poziţie, atunci şirul trebuie să fie ordonat descrescător. De asemenea, cazul cel mai defavorabil va fi atunci când vectorul este ordonat crescător (corpul buclei cât timp se execută de cele mai multe ori).
Din punct de vedere al atribuirilor, în cazul cel mai favorabil, corpul buclei pentru nu ar trebui să se execute nici măcar o dată, deci nu sunt necesare deplasări, şirul fiind sortat crescător. Cazul cel mai defavorabil apare când bucla interioara a lui pentru se execută de cele mai multe ori, deci vectorul e sortat descrescător.
Se observă că cel mai favorabil caz pentru atribuiri este defavorabil din punct de vedere al comparărilor şi invers, cel mai favorabil caz pentru comparări este defavorabil din punct de vedere al atribuirilor. Datorită faptului că nu poate fi determinată o echivalenţă absolută între un anumit număr de atribuiri şi un anumit număr de comparări, nu există posibilitatea determinării clare a celui mai favorabil si defavorabil caz a acestui algoritm de sortare.
Observăm că ordinul de complexitate al algoritmului prezentat este O(n²).

Implementare C++ :

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

j=0;

do {j++} while (x[i]<x[j] && j<i); //caut poziţia j pentru x[i]

aux2=x[j];

for (k=j; k<i;k++){

//deplasez dreapta elementele de la poziţia j la poziţia i-1

aux1=x[k+1];

x[k+1]=aux2;

aux2=aux1;

}

x[j]=aux2 ; // elementul x[i] îl aduc pe poziţia j

}

Implementare Pascal :

for i :=2 to n do

begin

j:=1;

while (x[i]<x[j] and j<i) do j:=j+1;

aux2:=x[j];

for k:= j to i-1 do

begin

aux1:= x[k+1];

x[k+1]:=aux2;

aux2 :=aux1 ;

end ;

x[j] :=aux2 ;

end ;

Observaţii:

Se observă posibilitatea optimizării algoritmului anterior prin păstrarea elementului x_i, ce trebuie inserat în poziţia finală în subşirul ordonat x₁,… , x_i-1, într-o variabilă auxiliară aux, deplasarea elementelor de la poziţia j, până la poziţia i-1 la dreapta printr-o singură atribuire x_k₊₁←x_k, apoi aducerea pe poziţia j a lui x_iprin atribuirea x_j←aux.
De asemenea, se poate determina poziţia elementului cu care se va interschimba x_i parcurgând subşirul ordonat x₁,… , x_i-1de la dreapta la stânga, deci până vom găsi un element mai mic decât x_i sau ajungem pe prima poziţie. Pe măsură ce efectuăm căutarea unui element mai mic putem să efectuăm şi deplasările, în final vom insera elementul curent în poziţia finală.

Mergi la pagina METODE DE SORTARE

Aplicatii

Aplicaţie1: Se citeşte un număr natural n şi un vector cu 2*n elemente numere naturale. Construiţi n fracţii folosind elementele vectorului, astfel încât suma lor să fie maximă.

Exemplu: Pentru n=3 şi 3 2 4 9 7 6 vom obţine 9/2, 7/3, 6/4.

Observaţie: Ţinând cont că toate numerele sunt pozitive, fracţiile rezultate vor fi pozitive. Suma lor este maximă când fiecare fracţie este cât mai mare. Vom ordona vectorul descrescător, iar prima fracţie o vom construi având ca numărător pe cel mai mare termen al şirului, iar numitor cel mai mic. Următoarea fracţie o vom construi după aceeaşi observaţie, folosind valorile rămase, etc.

Program C++:

#include <iostream.h>

#include <conio.h>

void main() {

int i, j, k,aux1,aux2, n, a[100];

cin>>n;

for(i=1; i<=2*n; i++) cin>>a[i];

for(i=2; i<2*n; i++){

j=1;

do {j++} while (a[i]>a[j] && j<i);

aux2=a[j];

for(k=j; k<i; k++){

aux1=a[k+1];

a[k+1]=aux2;

aux2=aux1; }

a[j]=aux2; }

for(i=1; i<=n; i++) cout<<a[i]<<”/”<<a[2*n+1-i]<<endl;

getch(); }

Program Pascal:

PROGRAM InsertSort1;

VAR a:ARRAY[1..100] OF INTEGER;

i,j,k,aux1,aux2,n: INTEGER;

BEGIN

READLN(n);

FOR i:= 1 TO 2*n DO READLN(a[i]);

FOR i:= 2 TO n-1 DO

BEGIN

j:=1;

WHILE (a[i]>a[j]) AND (j<i) DO j:=j+1;

aux2:=a[j];

FOR k:= j TO i-1 DO

BEGIN

aux1:=a[k+1];

a[k+1]:=aux2

aux2:=aux1;

END;

a[j]:=aux2;

END;

FOR i:= 1 TO n DO WRITELN(a[i], ’ / ’, a[2*n+1-i]);

END.

Aplicaţie2: Se citeşte un tablou cu n elemente numere întregi. Să se ordoneze crescător elementele aflate în vector între poziţia elementului minim şi poziţia elementului maxim. Dacă minimul şi maximul sunt consecutive, se va afişa “NU E CAZUL”.

Exemplu: Pentru 3 2 7 4 9 6 vom obţine 3 2 4 7 9 6.

Program C++:

#include <iostream.h>

#include <conio.h>

void main() {

int i, j, k,aux, pmin, pmax , min, max, n, a[20];

cin>>n;

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

pmin=pmax=1; min=max=a[1];

for(i=2; i<=n; i++){

if (a[i]<min) {min=a[i]; pmin=i};

if (a[i]<max) {max=a[i]; pmax=i};}

if (pmin>pmax) {

aux=pmin; pmin=pmax; pmax=aux;}

if (pmax==pmin+1) cout<<’NU E CAZUL’;

else

for(i=pmin+1; i<pmax; i++){

j=pmin;

do {j++} while (a[i]<a[j] && j<i);

aux =a[i];

for (k=i-1; k>=j; k--) a[k+1]=a[k];

a[j]=aux;}

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

getch(); }

Program Pascal:

PROGRAM InsertSort2;

VAR a:ARRAY[1..20] OF INTEGER;

i,j,k,aux,pmin, pmax, min, max,n: INTEGER;

BEGIN

READLN(n);

FOR i:= 1 TO n DO READLN(a[i]);

min:=a[1]; max:=a[1]; pmin:=1; pmax:=1;

FOR i:= 2 TO n DO

BEGIN

IF a[i]< min THEN

BEGIN min:=a[i]; pmin:=i; END;

IF a[i> max THEN

BEGIN max:=a[i]; pmax:=i; END;

END;

IF pmin>pmax THEN

BEGIN

aux:=pmin; pmin:=pmax; pmax:=aux;

END;

IF pmax=pmin+1 THEN WRITE(’NU E CAZUL’)

ELSE

FOR i:= pmin+1 TO pmax DO

BEGIN

j:=pmin;

WHILE (a[i]<a[j]) AND (j<i) DO j:=j+1;

aux:=a[i];

FOR k:= i-1 DOWNTO j DO a[k+1]:=a[k];

a[j]:=aux;

END;

FOR i:= 1 TO n DO WRITELN(a[i], ’ ’);

END.

Observaţie: În aplicaţia anterioară pentru a plasa elementul de pe poziţia i pe poziţia sa finală j am realizat deplasarea elementelor de la j până la i (de la stânga la dreapta) cu ajutorul a trei interschimbări. În aplicaţia actuală, aceeaşi deplasare am facut-o de la dreapta spre stânga, de la i la j, salvând iniţial a[i] în aux, descărcând apoi aux în a[j].

Aplicaţie3: Se citeşte o matrice cu n linii şi m coloane, având elemente întregi. Să se ordoneze crescător elementele de pe prima linie, interschimbând corespunzător coloanele.

Program C++:

#include <iostream.h>

#include <conio.h>

void main() {

int i, j, k,c,aux[20], m, n, a[20][20];

cin>>n>>m;

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

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

cin>>a[i][j];

for(i=2; i<m; i++){

j=1;

do {j++} while (a[1][i]<a[1][j] && j<i);

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

aux [c]=a[c][i];

for (k=i-1; k>=j; k--) a[c][k+1]=a[c][k];

a[c][j]=aux[c];}

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

for(j=1; i<=m; i++) cout<<a[i][j]<<” ”;

cout<<endl; }

getch(); }

Program Pascal:

PROGRAM InsertSort3;

VAR a:ARRAY[1..20,1..20] OF INTEGER;

aux: ARRAY[1..20] OF INTEGER;

i,j,k,c,m,n: INTEGER;

BEGIN

READLN(n,m);

FOR i:= 1 TO n DO

FOR j:= 1 TO m DO READLN(a[i][j]);

FOR i:= 2 TO m DO

BEGIN

j:=1;

WHILE (a[1,i]<a[1,j]) AND (j<i) DO j:=j+1;

FOR c:= 1 TO n DO

BEGIN

aux[c]:=a[c,i];

FOR k:= i-1 DOWNTO j DO a[c,k+1]:=a[c,k];

a[c,j]:=aux[c];

END;

FOR i:= 1 TO n DO BEGIN

FOR j:= 1 TO m DO WRITELN(a[i,j], ’ ’);

WRITELN;

END;

END.

Aplicaţie 4: Într-un fişier text se găsesc numere naturale. Să se ordoneze crescător numerele din fişier folosind o listă liniară simplu înlănţuită şi metoda sortării prin inserţie.

Program C++:

#include <iostream.h>

#include <conio.h>

#include

ifstream f(”nr.txt”, ios::in);

struct nod {int info, nod*leg};

nod *prim;

void adaugvf (nod *&prim, int x){

nod *nou=new nod;

nou->info=x;

nou->leg=prim;

prim=nou;}

void inserare (nod *prim, int x){

nod *p=prim;

while (p->leg->info < x && p->leg)p=p->leg;

nod *nou=new nod;

nou->info=x;

nou->leg=p->leg;

p->leg=nou;}

void citire (){

int x;

while (f>>x) if (xinfo ||prim==0)

adaugvf(prim,x);

else inserare (prim, x);}

void afis (nod *prim){

nod*p= prim;

while (p){cout<info<<” ”;

p=p->leg;}

cout<<endl;}

void main (){

citire();

afis(prim);

f.close();}

Program Pascal:

PROGRAM InsertSort4;

TYPE adresa=^nod;

nod=RECORD

info:INTEGER;

urm:^nod;

END;

VAR prim: adresa; f:TEXT;

PROCEDURE adaugvf (var prim:adresa; x:integer);

VAR nou: adresa;

BEGIN

new(nou);

nou^.info:=x;

nou^.urm:=prim;

prim:=nou;

END;

PROCEDURE inserare (prim:adresa, x:integer);

VAR p, nou:adresa;

BEGIN

p:=prim;

while (p^.urm^.info < x) AND( p^urm<>NIL) DO p:=p^.urm;

new(nou);nou^.info:=x;nou^.urm:=p^.urm;

p^.urm:=nou;END;

PROCEDURE citire ;

VAR x:INTEGER;

BEGIN

RESET (f);

WHILE NOT EOF(f) DO

BEGIN READ(f,x);

IF (x<prim^.info) OR (prim=NIL)

adaugvf(prim,x)

ELSE inserare (prim, x);

END;

CLOSE(f);

END;

PROCEDURE afis (prim:adresa);

VAR p:adresa;

BEGIN

p:= prim;

WHILE p<>NIL DO

BEGIN

WRITE (p^.info, ’ ’);

p:=p^.urm;

END;

READLN;

END;

BEGIN

prim:=NIL;

citire;

afis(prim);

END.

Mergi la pagina METODE DE SORTARE