Barrapunto

No hay nada que opinar, está todo (o casi todo) inventado.

Sólo tienes que consultar las dos fuentes clásicas: The Art of Computer Programming [stanford.edu], the Donald E. Knuth [stanford.edu] y Fundamentos de algoritmia [barrapunto.com], the Brassard y Bratley [prenhall.com]

El método más rápido es quicksort pero debes estar familiarizado con programación recursiva aunque investigando encontré una versión de quicksort iterativa (aunque muy larga). Como no sabes cuantos datos vas a manejar y pueden ser muchísimos este método quicksort es el mejor. Hay otros como burbuja, burbuja mejorado, burbuja con bandera, inserción, selección, pero son algoritmos de museo: Interesantes para ver la historia de como se encuentra un algortimo mas eficiente. Tal vez en unos años lleguemos al algoritmo definitivo para comprimir musica y video dejando a MP3, WAV, MPEG, etc.. en el museo.

REsumo si no me equivoco; Burbuja, Selección e inserción. Coste polinómico 0(n^2) para casi cualquier caso (sin mejoras) HeapSort y MergeSort, Coste en el peor caso polinómico, pero en promedio coste o(n·log(n)) Quicksort O(n·logn) y.... RadixSort Maravilla 0(n·l) donde n es el número de elmentos a ordenar y l la longitud máxima de símbolos que tienen los elementos (o sea, la cantidad de cifras) A éstas horas de la noche no tengo ganas de explicar más, pero buscad buscad.... os lo recuerdo por si acaso "www.google.es" Mi preferido es el HeapSort

http://www.algoritmia.net/

Salu2

... en esta página puedes ver unas demos, y también tienes código en java:

http://www.hci.uniovi.es/martinDocencia/Asignatura s/ordenacion.htm [uniovi.es]

Saludos.

Hola, puedes ver todo tipo de algoritmos explicados en mis apuntes de clase: http://servil.unileon.es/asignaturas/MTP/apuntesMT P.pdf.bz2 . El código de ejemplo esta en pascal, pero las explicaciones son las mismas para todo. -- www.garpanta.com

Los mas rápidos O(N): RadixSort (Sólo ordena números) BinSort (Requiere conocer los valores a priori) Los más rápidos para cualquier tipo de problema O(NlogN): QuickSort (El más rápido conocido) MergeSort (Dado N siempre tarda lo mismo independientemente del orden inicial) HeapSort Los más fáciles de programar O(N^2): Inserción Seleccion Burbuja PD: Existen más,pero estos son los que se usan. Y los algoritmos de orden O(n^2) no son de museo, pueden usarse si la eficiencia temporal no es crítica y no queremos complicarnos (para qué cortar el queso con un bisturí si nos sobra con un cuchillo...)

La definición clásica de los algorismos de busqueda y ordenación siempre se refieren a vectores, peró ya nadie usa vectores para guardar listas que deban ser ordenadas.

Tenemos arboles binarios de busqueda:

- Se inserta un elemento con tiempo medio logN y N en el peor caso.

- Insertar N elementos ordenados tarda N*logN

- Sueles encontrarte con el peor caso.

- Se pueden listar todos los elementos ordenados con un coste N, como un vector.

Arboles casi-balanceados:

- Como el arbol binario, peró

- Siempre la insercion y quite de elementos es logN

tries:

- Suele gastar un montón de memoria, peró son ultrarápidos. Son independientes del numero de elementos.

tablas de hash:

- Sacrificas la posibilidad de lista ordenada, peró buscar y quitar elementos te lo deja en coste medio O(1)

Veis, teniendo estas alternativas, el uso de las técnicas de ordenación clásicas és méramente anecdótico.

La verdad es que no estoy muy puesto en el tema, pero supongo que la STL soportará de alguna manera u otra la ordenación y búsqueda en listas, vectores, mapas, etc. Yo investigaría este enfoque.

Yo hice mi proyecto final de carrera sobre algoritmos de búsqueda de un sólo patrón.

No se si te resultará interesante, pero por si acaso la memoria está en:

http://www.uv.es/~sto/pfc/mpfc.pdf [www.uv.es]

Y el código en C++ está en:

http://www.uv.es/~sto/pfc/adml-1.0b1.tar.gz [www.uv.es]

De todos modos hace años que no lo pruebo, así que igual ni compila.

Creo que el mejór método de ordenación y búsqueda en C++, para un 99% de los programadores, es olvidarse los algoritmos.

Es decir, usa la STL y no te preocupes por el algoritmo que usa: en cualquier caso será el mejor.

Por desgracia, ni la milésima parte de los que "usan" C++ saben usar la STL, ni saben hacer un programa en C++ ANSI, así que cada uno se hace su propia función de ordenación que peta por todas partes. Y luego dirá que el C++ es complicado, que si los punteros, que si gestión de memoria, etc...

