Probleme Rezolvate

Sa se rearanjeze elementele unui vector astfel incat in vector sa se găsească mai întâi numerele impare şi apoi numerele pare. Se vor realiza două versiuni ale programului, câte una pentru fiecare metodă de sortare care foloseşte strategia divide et impera .
Pentru a rearanja elementele unui vector astfel încât în vector să se găsească mai întâi numerele impare și apoi numerele pare, putem folosi o strategie divide et impera și două metode de sortare: QuickSort și MergeSort .
Metoda QuickSort constă în a alege un element din vector ca pivot și a muta toate elementele mai mici decât pivotul la stânga acestuia și toate elementele mai mari decât pivotul la dreapta acestuia. Apoi, sortăm recursiv sub-vectorii stângi și drepti , până când întregul vector este sortat.
Metoda MergeSort constă în a împărți vectorul în două sub-vectori egali, sortând recursiv fiecare sub-vector și apoi combinând cele două sub-vectori într-un vector sortat mai mare.
Iată implementarea în C++ a celor două metode:
QuickSort

# include < iostream >
using namespace std ;
void swap ( int &a, int &b) {
int temp = a;
a = b;
b = temp ;
}
bool compare ( int a, int b) {
if (a % 2 == 0 && b % 2 == 1 ) {
return true ;
}
if (a % 2 == 1 && b % 2 == 0 ) {
return false ;
}
if (a % 2 == 0 ) {
return a < b;
}
return a > b;
}
int partition ( int a[], int left, int right ) {
int pivot = a[left];
int i = left + 1 ;
int j = right ;
while (i <= j) {
while (i <= j && compare (a[i], pivot)) {
i++;
}
while (i <= j && compare (pivot, a[j])) {
j--;
}
if (i <= j) {
swap (a[i], a[j]);
i++;
j--;
}
}
swap (a[left], a[j]);
return j;
}
void quickSort ( int a[], int left, int right ) {
if (left >= right ) {
return ;
}
int pivotIndex = partition (a, left, right );
quickSort (a, left, pivotIndex - 1 );
quickSort (a, pivotIndex + 1 , right );
}
int main () {
int n;
cout << " Introduceti numarul de elemente din vector: " ;
cin >> n;
int a[n];
cout << " Introduceti elementele vectorului: " ;
for ( int i = 0 ; i < n; i++) {
cin >> a[i];
}
quickSort (a, 0 , n - 1 );
cout << "Vectorul sortat este: " ;
for ( int i = 0 ; i < n; i++) {
cout << a[i] << " " ;
}
return 0 ;
}
MergeSort
# include < iostream >
using namespace std ;
bool compare ( int a, int b) {
if (a % 2 == 0 && b % 2 == 1 ) {
return true ;
}
if (a % 2 == 1 && b % 2 == 0 ) {
return false ;
}
if (a % 2 == 0 ) {
return a < b;
}
return a > b;
}
void merge ( int a[], int left, int mid , int right ) {
int i = left;
int j = mid + 1 ;
int k = 0 ;
int temp [ right - left + 1 ];
while (i <= mid && j <= right ) {
if ( compare (a[i], a[j])) {
temp [k] = a[i];
i++;
} else {
temp [k] = a[j];
j++;
}
k++;
}
while (i <= mid ) {
temp [k] = a[i];
i++;
k++;
}
while (j <= right ) {
temp [k] = a[j];
j++;
k++;
}
for ( int i = left; i <= right ; i++) {
a[i] = temp [i - left];
}
}
void mergeSort ( int a[], int left, int right ) {
if (left < right ) {
int mid = left + ( right - left) / 2 ;
mergeSort (a, left, mid );
mergeSort (a, mid + 1 , right );
merge (a, left, mid , right );
}
}
int main () {
int n;
cout << " Introduceti numarul de elemente din vector: " ;
cin >> n;
int a[n];
cout << " Introduceti elementele vectorului: " ;
for ( int i = 0 ; i < n; i++) {
cin >> a[i];
}
mergeSort (a, 0 , n - 1 );
cout << "Vectorul sortat este: " ;
for ( int i = 0 ; i < n; i++) {
cout << a[i] << " " ;
}
return 0 ;
}