Bella: Created page with "= Lectie = == Metode de sortare == === 1 Sortarea prin interschimbare directa === Se dă un vector de `n` elemente. Să se sorteze prin metoda interschimbarii directe...."

2019-04-05T13:37:49Z

Created page with "= Lectie = == Metode de sortare == === 1 Sortarea prin interschimbare directa === Se dă un vector de <tt>n</tt> elemente. Să se sorteze prin metoda interschimbarii directe...."

New page

= Lectie =
== Metode de sortare ==
=== 1 Sortarea prin interschimbare directa ===
Se dă un vector de <tt>n</tt> elemente. Să se sorteze prin metoda interschimbarii directe.
Metoda interschimbarii directe: Vom compara fiecare element v[i] cu toate elementele de la dreapta lor, si oridecate ori gasim un element mai mic ca acesta, vom interschimba valoarea din v[i] cu valoarea din v[j].

<syntaxhighlight>
for ( i = 0; i < n - 1; i++ )
for ( j = i + 1; j < n; j++ )
if ( v[i] > v[j] ) {
aux = v[i];
v[i] = v[j];
v[j] = aux;
}
}</syntaxhighlight>
=== 2 Metoda bulelor ===
Descrierea metodei: se parcurge vectorul și se compară fiecare element cu succesorul său. Dacă nu sunt în ordine cele două elemente se interschimbă între ele. Vectorul se parcurge de mai multe ori, până când la o parcurgere completă nu se mai execută nicio interschimbare între elemente (vectorul este sortat). Vom folosi o variabilă steguleţ pentru a marca faptul ca am efectuat o interschimbare, marcare care ne semnalează că incă vectorul nu a devenit sortat.

<syntaxhighlight>
do {
ok = 1; // pp ca vectorul este sortat
for ( i = 0; i < n - 1; i++ ) // parcurgem toate perechile de elemente vecine si le comparam
if ( v[i] > v[i+1] ) { // daca am gasit un element mai mare decat vecinul sau din dreapta
aux = v[i]; // interschimbam cele doua valori vecine
v[i] = v[i+1];
v[i+1] = aux;
ok = 1; // si marcam ca am facut o modificare, deci nu a fost sortat
}
}while(!ok); // repetam parcurgerea cata vreme nu avem sortat vectorul
}</syntaxhighlight>

Optimizare: Cum metoda garanteaza ca la prima parcurgere, pe ultima pozitie va ajunge cel mai mare element, la urmatoarea parcurgere nu mai este necesar sa luam in calcul si acest element. De asemenea, la a doua parcurgere, avem garantia ca pe penultima pozitie va ajunge cel mai mare element din elementele ramase, deci la urmatoarea parcurgere nu il vom mai lua in calcul nici pe acesta. ca o generalizare, la o parcurgere '''p''', vom avea de sortat doar '''n-p''' valori.

<syntaxhighlight>
do {
ok = 1; // pp ca vectorul este sortat
p = 1; // numarul de parcurgerii vectorului curente
for ( i = 0; i < n - p; i++ ) // parcurgem toate perechile de elemente vecine si le comparam
if ( v[i] > v[i+1] ) { // daca am gasit un element mai mare decat vecinul sau din dreapta
aux = v[i]; // interschimbam cele doua valori vecine
v[i] = v[i+1];
v[i+1] = aux;
ok = 1; // si marcam ca am facut o modificare, deci nu a fost sortat
}
p++; // trecem la urmatoarea parcurgere a vectorului
}while(!ok); // repetam parcurgerea cata vreme nu avem sortat vectorul
}</syntaxhighlight>

=== 3 Sortarea prin selecție (select sort) ===
Se dă un vector de <tt>n</tt> elemente. Să se sorteze prin metoda selecției. Prin sortare înțelegem ordonare crescătoare a elementelor vectorului. Metoda selecției este următoarea: vom găsi maximul din vector, împreună cu poziția sa. Apoi vom interschimba maximul cu ultimul element din vector. Astfel ne vom asigura că ultimul element este chiar cel corect în vectorul ordonat. Ne-a rămas astfel un vector cu <tt>n-1</tt> elemente, care trebuie sortat. Vom proceda la fel: vom găsi maximul în subvectorul de <tt>n-1</tt> elemente, precum și poziția lui, și-l vom muta la coadă, rezultînd un vector de <tt>n-2</tt> elemente. Continuăm procedura pînă ce vectorul este sortat.

