Created
August 29, 2012 15:06
-
-
Save felialois/3514008 to your computer and use it in GitHub Desktop.
Tarea 3 ej5
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// | |
// 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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment