Algoritmos De Ordenamiento

ALGORITMOS DE ORDENAMIENTO
COUNTING SORT

CHRISTIAN ESTEBAN ALDANA ROZO
BRAYAN STIF FORERO CRUZ
GIOVANNY GUZMÁN CÉSPEDES
JORGE MEJIA

Profesora:
DIANA MABEL DIAZ

UNIVERSIDAD PILOTO DE COLOMBIA
INGENIERIA DE SITEMAS
ANALISIS Y DISEÑO DE ALGORTIMOS
BOGOTA D.C.
2010

BIBLIOGRAFIA


http://es.wikipedia.org/wiki/Algoritmo_de_ordenamiento

http://books.google.com.co/books?id=NLngYyWFl_YC&pg=PA168&lpg=PA168&dq=counti
ng+sort+cormen&source=bl&ots=BwVsEEnFb&sig=0BubWTzl9Rk0cwlgkTLZXZlx9vU&hl=es&ei=rtWtTLa2D4O8lQeR55zUBQ&sa=X&oi
=book_result&ct=result&resnum=1&ved=0CBcQ6AEwAA#v=onepage&q&f=false



http://es.wikipedia.org/wiki/Ordenamiento_por_cuentas



http://www.ritmodominicano.com/wiki.php?title=Discusi%C3%B3n:Algoritmo_de_ordena
miento

http://ing.utalca.cl/~jperez/ae/documentos/ordenacion.pdf

HISTORIA
El algoritmo de ordenamiento Counting Sort (Ordenamiento por Cuentas en español) 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, por
ejemplo, los números enteros de un determinado intervalo,sin contar números reales.
El algoritmo fue creado por Harold H. Seward en 1954,

ANÁLISIS DEL ALGORITMO
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 (0apariciones). 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.
1. para i ← 0 hasta r
2.
hacer C[ i ] ← 0
3.
para j ← 1 hasta n
4.
hacer C[A[ j ]] ← C[A[ j ]] + 1
5.
C[i] contiene el número de elementos igual a i6.
para i ← 1 hasta r
7.
hacer C[ i ] ← C[ i ] + C[i -1]
8.
C[i] contiene el número de elementos ≤ i
9.
para j ← n abajo de 1
10.
hacer B[C[A[ j ]]] ← A[ j ]
11.
C[A[ j ]] ← C[A[ j ]] - 1

Se trata de un algoritmo estable cuya complejidad computacional es O(n+k), siendo n el número
de elementos a ordenar y k el tamaño del vector auxiliar (máximo - mínimo). Si este último
intervaloes muy amplio, el algoritmo es ineficiente, ya que el vector auxiliar tiene un tamaño
excesivamente grande, lo que supondría un gran coste en memoria y también en tiempo.
Con lenguajes de programación que no permitan definir vectores cuyo primer índice sea un valor
distinto de 0 ó 1 es necesario realizar una traducción de los valores. Por ejemplo, si el intervalo es
[4,10] y el vectorauxiliar se define como vaux = vector[1..7], el valor 6 deberá incrementar el
contador de la posición vaux[3].Si en lugar de esta simple traducción se utilizan funciones más
complejas, entonces el algoritmo se denominaría bucket sort.
Counting sort es un algoritmo de ordenamiento similar al algoritmo de Bucket sort, este algoritmo
tiene la ventaja de conocer el rango de los números de la matriz aordenar (matriz A). Utiliza este
rango para crear una matriz C de esta longitud. Cada índice i en C matriz se utiliza para contar el
número de elementos en una cuenta con el valor, y luego cuenta almacenada en C se puede
utilizar para poner los elementos de A en su posición correcta en la matriz resultante ordenados.
El algoritmo fue creado por Harold H. Seward en 1954.

CORRECTITUD
INICIO:Los datos de entrada para desarrollar el algoritmo son un vector A con los números a organizar y
una constante k que será el limite.
MANTENIMIENTO (INVARIANTE)
El único valor que no cambia dentro del desarrollo del algoritmo es el valor de K, puesto que es
una constante que nos dará el número de posiciones que tendrá el vector C.
FINALIZACIÓN
Después que los datos de entrada han pasado por...