CountSort

Sortarea prin numărare CountSort

Informaţii generale:

Această metodă constă în construirea unui nou vector, y, care are aceeaşi dimensiune ca şi vectorul de sortat, x, în care se vor memora elementele din x ordonate crescător. Fiecare element din x se compară cu celelalte elemente ale vectorului pentru a determina câte elemente mai mici decât el se află în vector. Acest element se va aşeza în vectorul sortat ţinând cont că în faţa lui trebuie să fie elementele mai mici.

Prezentarea algoritmului:

Se folosesc trei vectori:

- vectorul sursă (vectorul nesortat): x;
- vectorul destinaţie (vectorul sortat): y;
- vectorul numărător (vectorul de contoare): k.

Pentru a se cunoaşte poziţia în care va fi inserat fiecare element, se parcurge vectorul sursă x şi se numără în vectorul k, pentru fiecare element x[i], câte elemente au valoarea mai mică decât x[i]. Aşadar, elementul k[i] este un contor pentru elementul x[i], reprezentând câte elemente sunt mai mici decât el şi arată de fapt poziţia în care trebuie copiat în vectorul y.

Se folosesc următoarele variabile de memorie:

- x, y, k pentru vectori şi n pentru lungimea vectorilor; vectorul k fiind un vector de contoare, elementele lui se iniţializează cu 0;
- variabila i pentru parcurgerea vectorului sursă în vederea numărării pentru fiecare element x[i] şi apoi pentru parcurgerea vectorului sursă în vederea copierii elementelor sale în y;
- variabila j pentru parcurgerea elementelor situate după elementul curent în vectorul sursă x: pentru fiecare comparare x[i] cu x[j], se incrementează fie k[i] (x[i] >x[j]), fie k[j] (x[i] ≤x[j]);

Exemplu: Fie vectorul x=[ 7,8,2,9]

Prima parcurgere i=1 si j=2,3,4:

i=1

y: Parcurgere pentru numărare: dacă x[i]>x[j] atunci k[i] ←k[i]+1altfel k[j]← k[j]+1;

j=2	0	1	0	7>8: Nu →k[2]=k[2]+1=1
j=3	1	1	0	7>2: Da→k[1]=k[1]+1=1
j=4	1	1	1	7>9: Nu→k[4]=k[4]+1=1

A doua parcurgere i=2 si j=3,4:

i=2

y: Parcurgere pentru numărare: dacă x[i]>x[j] atunci k[i] ←k[i]+1altfel k[j]← k[j]+1;

j=3	1	2	0	1	8>2: Da→k[2]=k[2]+1=2
j=4	1	2	0	2	8>9: Nu→k[4]=k[4]+1=2

A treia parcurgere i=3 si j=4:

i=3

y: Parcurgere pentru numărare: dacă x[i]>x[j] atunci k[i] ←k[i]+1altfel k[j]← k[j]+1;

j=4

2>9: Nu→k[4]=k[4]+1=3

Parcurgere pentru copiere

y: 1 2 3 4

i=1		7			x[1]→ y[k[1]+1]=y[1+1]=y[2]
i=2		7	8		x[2]→ y[k[2]+1]=y[2+1]=y[3]
i=3	2	7	8		x[3]→ y[k[3]+1]=y[0+1]=y[1]
i=4	2	7	8	9	x[4]→ y[k[4]+1]=y[3+1]=y[4]
i=4					i=n→ terminare copiere

Observaţie:

Elementul x[i] se copiază în noul vector y pe poziţia indicată de k[i], la care se adaugă valoarea 1, pentru a îi face loc elementului însuşi.

Varianta pseudocod a algoritmului:

pentru i←1,n execută k[i]←0;

pentru i←1,n-1 execută

pentru j←i+1,n execută

dacă x[i]>x[j] atunci k[i] ←k[i]+1

altfel k[j] ←k[j]+1;

sfârşit dacă;

sfârşit pentru;

pentru i←1,n execută y[k[i]+1]←x[i];

sfârşit pentru;

pentru i←1,n execută scrie y[i];

sfârşit pentru;

Pentru acest algoritm de sortare nu putem spune că există caz favorabil, nefavorabil sau mediu, deoarece numărul de paşi efectuaţi este n² indiferent de structura datelor de intrare. Aşadar, ordinul de complexitate este O(n²).

Implementare C++:

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

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

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

if(x[ i ] > x[ j ]) k[ i ]++;

else k[ j ]++;

for (i=0;i<n;i++) y[k[i]]=x[i];

for (i=0;i<n;i++) cout<<y[i]<<” “;