Por favor: si estás pensando en reinventar un algoritmo de búsqueda y ordenación en C++, mejor usa Java o usa otra cosa, porque de C++ no sabes nada.

Hay un concurso de algoritmos de ordenacion http://www.research.microsoft.com/research/barc/So rtBenchmark/default.htm. Hay que reconocer que en I+D Microsoft siempre ha tenido cosas interesantes aunque luego no las use.

Me quedo un poco fuera de tema, pero si estás buscando lo "último" en programación en C, sería conveniente que echaras un vistazo a la GLib [gnome.org], que es la librería que lleva "por debajo" Gnome (y no me refiero a la librería gráfica, sino a la capa más baja).

La GLib, además de proporcionarte una serie de envoltorios que hacen que el manejo de memoria sea más sencillo, te permite llevar la orientación a objetos (o algo muy parecido) a C. Y por cierto, también trata muy bien la ordenación, proporcionándote funciones que ordenan listas (utilizando a-saber-que algoritmo, de forma transparente) y a las que solo les has de pasar el método de comparación que quieres usar (al estilo de Perl o Python, vamos).

No sé si será interesante para lo que estás recopilando, pero lo cierto es que se merece por lo menos un vistazo.

Existe una biblioteca de manipulación de números reales con precisión arbitraria, llamada GMP [swox.com], que es parte del proyecto GNU

No, no, no...

Burbuja: O(N^2)
Quicksort: N*logN de media
Heapsort: O(N*logN), pero en la practica tiene unas constantes mas elevadas que quicksort, aunque asintoticamente sea mas rapido.

No me acuerdo del mergesort, pero era algo peor que quicksort. El limite teorico de un algoritmo de ordenacion es O(N*LogN), puesto que ese es el numero minimo de comparaciones que se han de hacer para asegurar la correctitud de la ordenacion. Hay variantes mas rapidas, pero se salen del modelo de maquina de Turing (computacion cuantica..., pero no se mucho de eso).

En el SDK de Java tienes varios ejemplos. El código está en java, pero no es difícil traducirlo al C.

El más rápido es el heapsort, tiene O(n log n)... acá les dejo un link de un libro en español que está muy bueno, tiene muchos métodos de ordenación y un montón de cosas más: http://exactas.org/modules.php?op=modload&name=Dow nloads&file=index&req=getit&lid=158 Salu2 JANUS

Si requieres hacer muchas búsquedas sobre unos datos, los árboles binarios son adecuados. Pero si sólo quieres ordenarlos o hacer una sola búsqueda, ya dejan de serlo.
Esto es porque antes de buscar en el árbol tienes que construirlo ;) y esto tiene coste O(n*log(n)).
El coste total seria el coste de construir el árbol y el de realizar la búsqueda:
    O(n*log(n) + log(n)), que equivale a O(n*log(n))

No conozco una librería así en C/C++, pero quizá te baste con utilizar el comando unix bc "bc - arbitrary-precision arithmetic language".

Ademas de las librerias citadas anteriormente, comentarte que no existe ningun misterio en el manejo de numeros-grandes con una computadora. Los algoritmos son los mismos que usarias tu si tuvieses que hacer el calculo con lapiz y papel. La unica diferencia estriba en la base utilizada que suele ser 2^64, 2^32, 2^16 o 2^8 dependiendo del tamaño de palabra de la maquina y de si lo implementas en C o en ensamblador.

En algunos casos tambien se usa base 100 o 10, cuando se necesita mantener unas condiciones de redondeo estrictas y especificadas en base 10, como por ejemplo en el caso de calculos financieros (la base 100 se toma porque es la que cabe en un byte). De hecho, algunos procesadores como los motorola 680x0 incluso tienen instruciones especificas para el manejo de numeros en base 10, usando cuatro bits por digito y almacenando 2 en cada byte.

Como ya han comentado más arriba, quicksort y mergesort tienen coste O(n*log(n)). De todos modos, el quicksort puede aumentar hasta O(n^2) en el caso peor, mientras que mergesort es siempre O(n*log(n)) (aunque en algunos casos puede ir más lento que quicksort). Podriamos decir que el coste de mergesort es más "estable".

En cuando a algoritmos más rapidos... existe uno llamado radix sort, de coste O(n), pero de aplicación bastante concreta. Una simple búsqueda en google [google.com] os dará más información. Programas como sort(1) utilizan radix sort para realizar su trabajo (al menos bajo NetBSD), disponiendo de una opción especial para usar merge sort (con archivos muy grandes).

Precisamente estoy haciendo un ejercicio de la uni q trata de eso...
Se almacenan los numeros en arrays de char y se pasan a listas enlazadas (asignacion dinamica de memoria) donde cada nodo contiene un int con un digito y un puntero al siguiente nodo
El limite? la memoria del pc..