SelectSort

Sortarea prin selecţie SelectSort

Informaţii generale

Ideea care stă la baza sortării prin selecţie este de a alege din şirul de sortat acel element care va fi aşezat pe prima poziţie a vectorului (cel mai mic). Presupunând ca acest element se află iniţial în vectorul de sortat pe poziţia k, va fi necesară o interschimbare între el şi elementul de pe prima poziţie a vectorului. Se va aplica această regulă pentru restul elementelor vectorului, începând cu al doilea, până vom obţine şirul sortat.

Prezentarea algoritmului:

Se observă că se parcurge şirul iniţial pentru a amplasa pe poziţia curentă elementul corespunzător din şirul ordonat. Pentru a identifica acest element, va trebui să căutăm cel mai mic element al subşirului format din elementele rămase, deci vom realiza o parcurgere a acestui subşir. După identificarea elementului care trebuie plasat, se realizează interschimbarea. Se va folosi o variabilă auxiliară, min, care va ajuta la interschimbare.

Exemplu:Fie tabloul X=(5,0,8,7,3)

Pas	Tabloul X	Element minim	Poziţia minimului	Noul tablou X
i=1	5, 0, 8, 7, 3	0	2	0, 5, 8, 7, 3
i=2	0, 5, 8, 7, 3	3	5	0, 3, 8, 7, 5
i=3	0, 3, 8, 7, 5	5	5	0, 3, 5, 7, 8
i=4	0, 3, 5, 7, 8	7	4

Varianta pseudocod a algoritmului:

pentru i←1,n execută

min←x_i; ind←i ;

pentru j←i+1, n execută

dacă min>x_j atunci

min←x_j;

ind←j ;

sfârşit dacă;

x_ind←x_i;

x_i←min ;

sfârşit pentru;

Complexitatea algoritmului:

Se observă că pentru un şir cu n elemente numărul de comparări este acelaşi, indiferent de valoarea celor n numere.Numărul atribuirilor poate varia doar din cauza atribuirii din interiorul instrucţiunii dacă (executată doar în cazul în care se întâlneşte un element mai mic decât valoarea lui min). Cazul cel mai favorabil al algoritmului apare atunci când această atribuire se execută de cât mai puţine ori (când şirul iniţial este deja sortat această atribuire nu se execută nici măcar o dată). Cazul cel mai defavorabil apare atunci când atribuirea se execută de cât mai multe ori. Numărul maxim de atribuiri ar fi: (n-1)+(n-2)+…+2+1=n∙(n-1)/2. Şirul corespunzător este cel ordonat descrescător.
Observăm că ordinul de complexitate al algoritmului prezentat este O(n²).

O variantă îmbunătăţită a algoritmului:

Algoritmul anterior se poate optimiza:la fiecare pas se păstrează doar poziţia minimului, nu şi valoarea sa. Astfel se elimină câteva operaţii de atribuire.Corespunzător, algoritmul va fi:

pentru i←1,n execută

ind←i;

pentru j←i+1, n execută

dacă x_ind>x_j atunci

ind←j ;

sfârşit dacă;

aux←x_ind;

x_ind←x_i;

x_i←aux ;

sfârşit pentru;

Se observă că ambele variante au un ordin de complexitate pătratică (O(n²).Nu este un algoritm indicat pentru vectorii mari, în majoritatea cazurilor oferind rezultate mai slabe decât sortare prin inserţie şi sortare cu metoda bulelor .

Implementare C++ :

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

//selectăm minimul din subşirul rămas de prelucrat

ind=i;

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

if (x[ind]>x[j]) ind=j; //căutăm poziţia minimului din subşirul rămas

aux=x[ind]; // interschimbăm elementul x[i] cu minimul găsit

x[ind]=x[i];

x[i]=aux;

}

Implementare Pascal :

for i :=1 to n-1 do

begin

ind:=i;

for j :=i+1 to n do

if x[ind] >x[j] then ind :=j ;

aux:= x[ind];

x[ind]:=x[i];

x[i]:=aux;

end;

Mergi la pagina METODE DE SORTARE

Aplicaţii

Aplicaţie1: Să se ordoneze descrescător elementele unui vector care conţine n numere întregi, fără a lua în calcul elementele nule.

Exemplu: pentru 3,-5,0,25 vom obţine 25, 3, 0, -5.

Program C++:

#include <iostream.h>

#include <conio.h>

void main() {

int i, j, aux, ind, n, a[100];

cin>>n;

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

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

ind=i;

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

if (a[i]!=0 && a[j]!=0)

if (a[i]<a[j]) ind=j;

aux=a[ind];

a[ind]=a[i];

a[i]=aux;

}

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

getch(); }

Program Pascal:

PROGRAM SORTSEL1;

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

i,j,aux,ind,n: INTEGER;

BEGIN

READLN(n);

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

FOR i:= 1 TO n-1 DO

BEGIN

ind:=i;

FOR j:= i+1 TO n DO

