URI (BEECROWD) - 1259 - Pares e Ímpares - Estruturas - C e C++

Esse exercício que trago pra vocês é mais um da categoria de estruturas do beecrowd e chama-se pares e ímpares.

Plataforma: URI (BEECROWD)

Problema: 1259

Enunciado:

Considerando a entrada de valores inteiros não negativos, ordene estes valores segundo o seguinte critério:

Primeiro os Pares

Depois os Ímpares

Sendo que deverão ser apresentados os pares em ordem crescente e depois os ímpares em ordem decrescente.

Linguagens: C e C++

Solução:

A ideia foi ler os valores e armazená-los em arrays de pares e ímpares em cada caso. Depois bastava ordenar os arrays nas formas crescente e decrescente. Utilizei o algoritmo do merge sort para isso.

Código em C:

#include <stdio.h>
void merge(int arr[], int l, int m, int r) { 
    int i, j, k; 
    int n1 = m - l + 1; 
    int n2 =  r - m; 
    int L[n1], R[n2]; 
    for (i = 0; i < n1; i++) 
        L[i] = arr[l + i]; 
    for (j = 0; j < n2; j++) 
        R[j] = arr[m + 1+ j]; 
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) { 
        if (L[i] <= R[j]) { 
            arr[k] = L[i]; 
            i++; 
        } 
        else { 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 
    while (i < n1) { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 
    while (j < n2) { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
} 
void mergeSort(int arr[], int l, int r) { 
    if (l < r) { 
        int m = l + (r - l) / 2; 
        mergeSort(arr, l, m); 
        mergeSort(arr, m + 1, r); 
        merge(arr, l, m, r); 
    } 
} 
int main() {
    int n, indice = 0, odd = 0, even = 0;
    scanf("%i", &n);
    unsigned int valor, pares[n], impares[n];
    while (n--) {
        scanf("%u", &valor);
        if (valor & 1)
            impares[odd++] = valor;
        else
            pares[even++] = valor;
    }
    mergeSort(pares, 0, even - 1); 
    mergeSort(impares, 0, odd - 1); 
    while (indice < even)
        printf("%u\n", pares[indice++]);
    while (--odd >= 0)
        printf("%u\n", impares[odd]);
    return 0;
}

Código em C++:

#include <iostream>
using namespace std;
void merge(unsigned int arr[], int l, int m, int r) { 
    int i, j, k; 
    int n1 = m - l + 1; 
    int n2 =  r - m; 
    unsigned int L[n1], R[n2]; 
    for (i = 0; i < n1; i++) 
        L[i] = arr[l + i]; 
    for (j = 0; j < n2; j++) 
        R[j] = arr[m + 1+ j]; 
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) { 
        if (L[i] <= R[j]) { 
            arr[k] = L[i]; 
            i++; 
        } 
        else { 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 
    while (i < n1) { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 
    while (j < n2) { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
} 
void mergeSort(unsigned int arr[], int l, int r) { 
    if (l < r) { 
        int m = l + (r - l) / 2; 
  
        mergeSort(arr, l, m); 
        mergeSort(arr, m + 1, r); 
  
        merge(arr, l, m, r); 
    } 
} 
int main() {
    int n, indice, odd = 0, even = 0;
    cin >> n;
    unsigned int valor, pares[n], impares[n];
    while (n--) {
        cin >> valor;
        if (valor & 1)
            impares[odd++] = valor;
        else
            pares[even++] = valor;
    }
    mergeSort(pares, 0, even-1); 
    mergeSort(impares, 0, odd-1); 
    indice = 0;
    while (indice < even)
        cout << pares[indice++] << endl;
    while (--odd >= 0)
        cout << impares[odd] << endl;
    return 0;
}