Iată o exemplificare grafică:

{| style="border-spacing:0;"
| style="border:0.05pt solid #000000;padding:0.0382in;"|
'''9''' 2 8 3 6 5 3 9 6 |
6 2 8 3 6 5 3 '''9''' | 9
6 2 '''8''' 3 6 5 3 | 9 9
'''6''' 2 3 3 6 5 | 8 9 9
5 2 3 3 '''6''' | 6 8 9 9
'''5''' 2 3 3 | 6 6 8 9 9
'''3''' 2 3 | 5 6 6 8 9 9
'''3''' 2 | 3 5 6 6 8 9 9
2 | 3 3 5 6 6 8 9 9
<nowiki>|</nowiki> 2 3 3 5 6 6 8 9 9

|}

Iată programul:

<syntaxhighlight>// avem vectorul v de n elemente
for ( i = n – 1; i > 0; i-- ) { // pozitia ultimului element din subvector
max = v[0];
p = 0; // p este poziția maximului
for ( j = 1; j <= i; i++ )
if ( v[j] > max ) { // memoram noul maxim si pozitia lui
max = v[j];
p = j;
}
// interschimbam maximul de pe pozitia p cu ultimul element, pe pozitia i
v[p] = v[u];
v[u] = max;
}</syntaxhighlight>

O alta modalitate de a implementa aceasta metoda este de a cauta minimul si a-l aduce pe prima pozitie in vector.

<syntaxhighlight>
for ( i = 0; i < n - 1; i++ ){
min = div[i]; p = i;
for ( j = i + 1; j < n; j++ )
if ( min > v[j] ){
max = v[j];
p = j;
}
v[p] = v[i];
v[i] = max;
}
</syntaxhighlight>

Vă recomand folosirea algoritmului de sortare prin selecție și nu a sortării cu bule, deoarece face mai puține operații. În practică el este de cinci pînă la zece ori mai rapid. Desigur, și mai rapidă este sortarea prin vectori de frecvență, numită și sortare prin numărare, atunci cînd ea poate fi aplicată (cînd numerele sînt foarte mici).

=== 4 Sortarea prin insertie ===
<syntaxhighlight>
#include <iostream>

using namespace std;

#include <stdio.h>

int main(){
int n, i, v[1000], x;

// citim sirul de n elemente si le inseram in vector inainte de ultimul element mai mare ca el
scanf( "%d", &n );

for( i = 0; i < n; i++ ) {
scanf( "%d", &x ); // citim elem de pe pozitia i, deci pana acum am pus elem pana la i-1
int p = i - 1; // pornim de la ultimul element adaugat in vector
while(p >= 0 && v[p] > x ) // cata vreme elementul curent e mai mare decat x
v[p + 1] = v[p], p --; // il mut la dreapta
v[p + 1] = x; // acum a[p] e mai mic sau egal cu x, si a[p+1] e liber
}

for( i = 0; i < n; i++ )
printf( "%d ", v[i] );

return 0;
}

</syntaxhighlight>

=== 5 Sortarea prin numarare ===
Acest tip de sortare l-am folosit cand am studiat vectorii caracteristi ( de frecventa )

=== 5 Sortarea rapida - Quicksort ===
Algoritmul acestui tip de sortare va fi studiat in clasa a 10-a. Putem sorta rapid insa folosing functia predefinita din biblioteca algorithm care are complexitate O( n log n)
<syntaxhighlight>
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
int n, i, j, v[1000], aux;

// citim sirul de n elemente si memoram valorile sale in vectorul v
scanf( "%d", &n );
for( i = 0; i < n; i++ )
scanf( "%d", &v[i] );

sort( v, v + n );
for( i = 0; i < n; i++ )
printf( "%d ", v[i] );

return 0;
}
</syntaxhighlight>

