Exercitiu + tema

Exercitiu:

• Se dă un șir cu n elemente, numere întregi. Folosind metoda MergeSort (Sortare prin interclasare), ordonați crescător elementele acestui șir.
• Date de intrare
• Programul citește de la tastatură numărul n, iar apoi cele n elemente ale șirului.
• Date de ieșire
• Programul va afișa pe ecran elementele șirului sortat, separate prin exact un spațiu.
• Restricții și precizări
• 1 ≤ n ≤ 10.000
• elementele șirului vor fi cuprinse între
• -1.000.000.000 și 1.000.000.000
• Exemplu
• Intrare
• 12
• 10 0 -1 -3 1 -4 9 3 -1 -4 3 -4
• Ieșire
• -4 -4 -4 -3 -1 -1 0 1 3 3 9 10

O metoda de rezolvare:

• #include <iostream>
• #include <fstream>
• using namespace std;
• long a[100],b[100];
• void interclasare(int st,int dr)
• {
• int k,mij,i,j;
• if(st<dr)
• {
• if(dr-st==1 && a[st]>a[dr])
• swap(a[st],a[dr]);
• else
• {
• mij=(st+dr)/2;
• interclasare(st,mij);
• interclasare(mij+1,dr);
• k=st-1;
• for(i=st,j=mij+1; i<=mij && j<=dr; )
• {
• if(a[i]<=a[j])
• {
• k++;
• b[k]=a[i];
• i++;
• }
• else
• {
• k++;
• b[k]=a[j];
• j++;
• }
• }
• for( ; i<=mij; i++)
• {
• k++;
• b[k]=a[i];
• }
• for( ; j<=dr; j++)
• {
• k++;
• b[k]=a[j];
• }
• for(k=st; k<=dr; k++)
• a[k]=b[k];
• }
• }
• }
• int main()
• {
• int n,i;
• ifstream f("nr.txt");
• f>>n;
• for(i=1; i<=n; i++)
• f>>a[i];
• interclasare(1,n);
• for(i=1; i<=n; i++)
• cout<<a[i]<<' ';
• return 0;
• }

Tema:

• Se dă un șir cu n elemente, numere întregi. Folosind metoda MergeSort (Sortare prin interclasare), ordonați descrescător elementele acestui șir.
• Exemplu:
• mergesort.in
• 5
• 10 90 5 6 101
• mergesort.out
• 101 90 10 6 5