BINGO SORT

Lință Iulia & Toma Karina

SORTAREA
PRIN
SELECȚIE
 #include <iostream>

Sortarea prin using namespace std;

int main()

Selecție
S o r t a r e a î n c a r e a l e g e m , l a fi e c a r e p a s , a u n u i
{
int n, v[1001];
cin>>n;
element (minimul, maximul sau minimul și for (int i=1; i<=n; i++)
maximul), pe care îl vom muta direact pe poziția cin>>v[i];
s a fi n a l ă . for (int i=1; i<n; i++)
Distingem 3 tipuri de sortare prin selecția: {
int mini=v[i], pozmini=i;
• minimului
for (int j=i+1; j<=n; j++)
• maximului if (v[j]<v[pozmini])
• minimului și a maximului (sortarea minimax) {
mini=v[j];
pozmini=j;
}
Complexitate: O(n(n-1))/2
swap (v[i], v[pozmini]);
}
D e c e e s t e e fi c i e n t : for (int i=1; i<=n; i++)
Este un algoritm stabil=dupa un numar de k cout<<v[i]<<" ";
iteratii exista cel putin k elemente care se vor return 0;
}
a fl a p e p o z i t i a l o r fi n a l a i n v e c t o r u l s o r t a t .
 Bingo Sort
Definiț
e
B I N G O S O RT E S T E S O RTA R E A Î N C A R E G Ă S I M M A I Î N T Â I C E L M A I M I C E L E M E N T N U M I T
Bingo Element și apoi parcurgem în mod repetat elementele vectorului pentru a obține
p o z i ț i i l e c o r e c t e a l e t u t u r o r e l e m e n t e l o r. Î n m o d s i m i l a r , g ă s i ț i u r m ă t o r u l e l e m e n t d e b i n g o
pentru următoarea trecere și așa mai departe. Fiecare element distinct este considerat un
element Bingo și chemat în ordine crescătoare.

Complexit
ate
În cel mai bun caz :O(n+m²)
În cel mai rău caz/complexitatea medie: O(n*m)
n-nr de
elemente
m-nr de elemente
Ideea principală a programului:
1.Găsim minimul (elementul „Bingo”)
2. Mutăm elementul minim direct la poziția sa finală, schimbând
poziția sa curentă cu pozția elementului care îi ocupă locul
#include <iostream>

Codul
#include <fstream>
#include <climits>
using namespace std;
ifstream fin ("[Link]");
ofstream fout ("[Link]");
int main()
{
int n, v[1001], maxi=INT_MIN, mini=INT_MAX;
fin>>n;
for (int i=1; i<=n; i++)
{
fin>>v[i];
if (v[i]>maxi)
maxi=v[i];
if (v[i]<mini)
mini=v[i];
}
int bingo=mini;
int nextBingo=maxi;
int nextElePos=1;

simplifica
while (bingo<maxi)
{
int startPos=nextElePos;
for (int i=startPos; i<=n; i++)
{
if (v[i]==bingo)
{
swap(v[i], v[nextElePos]);
nextElePos++;
}

t
else if (v[i]<nextBingo)
nextBingo=v[i];
}
bingo=nextBingo;
nextBingo=maxi;
}
for (int i=1; i<=n; i++)
fout<<v[i]<<" ";
return 0;
}
Codul Original

6/11
 *Câteva precizări despre cod:

[Link]ă sortare este scrisa original pentru o matrice,dar noi am modificat

3. În a doua poză regăsim citirea si afișarea vectorului sortat, deci doar prima
poză este relevantă pentru subiectul proiectului nostru.(totuși vom lăsa și a doua
poză)
Surse
[Link]://[Link]/bingo-sort-
2. Documentul cu sortări de pe
algorithm/t
classroom
 COMPARAREA
COMPLEXITĂȚILOR:
**Pentru a estima complexitatea algoritmului de sortare Bingo, vom
presupune că numărul de elemente distincte m este chiar n/2

Observăm,
așadar, că
Bingo Sort este
mereu mai
eficient
Exemplele folosite pentru crearea graficului
VĂ MULȚUMIM
PENTRU
ATENȚIE!