Name:proiectinfo Type:C++ source file
1
2
3
4
{Sortare prin ‘interclasare’
5
6
[MergeSort]
7
8
9 < Haiduc Andrei,Mare Raul >
10 //profesor coordonator:Șandor Nicoleta
11
12
13 }
14
#include <iostream>
Sources [Link]
1
2
Cuprins{
3
4 01 Descriere
5
<an apariţie,inventator,principiu,algoritm în C++>
6
7
8
9
10
11
12
13
14 }
using namespace std;
Sources [Link]
1
2
Cuprins{
3
4 01 Descriere
5
<an apariţie,inventator,principiu,algoritm în C++>
6
7
8 02 Detalii
<complexitate şi
9 observații,comparare cu alte
10 sortări>
11
12
13
14 }
using namespace std;
Sources [Link]
1
2
Cuprins{
3
4 01 Descriere
5
<an apariţie,inventator,principiu,algoritm în C++>
6
7
8 02 Detalii
<complexitate şi
9 observații,comparare cu alte
10 sortări>
11
12
03 Animaţie
13 <animaţie>
14 }
using namespace std;
Process returned 0 (0x0) execution time : 0.069 s
1
2
3 01 {
4
5
6
[Descriere]
7
8
9 cout << "Hello world!" <<
10
11 endl;
}
12
13
14
int main(){
OneDrive\Desktop\ddvjf [Link]
1
2
An apariție &&‘inventator’
3
4 {
5
6
MergeSort a aparut în anul 1945,fiind
7 inventat de matematicianul
8
John von Neumann.
9
10 }
11
12
13
14
<global>
<global> Common Files\Intel
1
2
Principiu < /1 > {
3
4
5
“MergeSort” este o metodă eficientă de sortare bazată pe
6
comparații care urmează abordarea de programare Divide-Et-
7
8
Impera.”MergeSort” împarte un vector nesortat în sub-vectori
9
până când fiecare conține un element, apoi îmbină în mod
10
repetat sub-vectorii până când rămâne un singur vector sortat.
11
12
13
14 }
sorting…
Algoritm in C++
#include <iostream>
void sortare(int a[],int st, int dr) {
1 using namespace std; if(st<dr) {
int b[100001];
2 void interclasare(int a[], int st, int dr) { int mij=(st+dr)/2;
sortare(a,st,mij);
3 int mij=(st+dr)/2;
sortare(a,mij+1,dr);
4 int i=st, j=mij+1,k=0; interclasare(a,st,dr);
while(i<=mij&&j<=dr) {
5 if(a[i]<a[j]) }
}
6 b[++k]=a[i++];
int main() {
else
7 int n,v[100001];
b[++k]=a[j++];
8 } cin>>n;
for(int i=1; i<=n; i++) {
9 while(i<=mij) { cin>>v[i];
b[++k]=a[i++];
10 } }
sortare(v,1,n);
11 while(j<=dr) {
for(int i=1;i<=n;i++)
12 b[++k]=a[j++]; {
///copiem elem sortate din b inapoi in a
13 } cout<<v[i]<<" ";
}
14 for(i=st,j=1; i<=dr; i++,j++) { return 0;
a[i]=b[j];
}
}
}
Debug\[Link] Program Files (x86)\Brackets
1
2
{
Dacă vectorul este de lungime 0 sau 1, atunci
3
este deja sortat. Altfel:
4
5 Împarte vectorul nesortat în doi sub-
6 vectori aproximativ egali.
7
8
9
10
11
12
13
14 }
#include<cmath>
Debug\[Link] Program Files (x86)\Brackets
1
2
{
Dacă vectorul este de lungime 0 sau 1, atunci
3
este deja sortat. Altfel:
4
5 Împarte vectorul nesortat în doi sub-
6 vectori aproximativ egali.
7 Sortează fiecare sub-vector recursiv.
8
9
10
11
12
13
14 }
#include<cmath>
Debug\[Link] Program Files (x86)\Brackets
1
2
{
Dacă vectorul este de lungime 0 sau 1, atunci
3
este deja sortat. Altfel:
4
5 Împarte vectorul nesortat în doi sub-
6 vectori aproximativ egali.
7 Sortează fiecare sub-vector recursiv.
8
9 Se interclasează și se obține vectorul
10 inițial sortat.
11
12
13
14 }
#include<cmath>
Process returned 0 (0x0) execution time : 0.069 s
1
2
3 02 {
4
5
6
7
[Detalii]
8
9
10 int mij=(st+dr)/2;
11
}
12
13
14
int main(){
[Link] if(a[i]<a[j])
1
2
Complexitate &&‘observatii’ {
3
4 -complexitatea sortării prin interclasare este O(n⋅logn);
5
6
7
8
9
10
11
12
13
14 }
#include <fstream>
[Link] if(a[i]<a[j])
1
2
Complexitate &&‘observatii’ {
3
4 -complexitatea sortării prin interclasare este O(n⋅logn);
5 -pentru interclasare este este necesar un spațiu de memorie suplimentar, de
6 dimensiunea tabloului care se sortează;
7
8
9
10
11
12
13
14 }
#include <fstream>
[Link] if(a[i]<a[j])
1
2
Complexitate &&‘observatii’ {
3
4 -complexitatea sortării prin interclasare este O(n⋅logn);
5 -pentru interclasare este este necesar un spațiu de memorie suplimentar, de
6 dimensiunea tabloului care se sortează;
7 -în secvența de mai sus tabloul b a fost declarat global;
8
declararea sa locală putând duce la depășirea stivei;
9
10
11
12
13
14 }
#include <fstream>
[Link] if(a[i]<a[j])
1
2
Complexitate &&‘observatii’ {
3
4 -complexitatea sortării prin interclasare este O(n⋅logn);
5 -pentru interclasare este este necesar un spațiu de memorie suplimentar, de
6 dimensiunea tabloului care se sortează;
7 -în secvența de mai sus tabloul b a fost declarat global;
8
declararea sa locală putând duce la depășirea stivei;
9
10 - o soluție pentru această situație poate fi alocarea dinamică a tabloului auxiliar.
11
12
13
14 }
#include <fstream>
cout<<v[i]<<" "; int main() {
1 Comparație Merge sort VS Quick Sort
2
3 {
4 Partiția elementelor din vector: la merge sort, vectorul este împărțit în doar
5 2 jumătăți (adică n/2), în timp ce la quick sort, vectorul este împărțit în orice
6 raport.
7
8
9
10
11
12
13
14 }
interclasare(a,st,dr);
cout<<v[i]<<" "; int main() {
1 Comparație Merge sort VS Quick Sort
2
3 {
4 Partiția elementelor din vector: la merge sort, vectorul este împărțit în doar
5 2 jumătăți (adică n/2), în timp ce la quick sort, vectorul este împărțit în orice
6 raport.
7
Complexitatea cazului cel mai rău: complexitatea cazului cel mai rău la quick
8
sort este O(n^2), deoarece este nevoie de o mulțime de comparații în cea mai
9
proastă stare, în timp ce la merge sort, cel mai rău caz și cazul mediu au
10
aceleași complexități O(nlog n).
11
12
13
14 }
interclasare(a,st,dr);
int b[10001]; a[i]=b[j];
1 }
2
3 Eficiență: merge sort este mai eficient și funcționează mai rapid decât quick
4 sort în cazul unui vector sau seturi de date mai mari, însă quick sort este
5 mai eficient și funcționează mai rapid decât merge sort în cazul unui vector
6 mai mic sau seturi de date mai mici.
7
8
9
10
11
12
13
14 }
while(i<=mij&&j<=dr)
int b[10001]; a[i]=b[j];
1 }
2
3 Eficiență: merge sort este mai eficient și funcționează mai rapid decât quick
4 sort în cazul unui vector sau seturi de date mai mari, însă quick sort este
5 mai eficient și funcționează mai rapid decât merge sort în cazul unui vector
6 mai mic sau seturi de date mai mici.
7
8 Metoda de sortare: quick sort este o metodă de sortare internă în care datele
9 sunt sortate în memoria principală, în timp ce merge sort este o metodă de
10 sortare externă în care datele care urmează să fie sortate nu pot fi stocate în
11 memorie și au nevoie de memorie auxiliară pentru sortare.
12
13
14 }
while(i<=mij&&j<=dr)
Process terminated with status 0 (0 minute(s), 7
cout<<n<<endl;
second(s))
}
03
1
2
3
4
5
{Animație}
6 void sortare(int a[],int st, int dr) {
7 if(st<dr) {
int mij=(st+dr)/2;
8
sortare(a,st,mij);
9 sortare(a,mij+1,dr);
10 interclasare(a,st,dr);
11 }
}
12
}
13
14
Press any key to continue.
using namespace std; return 0;
1
}
7 3 55 2 11 44 66
2
3
4
5
6
7
8
9
10
11
12
13
14 }
Process terminated with status 0 (0 minute(s), 1 second(s))
using namespace std; return 0;
1
}
7 3 5 2 1 4 6
2
3
4
5 7 3 5 2 1 4 6
6
7
8
9
10
3 7 2 5
11
12
13
14 }
Process terminated with status 0 (0 minute(s), 1 second(s))
using namespace std; return 0;
1
}
7 3 5 2 1 4 6
2
3
4
5 2 3 5 7 1 4 6
6
7
8
9
10
11
12
13
14 }
Process terminated with status 0 (0 minute(s), 1 second(s))
using namespace std; return 0;
1
}
7 3 5 2 1 4 6
2
3
4
5 2 3 5 7 1 4 6
6
7
8
9
10
11
12
13
14 }
Process terminated with status 0 (0 minute(s), 1 second(s))
sortare(a,st,mij); 1+1=2
Surse{
1
2
3
4
[Link]
5 merge-sort/
6 [Link]
7 [Link]
8 [Link]
[Link]
9
[Link]
10
11
12
13
14 }
Surse accesate la data de 11 mai 2024,
ora:19:46
Mulțumim
pentru atenție!