IF (a[i]<>0 and a[j]<>0) THEN

IF a[i]<a[j] THEN ind:=j;

aux:=a[ind];

a[ind]:=a[i];

a[i]:=aux;

END;

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

END.

Aplicaţie2: Fişierul text numere.txt conţine pe o singură linie, separate prin câte un spaţiu, cel mult 100 de numere întregi. Scrieţi un program care citeşte numerele din fişier şi afişează pe ecran, în ordine crescătoare, numerele naturale nenule, iar dacă nu sunt se afişează “NU EXISTĂ”.

Exemplu: pentru 3,-5,0,25 vom obţine 3, 25.

Program C++:

#include <iostream.h>

#include <conio.h>

#include

ifstream f(”numere.txt”);

void main() {

int i, j, aux, x, n=0, a[100];

while (f>>x){

if(x>0){a[n]=x; n++}}

if(n==0) cout<<”NU EXISTA”;

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

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

if (a[i]>a[j]) {

aux=a[i];

a[i]=a[j];

a[j]=aux;}

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

}

f.close();

getch(); }

Program Pascal:

PROGRAM SORTSEL2;

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

i,j,aux,x,n: INTEGER;f:TEXT;

BEGIN

ASSIGN( f, ’numere.txt’);

RESET(f);

n:=0;

WHILE NOT EOF(f) DO

BEGIN

READ (f,x);

IF x>0 THEN BEGIN a[n]:=x;

n:=n+1;END;

END;

IF n=0 THEN WRITE(’NU EXISTA’);

ELSE BEGIN

FOR i:= 0 TO n-2 DO

FOR j:= i+1 TO n-1 DO

IF a[i]>a[j] THEN BEGIN

aux:=a[i];

a[i]:=a[j];

a[j]:=aux;

END;

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

END;

CLOSE(f);

END.

Observaţie: Algoritmul sortării prin selecţie directă a fost puţin modificat în această ultimă aplicaţie. În algoritmul clasic, pentru fiecare element curent se caută minimul (respectiv maximul) sau poziţia lor din subşirul rămas de sortat (pentru elem. i se ia j de la i+1 încolo), apoi la sfârşit se face interschimbarea lui cu minimul. În acest algoritm, fiecare posibil minim se interschimbă cu elementul curent (deci se execută mult mai multe interschimbări). Elevii preferă totuşi acest din urmă algoritm datorită simplităţii codului.

Aplicaţie3: Se citesc n fracţii dintr-un fişier text: pe primul rând e scris n, pe al doilea numere naturale corespunzătoare numărătorilor, iar pe al treilea – numitorilor. Să se afişeze fracţiile reductibile ordonate crescător.

Exemplu: pentru 3/6, 5/15, 2/11 vom obţine 5/15, 3/6.

Program C++:

#include <iostream.h>

#include <conio.h>

#include

struct fractie {int nr, nu;};

ifstream f(”fractii.txt”);

int cmmdc (int a, int b){

while (a!=b) if (a>b) a=a-b;

else b=b-a;

return a;}

void afisare (fractie a){

cout<<a.nr<<”/”a.nu<<” ”;}

void main() {

int i, j, n, fractie a[20], aux;

f>>n>>endl;

for(i=1; i<=n; i++) f>>a[i].nr; f>>endl;

for(i=1; i<=n; i++) f>>a[i].nu;

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

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

if (a[i].nr/a[i].nu>a[j].nr/a[j].nu) {

aux=a[i];

a[i]=a[j];

a[j]=aux;}

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

if (cmmdc(a[i]. nr, a[i].nu) !=1) afisare(a[i]);

f.close();

getch(); }

Program Pascal:

PROGRAM SORTSEL3;

TYPE fractie=RECORD

nr, nu:integer; END;

vector= ARRAY[1..20] OF fractie;

VAR a:vector; aux:fractie;

i,j n: INTEGER; f:TEXT;

FUNCTION cmmdc (a,b: INTEGER):INTEGER;

BEGIN

WHILE a<>b DO

IF a>b THEN a:=a-b

ELSE b:=b-a;

cmmdc:= a;

END;

PROCEDURE afisare (a:fractie)

BEGIN

WRITE(a.nr, ’/’,a.nu, ’ ’;

END;

BEGIN

ASSIGN( f, ’fractii.txt’);

RESET(f);

READLN(f,n);

FOR i :=1 TO n DO READ (f, a[i].nr); READLN(f);

FOR i :=1 TO n DO READ (f, a[i].nu);

FOR i:= 1 TO n-1DO

FOR j:= i+1 TO n DO

IF a[i].nr/a[i].nu>a[j].nr/a[j].nu THEN

BEGIN

aux:=a[i];

a[i]:=a[j];

a[j]:=aux;

END;

FOR i:=1 TO n DO

IF cmmdc(a[i].nr, a[i].nu)<>1 THEN afisare(a[i]);

CLOSE(f);

END.

Mergi la pagina METODE DE SORTARE