Tarea 3 ej5

Tarea3ej5.cpp

//
//  main.cpp
//  Tarea 3 ejercici5
//
//  Created by Felipe Alfaro on 8/28/12.
//  Copyright (c) 2012 Felipe Alfaro. All rights reserved.
//
/* Ordenamiento por conteo: El ordenamiento por conteo (counting sort en inglés) es un algoritmo de ordenamiento en el que se cuenta el número de elementos de cada clase para luego ordenarlos. Sólo puede ser utilizado por tanto para ordenar elementos que sean contables (como los números enteros en un determinado intervalo, pero no los números reales, por ejemplo). El primer paso consiste en averiguar cuál es el intervalo dentro del que están los datos a ordenar (valores mínimo y máximo). Después se crea un vector de números enteros con tantos elementos como valores haya en el intervalo [mínimo, máximo], y a cada elemento se le da el valor 0 (0 apariciones). Tras esto se recorren todos los elementos a ordenar y se cuenta el número de apariciones de cada elemento (usando el vector que hemos creado). Por último, basta con recorrer este vector para tener todos los elementos ordenados. Escriba el método void countingSort(int[] arreglo) que ordene los elementos del arreglo utilizando este método. Escriba un programa de ejemplo para probar este método.
 */
#include <iostream>
 
void imprimir(int arreglo[], int largo){ //imprime un arreglo
    for (int x=0; x<largo;x++){ //recorre el arreglo e imprime digito por digito
        std::cout<<arreglo[x];
        std::cout<<(" , ");
    }
    std::cout<<("\n");
}

int contar(int arreglo[],int valor, int largo){ //cuenta la cantidad de un numero en un arreglo
    int cant=0;
    for(int i=0;i<largo;i++){
        if (arreglo[i]==valor)
            cant++;
    }
    return cant;
}
           
           
int max(int arreglo[], int largo){ //retorna el mayor elemento del arreglo
    int mayor;
    mayor=0;

    for (int i=0;i<largo;i++){//recorre el arreglo y compara
        if (mayor<arreglo[i])
            mayor=arreglo[i];
    }
    return mayor;
 };

int min(int arreglo[], int largo){//retorna el menor elemento del arreglo
    int menor;
    menor=1000;
    
    for (int i=0;i<largo;i++){ //recorre el arreglo y compara
        if (menor>arreglo[i])
            menor=arreglo[i];
    }
    return menor;
};

void countingSort(int arreglo[], int largo){
    int mayor=max(arreglo,largo),menor=min(arreglo,largo),tamano,menorC=menor, cont=0;

    tamano=(mayor-menor)+1; //tamano del arreglo nuevo
    
    int vectorAux[tamano],arreglo2[tamano]; //crea un nuevo vector con campos para las apariciones de cada valor
    
    for(int i=0;i<tamano;i++){ //crea un arreglo con los valores entre el menor y el mayor
        arreglo2[i]=menor;
        menor++;
    }

    for (int i=0;i<tamano;i++){ //recorre el vector nuevo de las apariciones
        //y le asigna a cada campo la cantidad de ese valor que se encuentre en el arreglo
        vectorAux[i]=contar(arreglo,menorC,largo); 
        menorC++;
    }

    for (int j=0;j<tamano;j++){ //en el arreglo original acomoda los numeros segun su cantidad de apariciones
        for (int y=0;y<vectorAux[j];y++){
            arreglo[cont]=arreglo2[j];
            cont++;
        }

    }
    imprimir(arreglo,largo);
    std::cout<<("\n");
};


int main(int argc, const char * argv[])
{
    
    int a[]={0,5,5,4,3,2,6,11,13,14,11,12,4,5,6,3,2,9};
    int largo=18;
    countingSort(a,largo);
    return 0;
}