Implementare Pascal:

for i:=1 to n do k[i]:=0;

for i:=1 to n-1 do

for j:=i+1 to n do

if x[ i ] > x[ j ] then k[ i ]:=k[ i ]+1;

else k[ j ]:=k[ j ]+1;

for i:=1 to n do y[k[i]+1]:=x[i];

for i:=1 to n do write (y[i],’ );

Mergi la pagina METODE DE SORTARE

Aplicatii

Aplicaţie1: Se citeşte un vector a cu n elemente cifre. Afişaţi cel mai mic număr natural care se poate forma cu toate cele n cifre din vectorul a.

Exemplu: Dacă a este compus din 5 0 3 0 1, atunci numărul cerut este 10035.

Program C++:

#include <iostream.h>

#include <conio.h>

int n,i,j, a[20], b[20], k[20];

void main() {

cin>>n;

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

for(i=1; i<=n; i++) k[i]=0;

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

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

if (a[i]>a[j]) k[i]++;

else k[j]++;

for(i=1; i<=n; i++) b[k[i]]=a[i];

if (b[1]==0){

i=2;

while (b[i]==0) i++;

b[1]=b[i]; b[i]=0;}

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

getch(); }

Program Pascal:

PROGRAM CountSort1;

TYPE vector= ARRAY[1..20] OF INTEGER;

VAR a,b,k:vector;

i,j, n: INTEGER;

BEGIN

READLN(n);

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

FOR i:= 1 TO n DO k[i]:=0;

FOR i:= 1 TO n-1 DO

FOR j:= i+1 TO n DO

IF a[i]>a[j] THEN k[i]:=k[i]+1

ELSE k[j]:=k[j]+1;

FOR i:= 1 TO n DO b[k[i]]:=a[i];

IF b[1]=0 THEN

BEGIN

i:=2;

WHILE b[i]=0 DO i:=i+1;

b[1]:=b[i]; b[i]:=0;

END;

FOR i:= 1 TO n DO WRITE(b[i]);

END.

Aplicaţie2: Se citeşte din fişierul date.in o matrice cu n linii şi m coloane, având elemente numere întregi. Să se ordoneze crescător elementele de pe fiecare linie a matricii.

Program C++:

#include <iostream.h>

#include <conio.h>

#include

ifstream f(”date.in”);

int a[20][20],x[20], m, n, i ,j;

void countsort(int x[20]){

int k[20],y[20], i, j;

for(i=1; i<=m; i++) k[i]=0;

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

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

if (x[i]>x[j]) k[i]++;

else k[j]++;

for(i=1; i<=m; i++) y[k[i]]=x[i];

for(i=1; i<=m; i++) x[i]=y[i];}

void main() {

f>>n>>m;

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

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

f>>a[i][j];

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

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

countsort (x);

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

}

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

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

cout<<a[i][j]<<” ”;

cout<<endl;}

f.close();

getch(); }

Program Pascal:

PROGRAM CountSort2;

TYPE vector= ARRAY[1..20] OF INTEGER;

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

x:vector;

i,j,m, n: INTEGER; f:TEXT;

PROCEDURE countsort (VAR x:vector);

VAR y,k:vector; i,j:INTEGER;

BEGIN

FOR i:= 1 TO m DO k[i]:=0;

FOR i:= 1 TO m-1 DO

FOR j:= i+1 TO m DO

IF x[i]>x[j] THEN k[i]:=k[i]+1

ELSE k[j]:=k[j]+1;

FOR i:= 1 TO n DO y[k[i]]:=x[i];

FOR i:= 1 TO n DO x[i]:=y[i];

END;

BEGIN

ASSIGN (f, ’date.in’);

READ(f, m, n);

FOR i:= 1 TO n DO

FOR j:= 1 TO m DO

READ(f, a[i,j]);

FOR i:= 1 TO n DO

BEGIN

FOR j:= 1 TO m DO x[j]:=a[i,j];

countsort (x);

FOR j:= 1 TO m DO a[i,j]:=x[j];

END;

FOR i:= 1 TO n DO BEGIN

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

WRITELN;

END;

CLOSE(f);

END.

Observaţie: Am folosit o funcţie în care am făcut sortarea fiecărei linii în parte, sub forma vectorului x[m]. Pentru sortarea prin numărare au mai fost necesari încă doi vectori de aceeaşi dimensiune, k şi y. În Pascal a trebuit să definim tipul vector pentru a putea transmite ca parametru vectorul de lucru x[m].

Mergi la pagina METODE DE SORTARE