== Aplicatii ==
=== Implementare sortare prin interschimbare ===
==== [https://www.pbinfo.ro/?pagina=probleme&id=509 Ordonare] ====
- sortare crescatoare
Se dă un sir cu n(1 ≤ n ≤ 1000) elemente numere naturale x<sub>i</sub> < 1.000.000.000. Să se ordoneze crescător elementele vectorului.
- sortare descrescatoare ( impllemntati probleme [https://www.pbinfo.ro/?pagina=probleme&id=129 Sortare] )
<syntaxhighlight>
// Metoda interschimbarii directe - complexitate O(n^2)
// Fiecare element v[i] va fi comparat cu elementele din dreapta v[j].
// Daca v[j] e mai mic, interschimbam valorile de pe cele doua pozitii i si j
#include <stdio.h>

int main(){
int n, i, j, v[1000], aux;

// citim sirul de n elemente si memoram valorile sale in vecotrul v
scanf( "%d", &n );
for( i = 0; i < n; i++ )
scanf( "%d", &v[i] );

// sortam elementele
for ( i = 0; i < n - 1; i++ )
for ( j = i + 1; j < n; j++ )
if ( v[i] > v[j] ) {
aux = v[i];
v[i] = v[j];
v[j] = aux;
}

for( i = 0; i < n; i++ )
printf( "%d ", v[i] );

return 0;
}
</syntaxhighlight>

====[https://www.pbinfo.ro/?pagina=probleme&id=86 halfsort] ====
Să se scrie un program care ordonează crescător elementele din prima jumătate a unui vector și descrescător elementele din a doua jumătate.
<syntaxhighlight>
#include <stdio.h>
#include <stdlib.h>

int v[100];

int main(){
FILE *fin = fopen( "halfsort.in", "r" );
FILE *fout = fopen( "halfsort.out", "w" );
int n, i, j, aux;
fscanf(fin, "%d", &n);

for( i = 0; i < n; i++ )
fscanf( fin, "%d", &v[i] );

// sortam crescator elem din prima jumatate
for( i = 0; i < n / 2; i ++ )
for(j = i + 1; j < n / 2; j ++ )
if( v[i] > v[j] ){
aux = v[i];
v[i] = v[j];
v[j] = aux;
}
// sortam descrescator elem din a doua jumatate
for( i = n / 2; i < n; i ++ )
for( j = i + 1; j < n; j ++ )
if( v[i] < v[j] ){
aux = v[i];
v[i] = v[j];
v[j] = aux;
}

for( i = 0; i < n; i++ )
fprintf( fout, "%d ", v[i] );
fclose( fin );
fclose( fout );
return 0;
}

</syntaxhighlight>

Alternativa mai rapida de sortare :
<syntaxhighlight>
#include<cstdio>
#include<algorithm>
using namespace std;
int v[102];
int cmp(int a, int b){
return a > b;
}
int main() {
FILE *fin, *fout;
int n, i, j, aux;

fin = fopen("halfsort.in", "r");
fout = fopen("halfsort.out", "w");
fscanf(fin, "%d", &n );
for (i = 0; i < n; i++)
fscanf( fin, "%d", &v[i] );
sort(v , v + n / 2 );
sort(v + n / 2 , v + n, cmp );

for (i = 0; i < n; i++)
fprintf(fout, "%d ", v[i]);
fclose(fin);
fclose(fout);
return 0;
}
</syntaxhighlight>

=== Implementare Select Sort ===
====[https://www.pbinfo.ro/?pagina=probleme&id=1191 Arhitectura]====
Se citesc n numere naturale reprezentând înălțimile a n clădiri. Cerința problemei este de a realiza un proiect de arhitectură în care clădirile sunt ordonate descrescător după înălțimea lor.

<syntaxhighlight>
#include <stdio.h>
int v[1000];
int main()
{
int i, n, p, max, j;
scanf ( "%d", &n );
for ( i = 0; i < n; i ++ ) {
scanf ( "%d", &v[i] );
}
for ( i = 0; i < n - 1; i ++ ){
max = 0;
for ( j = i; j < n; j ++ ){;
if ( max < v[j] ){
max = v[j];
p = j;
}
}
v[p] = v[i];
v[i] = max;
}
for ( i = 0; i < n; i ++ )
printf ( "%d ", v[i] );
return 0;
}

</syntaxhighlight>

==== [https://www.pbinfo.ro/?pagina=probleme&id=1608 Sortare Divizori]====

<syntaxhighlight>
// Metoda de sortare select sort + numarare divizori folosind descompunerea in factori primi

#include <stdio.h>

int main(){
int n, i, j, v[1000], div[1000], aux, nrdiv, d ;
FILE *fin = fopen( "sortare_divizori.in", "r" );
FILE *fout = fopen ( "sortare_divizori.out", "w" );

fscanf( fin,"%d", &n );
for( i = 0; i < n; i++ ){
fscanf( fin, "%d", & v[i] );
nrdiv = 1;
d = 2;
int x = v[i], p;
while ( d * d <= x ){
p = 0;
while ( x % d == 0 ){
x = x / d;
p ++;
}
nrdiv *= ( p + 1 );
d ++;
}
if ( x > 1 )
nrdiv *= 2;
div[i] = nrdiv;
}

// sortam elementele dupa nr de divizori in ordine crescatoare
int poz, max;
for ( i = 0; i < n - 1; i++ ){
max = div[i]; poz = i;
for ( j = i + 1; j < n; j++ )
if ( max < div[j] || ( max == div[j] && v[poz] > v[j]) ){
max = div[j];
poz = j;
}
aux = v[poz];
v[poz] = v[i];
v[i] = aux;
div[poz] = div[i];
div[i] = max;
}
// afisam vectorul sortat
for( i = 0; i < n; i++ )
fprintf( fout, "%d ", v[i] );

return 0;
}
</syntaxhighlight>

== Sortarea prin numarare ==
Aplicatie: arhitectura 2
Pentru aceasta problema am ales sortarea prin vector de frecventa deoarece, daca am sorta toate de le n = 2 milioane de elemente folosind algoritmii invatati, am avea o complexitate O(n*n) ceea ce ar conduce la depasirea timpului cerut de exectutie.
<syntaxhighlight>
// Sortare prin numarare ( folosim vector de frecventa )
#include <stdio.h>
#include <stdlib.h>

int v[100001]; // val maxima este 100000
int a[2000002]; // 2mil de elemente + 2 pseudocladiri ( santinele )
int main(){
FILE *fin , *fout;
fin = fopen ( "arhitectura2.in", "r" );
fout = fopen ( "arhitectura2.out", "w" );
int n, k, i, nr;

// construim un vector de frecventa pentru a sorta cele n valori
fscanf ( fin , "%d", &n );
for ( i = 0; i < n; i++ ){
fscanf ( fin , "%d", &nr );
v[nr] ++;
}

// parcurgem vectorul de frecventa si reconstruim sirul de n valori, in ordine descrescatoare
k = 0;
for ( i = 100000; i >= 0; i-- )
while ( v[i] != 0 ){
a[++k] = i;
v[i]--;
fprintf ( fout , "%d ", a[k] );
}
fprintf ( fout, "\n");

// pentru fiecare element din sir verificam daca e media valorilor vecine
a[0] = a[k+1] = 0; // pseudocladirile : santinele
for ( i = 1; i <= k; i++ ){
if ( 2 * a[i] == a[ i - 1 ] + a[ i + 1 ] )
fprintf ( fout , "1 " );
else
fprintf ( fout , "0 " );
}
fclose ( fin );
fclose ( fout );
return 0;
}
</syntaxhighlight>

Ca o alternativa mai rapid de implemntat in conditii de olimpiada aveti algormul de mai jos, cu complexitate apropiata de cea a algoritmului anterior, dar care intra in timp. Complexitatea fiin O( n log n ) data de complexitatea algoritmului rapid de sortare definit in biblioteca algorithm.

<syntaxhighlight>
// Sol cu qsort -sort de biblioteca
#include<bits/stdc++.h>
using namespace std;
int v[2000003];
int cmp(int a, int b){
return a>b;
}
int main(){
ifstream fin("arhitectura2.in");
ofstream fout("arhitectura2.out");
int n;
fin >> n;
for(int i=1; i <= n; i++)
fin >> v[i];
sort(v+1, v+n+1, cmp);
for(int i=1; i <= n; i++)
fout << v[i] << " ";
fout << '\n';
for(int i=1; i <= n; i++){
if(2*v[i]==v[i-1]+v[i+1])
fout << "1 ";
else fout << "0 ";
}
}
</syntaxhighlight>

=Tema =
Runda pbinfo
== Optional ==
==== Probleme de studiu ====
* [https://www.pbinfo.ro/?pagina=probleme&id=1123 iepurasi] - Pancake sorting. Sortati conform indicatiilor, fara sa tineti cont ca se cere numarul minim de tap-uri.

Clasa a 6-a lectia 25 - Revision history

Bella: Created page with "= Lectie = == Metode de sortare == === 1 Sortarea prin interschimbare directa === Se dă un vector de n elemente. Să se sorteze prin metoda interschimbarii directe...."

Bella: Created page with "= Lectie = == Metode de sortare == === 1 Sortarea prin interschimbare directa === Se dă un vector de `n` elemente. Să se sorteze prin metoda interschimbarii directe...."