Ordenar valores en una secuencia: C++ Linux[SOLUCIONADO]

Temas sobre programación ( php, c, sql, html, perl, python, ruby, java, bash, etc ) y recursos ( herramientas, frameworks, hosting, cms, etc )

Moderadores: akodo, maiku

Avatar de Usuario
cerenkov
Forista Medio
Forista Medio
Mensajes: 402
Registrado: Jue Jun 17, 2010 5:23 am
Ubicación: Venezuela

Ordenar valores en una secuencia: C++ Linux[SOLUCIONADO]

Mensaje por cerenkov » Vie Ago 13, 2010 6:56 pm

Aquí expongo un programa sencillo para ordenar una secuencia desordenada de valores enteros (cambien el tipo si así lo desean). Grábenlo como ordenar.cpp y pónganlo, por ejemplo, en una carpeta llamada ORDENAR.

Código: Seleccionar todo

//Programa para ordenacion de datos

#include <iostream>
#include <fstream>
#include <cstdlib>

void ordenar (int n, int *a);

using namespace std;

int main() {

   system ("clear");

    ifstream label1 ("datos.in");

   int n, i, j;

   int *a;

   label1 >> n;  // numero de datos

   a = new int [n];

   for (i=0; i < n; i++){

      label1 >> a[i];

   }

   cout << "Serie desordenada de valores\n";

   for (i=0; i < n; i++){

      cout << a[i] << " ";

   }

   cout << "\n";

   ordenar(n,a); //funcion ordenar

   cout << "Serie ordenada de valores\n";

   for (i=0; i < n; i++){

      cout << a[i] << " ";

   }

   cout << "\n";

   return 0;

}

void ordenar (int n, int *a){

   int i, j, mayor;

   for (i=0; i < n-1; i++){

      for (j=0; j < n-1; j++){

         if(a[j] > a[j+1]){

            mayor = a[j];

            a[j] = a[j+1];

            a[j+1] = mayor;

         }

      }

   }

}


Graben el archivo datos.in, en el directorio ORDENAR, con lo siguiente:

Código: Seleccionar todo

7
4 5 1 8 2 7 0


Compilen y ejecuten, en el directorio ORDENAR, con:

Código: Seleccionar todo

g++ ordenar.cpp -o ordenar [Enter]
./ordenar [Enter]


La salida por pantalla será algo como esto:

Código: Seleccionar todo

Serie desordenada de valores
4 5 1 8 2 7 0
Serie ordenada de valores
0 1 2 4 5 7 8


Para una secuencia diferente modifiquen el archivo datos.in y si quieren introducir los datos por pantalla hagan las modificaciones a su gusto 8-).

Saludos
Última edición por cerenkov el Mié Ago 18, 2010 4:55 pm, editado 1 vez en total.
malicious-mind
Forista Nuevo
Forista Nuevo
Mensajes: 1
Registrado: Sab Ago 14, 2010 10:54 am

Re: Ordenar valores en una secuencia: C++ Linux

Mensaje por malicious-mind » Sab Ago 14, 2010 11:01 am

Muy bien...., Un For dentro de otro For, si tienes 1000 elementos, 1000 * 1000 = 1000000, muy eficiente si señor.....

Echale un vistazo a estos enlaces anda.....

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

http://en.wikipedia.org/wiki/Sorting_algorithm
Avatar de Usuario
cerenkov
Forista Medio
Forista Medio
Mensajes: 402
Registrado: Jue Jun 17, 2010 5:23 am
Ubicación: Venezuela

Re: Ordenar valores en una secuencia: C++ Linux

Mensaje por cerenkov » Sab Ago 14, 2010 4:21 pm

malicious-mind escribió:Muy bien...., Un For dentro de otro For, si tienes 1000 elementos, 1000 * 1000 = 1000000, muy eficiente si señor.....

Echale un vistazo a estos enlaces anda.....

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

http://en.wikipedia.org/wiki/Sorting_algorithm


Y cuál es el problema? Acaso lo necesito para ordenar dentro de una base de datos monstruosa. NO. Lo anterior es un problema de codificación que se resuelve pensando un par de minutos (ni siquiera usé referencias sino que apelé a la memoria) y lo enseñan de manera introductoria en cursos de programación. El hecho de que existan algoritmos de ordenación más eficientes eso lo sé pero no los necesito; por ahora. Cuando lo requiera lo busco y lo implemento. Cuando requerí un generador de números pseudoaleatorios "SERIO" lo busqué y lo encontré. Los que se implementan rutinariamente en ciertos lenguajes y que usan como semilla la hora del sistema no sirven para ciertos usos y eso también lo sé. Lo que si no sé es por qué alguién pasa por aquí y se inscribe deliberadamente en un foro para hacer un comentario ERUDITO a sabiendas de que a los que estudian de manera seria en una escuela de computación les van a hacer esa misma advertencia que tu me hicistes.

Existe otra cosa que se llama criterio. No voy a pasar días enteros devanándome los sesos para implementar un algoritmo eficiente para ordenar sólo 12 valores, que es para lo que realmente lo necesito, cuando, como ya te dije, lo puedo codificar en un par de minutos. No obstante, te agradezco el material (lo acepto como una crítica muy constructiva). Está muy bueno 8-). Por otra parte, no hay error en mi implementación. Lamentablemente, el ineficiente método de la burbuja se hace con un doble for.

Saludos
Avatar de Usuario
akodo
Moderador
Moderador
Mensajes: 1457
Registrado: Mié Nov 28, 2007 8:00 am
Ubicación: En la X del explorer (pulse para llamar)

Re: Ordenar valores en una secuencia: C++ Linux

Mensaje por akodo » Sab Ago 14, 2010 4:31 pm

Pues no sé que decir. El comentario de malicious-mind tiene un punto de razón (aunque no sea la mejor forma de expresarlo). Creo que para ordenar 12 valores lo puedes hacer a mano sin perder demasiado tiempo. En el momento en que tengas que ordenar más de 50 sí que puede merecer la pena.
Por otro lado, tener que poner el número de elementos a mano en el fichero.... creo que es mejor poner algún tipo de separador que indique que la lista se ha acabado, aunque es cierto que resulta más cómodo para el programador al poder poner un array de tamaño fijo.

Un saludo
Descargue el gestor de mp3 "Music Manager" -> ([url=http://ctrlalt.iespana.es]mmlf[/url])
Última versión del gestor "Music Manager" -> ([url=http://sourceforge.net/projects/jmusicmanager/]jmmm[/url])
Avatar de Usuario
cerenkov
Forista Medio
Forista Medio
Mensajes: 402
Registrado: Jue Jun 17, 2010 5:23 am
Ubicación: Venezuela

Re: Ordenar valores en una secuencia: C++ Linux

Mensaje por cerenkov » Lun Ago 16, 2010 4:13 am

akodo escribió:Pues no sé que decir. El comentario de malicious-mind tiene un punto de razón (aunque no sea la mejor forma de expresarlo). Creo que para ordenar 12 valores lo puedes hacer a mano sin perder demasiado tiempo. En el momento en que tengas que ordenar más de 50 sí que puede merecer la pena.
Por otro lado, tener que poner el número de elementos a mano en el fichero.... creo que es mejor poner algún tipo de separador que indique que la lista se ha acabado, aunque es cierto que resulta más cómodo para el programador al poder poner un array de tamaño fijo.

Un saludo


Gracias por el comentario. El algoritmo lo requiero para esta implementación:

Multiplicación de una matriz NxN, por si misma, n veces

y precisamente no quiero hacerlo a mano porque quiero automatizarlo todo (una vez que lo implementé lo puse como un post). Lo que pasa es que algunos aquí piensan que todos los que programan tienen que lidiar con bases de datos voluminosas como las de este foro. Hay casos donde uno puede permitirse el lujo de usar algoritmos ineficientes si la sencillez así lo amerita (ni referencias usé). Con relación a lo que tu me señalas del separador también lo sé. Lo que pasa es que no recuerdo la sintaxis para eof y para no perder tiempo (tengo un programa donde si era imprescindible implementarlo pero por flojera no lo busco ::lol:: ) lo hago de esa manera por comodidad; tal como tu señalas. La razón de estos posts que yo desarrollo es poner código funcional que sirva para propósitos bien definidos. Cada quien es libre de modificarlo como se le antoje una vez que aprenda a hacerlo. Lo ideal sería que aquí mismo se publicasen esas "mejoras" pero casi nadie lo hace (al final termino haciéndolo yo cuando tengo tiempo). Fíjate que cuando tu hicistes las críticas sobre la comprobación de la independencia lineal en otro hilo yo las acepté y las implementé. Hay muchas otras cosas que no implemento, como el manejo de excepciones, pero es deliberado porque sino se alargaría demasiado el código. Por otra parte, yo no soy programador profesional sino aficionado. Me aventuro a publicar estos post para recibir retroalimentación positiva y corregir vicios. Lo que si te puedo decir es que mis programas más complejos (que por ser tan específicos tal vez nunca publique aquí) funcionan bien porque los depuro con cuidado.

Un saludo

Editado -- Sab Ago 14, 2010 5:30 pm --

akodo escribió:...Por otro lado, tener que poner el número de elementos a mano en el fichero.... creo que es mejor poner algún tipo de separador que indique que la lista se ha acabado, aunque es cierto que resulta más cómodo para el programador al poder poner un array de tamaño fijo.

Un saludo


Aquí está una opción que ya no requiere incluir el número de datos en el fichero:

ordenar2.cpp

Sin embargo, se requiere un contador en el while para dar cuenta del arreglo y ya no se puede contar con memoria dinámica (aunque para los alcances del programa es irrelevante).

Saludos

Editado -- Sab Ago 14, 2010 6:58 pm --

Bueno, aquí está la implementación del ordenamiento pero usando el método de inserción que se encuentra aquí.

Este es el código:

insercion.cpp

Para este ejemplo (datos.in), si esperan alguna diferencia medible con time pierden su tiempo. Tampoco existe mucha diferencia para un archivo de 450 valores (son números aleatorios) que encontré por allí. Lo dejo como adjunto. Si quieren probar el programa insercion.cpp con este archivo recuerden modificar int a[20] a int a[450]. En el primero, como usa memoria dinámica no hace falta pero hay que añadir al principio del archivo datos.in que bajaron el valor de 450.
Adjuntos
datos.in.zip
(1.22 KiB) Descargado 65 veces
hades2k5
Forista Nuevo
Forista Nuevo
Mensajes: 5
Registrado: Mar Ago 17, 2010 7:05 am

Re: Ordenar valores en una secuencia: C++ Linux

Mensaje por hades2k5 » Mar Ago 17, 2010 7:15 am

Hola.

Es mas fácil usando la STL (standard template library) el algoritmo implementado para ordenar el quick sort que es uno de los más rápidos y eficientes que existe. El programa, omitiendo la carga de datos desde el archivo, quedaría así:

// ordenamiento de enteros
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

// funcion para comparar 2 objetos. Cambie el tipo para sus necesidades
bool funcComparador (int i,int j) { return (i<j); }

// functor para comparar 2 objetos. Cambie el tipo para sus necesidades
struct functor {
bool operator() (int i,int j) { return (i<j);}
} unObjeto;

int main () {
int enteros[] = {32,71,12,45,26,80,53,33};
vector<int> unVector (enteros, enteros+8); // 32 71 12 45 26 80 53 33
vector<int>::iterator it;

// ordena los primeros 4 elementos usando comparacion por defecto (operador <):
sort (unVector.begin(), unVector.begin()+4); //(12 32 45 71)26 80 53 33

// ordena despues del cuarto elemento usando funcComparador para comparar
sort (unVector.begin()+4, unVector.end(), funcComparador); // 12 32 45 71(26 33 53 80)

// ordena todos los elementos usando un objeto para comparar
sort (unVector.begin(), unVector.end(), unObjeto); //(12 26 32 33 45 53 71 80)

// imprime el contenido:
cout << "unVector contiene:";
for (it=unVector.begin(); it!=unVector.end(); ++it)
cout << " " << *it;

cout << endl;

return 0;
}
Avatar de Usuario
cerenkov
Forista Medio
Forista Medio
Mensajes: 402
Registrado: Jue Jun 17, 2010 5:23 am
Ubicación: Venezuela

Re: Ordenar valores en una secuencia: C++ Linux

Mensaje por cerenkov » Mar Ago 17, 2010 4:06 pm

hades2k5 escribió:Hola.

Es mas fácil usando la STL (standard template library) el algoritmo implementado para ordenar el quick sort que es uno de los más rápidos y eficientes que existe...


Sería más fácil si dijeras cuál fue la referencia que TU usastes para usar la STL. Comó vas a decir que es más fácil si estás trabajando bajo un esquema de caja transparente. Así expresado no es entendible en su totalidad porque no sabes como funciona completamente. Por otra parte, si te lees la referencia de malicious-mind (allí si dice como funciona), se refleja claramente que el algoritmo es inestable y cuando se resiente su eficiencia es igual a la del método de la burbuja. Cómo vas a decir que es más fácil si con sólo copiar y pegar de la referencia de malicious-mind puedo implentar los métodos (ya llevo tres) sin ni siquiera saber que existe la STL (el QuickSort ni me molesto en verlo, ni alguno de los inestables, por tal referencia).

Un saludo :D.
hades2k5
Forista Nuevo
Forista Nuevo
Mensajes: 5
Registrado: Mar Ago 17, 2010 7:05 am

Re: Ordenar valores en una secuencia: C++ Linux

Mensaje por hades2k5 » Mar Ago 17, 2010 6:01 pm

cerenkov escribió:
hades2k5 escribió:Hola.

Es mas fácil usando la STL (standard template library) el algoritmo implementado para ordenar el quick sort que es uno de los más rápidos y eficientes que existe...


Sería más fácil si dijeras cuál fue la referencia que TU usastes para usar la STL. Comó vas a decir que es más fácil si estás trabajando bajo un esquema de caja transparente. Así expresado no es entendible en su totalidad porque no sabes como funciona completamente. Por otra parte, si te lees la referencia de malicious-mind (allí si dice como funciona), se refleja claramente que el algoritmo es inestable y cuando se resiente su eficiencia es igual a la del método de la burbuja. Cómo vas a decir que es más fácil si con sólo copiar y pegar de la referencia de malicious-mind puedo implentar los métodos (ya llevo tres) sin ni siquiera saber que existe la STL (el QuickSort ni me molesto en verlo, ni alguno de los inestables, por tal referencia).

Un saludo :D.


Pensé que la idea era dar soluciones y no entrar en polémica.

La STL se creó para simplificar tareas comunes de programación como son, entre otras, manejo de listas y algoritmos de recorrido de éstas. Simplente quería indicar que no es necesario hacer la implementación del algoritmo de ordenamiento ya que tanto C como C++ tienen implementado el quicksort en las bibliotecas estándar que vienen con el lenguaje. En C se usa un puntero a una función de comparación. Como tu artículo es sobre C++ me pareció bueno mostrar una forma de hacer lo mismo usando elementos existentes dentro del lenguaje.

No se a qué te refieres con la referencia. Si es algo bibliográfico, en la web hay mucha información sobre la STL. Si te refieres a que el programa no es claro trataré de explicarlo con una versión mas simple del programa que publiqué:

Código: Seleccionar todo

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

// funcion para comparar 2 enteros. Se puede cambiar para comparar cualquier objeto.
// La idea es que siempre retorne si "i" es menor que "j"
bool funcComparador (int i,int j) {
  return (i<j);
}

int main () {

// El arreglo de enteros. Si se leyó desde el archivo, como en el programa de
// ejemplo inicial, aquí deben quedar los datos
int enteros[] = {32,71,12,45,26,80,53,33};

// Se crea un objeto de tipo vector, definido en: "include <vector>", como un vector de enteros
// vector es una clase que sobrecarga el operador "[]" de manera que se pude usar como un array.
vector<int> unVector (enteros, enteros+8); // 32 71 12 45 26 80 53 33

// ordena todos los elementos usando un objeto para comparar
// la funcion sort esta definida en "include <algorithm>". begin() y end()
// devuelven un iterador que apunta al inicio y al fin del vector
// la invocación de la función se leería como: ordene el vector unVector entre el inicio y el fin
// usando para comparar la funcion funcComparador
sort (unVector.begin(), unVector.end(), funcComparador); //(12 26 32 33 45 53 71 80)

// imprime el contenido:
cout << "unVector contiene:";
for (int i=0; i < unVector.size(); i++) {
// note la sobrecarga del operador "[]"
    cout << " " << unVector[i];
}

cout << endl;

return 0;
}


La referencia de la STL se puede leer en http://www.sgi.com/tech/stl/
La api de la clase vector está en: http://www.sgi.com/tech/stl/Vector.html
Última edición por hades2k5 el Mié Ago 18, 2010 5:57 am, editado 1 vez en total.
Avatar de Usuario
cerenkov
Forista Medio
Forista Medio
Mensajes: 402
Registrado: Jue Jun 17, 2010 5:23 am
Ubicación: Venezuela

Re: Ordenar valores en una secuencia: C++ Linux

Mensaje por cerenkov » Mar Ago 17, 2010 7:53 pm

hades2k5 escribió:...Pensé que la idea era dar soluciones y no entrar en polémica.

La STL se creó para simplificar tareas comunes de programación como son, entre otras, manejo de listas y algoritmos de recorrido de éstas. Simplente quería indicar que no es necesario hacer la implementación del algoritmo de ordenamiento ya que tanto C como C++ tienen implementado el quicksort en las bibliotecas estándar que vienen con el lenguaje. En C se usa un puntero a una función de comparación. Como tu artículo es sobre C++ me pareció bueno mostrar una forma de hacer lo mismo usando elementos existentes dentro del lenguaje.

No se a qué te refieres con la referencia. Si es algo bibliográfico, en la web hay mucha información sobre la STL. Si te refieres a que el programa no es claro trataré de explicarlo con una versión mas simple del programa que publiqué:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

// funcion para comparar 2 enteros. Se puede cambiar para comparar cualquier objeto. La idea es que siempre retorne si "i" es menor que "j"
bool funcComparador (int i,int j) {
return (i<j);
}

int main () {

// El arreglo de enteros. Si se leyó desde el archivo, como en el programa de ejemplo inicial aquí deben quedar los datos
int enteros[] = {32,71,12,45,26,80,53,33};

// Se crea un objeto de tipo vector, definido en: "include <vector>", como un vector de enteros
// vector es una clase que sobrecarga el operador "[]" de manera que se pude usar como un array.
vector<int> unVector (enteros, enteros+8); // 32 71 12 45 26 80 53 33

// ordena todos los elementos usando un objeto para comparar
// la funcion sort esta definida en "include <algorithm>". begin() y end() devuelven un iterador que apunta al inicio y al fin del vector
// la invocación de la función se leería como: ordene el vector unVector entre el inicio y el fin
// usando para comparar la funcion funcComparador
sort (unVector.begin(), unVector.end(), funcComparador); //(12 26 32 33 45 53 71 80)

// imprime el contenido:
cout << "unVector contiene:";
for (int i=0; i < unVector.size(); i++) {
// note la sobrecarga del operador "[]"
cout << " " << unVector[i];
}

cout << endl;

return 0;
}


La referencia de la STL se puede leer en http://www.sgi.com/tech/stl/
La api de la clase vector está en: http://www.sgi.com/tech/stl/Vector.html


No amigo, no era para entrar en polémica. Me disculpo (porque haz hecho un segundo comentario) y le doy la bienvenida a tu aporte. Lo voy a aprovechar también con tu permiso. Lo que pasa es que la palabra no era "facil" sino "conciso"; lo cual si acepto. Por otra parte, al ver otro "posteador de un sólo comentario" creía que era otra vez el malicious-mind tratando de "lucirse" cuando, como tu bien haz dicho, la cuestión es hacer aportes; sobre todo por el bien de los que están empezando.

Saludos y nuevamente ruego me disculpes :D.
Avatar de Usuario
akodo
Moderador
Moderador
Mensajes: 1457
Registrado: Mié Nov 28, 2007 8:00 am
Ubicación: En la X del explorer (pulse para llamar)

Re: Ordenar valores en una secuencia: C++ Linux

Mensaje por akodo » Mar Ago 17, 2010 11:16 pm

El algoritmo quicksort es cierto que es el más rápido, pero como bien apunta cerenkov está más orientado a vectores aleatorios porque el algoritmo se resiente si el vector está ordenado o parcialmente ordenado.
Lo que tengo entendido que se suele hacer es desordenar el vector (generalmente con un método shuffle) para luego reordenarlo con este algoritmo.

Dejo el artículo de la wikipedia que nunca está de más:
http://es.wikipedia.org/wiki/Algoritmo_de_ordenamiento

El ordenamiento por montículos también debe estar bastante bien, aunque debe ser un poco complicado de montar. Sólo falta que te aburras mucho y te dé por comparar y hacer unos test :)
Descargue el gestor de mp3 "Music Manager" -> ([url=http://ctrlalt.iespana.es]mmlf[/url])
Última versión del gestor "Music Manager" -> ([url=http://sourceforge.net/projects/jmusicmanager/]jmmm[/url])
Avatar de Usuario
cerenkov
Forista Medio
Forista Medio
Mensajes: 402
Registrado: Jue Jun 17, 2010 5:23 am
Ubicación: Venezuela

Re: Ordenar valores en una secuencia: C++ Linux

Mensaje por cerenkov » Mié Ago 18, 2010 4:42 am

Estuve analizando el código de hades2k5, el cual modifiqué ligeramente (básicamente para hacerlo más legible porque no usó el BBCODE del foro y probablemente se desconfiguró la identación) y lo coloqué en pastebin aquí:

quick sort de hades2k5

y ahora concuerdo también con él en que no sólo es conciso sino más FÁCIL y funciona sin problemas. Además, aplica la estrategia de "divide y vencerás" y luego entrelaza los arrays usando un objeto como referencia. Es un excelente aporte. Disculpa nuevamente.

Por otra parte, sin usar el objeto para comparar también funciona a la perfección y es aún mucho más conciso. Aquí está el código:

quicksort2.cpp

Además, el código es totalmente portable a Win y puede ser compilado y ejecutado allí sin ninguna modificación.

Saludos
hades2k5
Forista Nuevo
Forista Nuevo
Mensajes: 5
Registrado: Mar Ago 17, 2010 7:05 am

Re: Ordenar valores en una secuencia: C++ Linux

Mensaje por hades2k5 » Mié Ago 18, 2010 5:38 am

Estuve leyendo un poco mas sobre los "algoritmos" de la STL y es posible reemplazar los ciclos for que imprimen el contenido del vector por algo como:

Código: Seleccionar todo

copy (v.begin(), v.end(), ostream_iterator<int> (cout, " "));


es decir, el fragmento

Código: Seleccionar todo

for (it=unVector1.begin(); it!=unVector1.end(); ++it)
                cout << " " << *it;


quedaría así:

Código: Seleccionar todo

copy (unVector1.begin(), unVector1.end(), ostream_iterator<int> (cout, " "));


La referencia es: http://www.sgi.com/tech/stl/copy.html

Ahh, es necesario agregar "#include <iterator>" a las cabeceras
Avatar de Usuario
cerenkov
Forista Medio
Forista Medio
Mensajes: 402
Registrado: Jue Jun 17, 2010 5:23 am
Ubicación: Venezuela

Re: Ordenar valores en una secuencia: C++ Linux

Mensaje por cerenkov » Mié Ago 18, 2010 6:24 am

hades2k5 escribió:...Ahh, es necesario agregar "#include <iterator>" a las cabeceras


y quitar la instrucción:

Código: Seleccionar todo

vector<int>::iterator i;


que ya no haría falta. Funciona perfecto!
hades2k5
Forista Nuevo
Forista Nuevo
Mensajes: 5
Registrado: Mar Ago 17, 2010 7:05 am

Re: Ordenar valores en una secuencia: C++ Linux

Mensaje por hades2k5 » Mié Ago 18, 2010 6:32 am

akodo escribió:El algoritmo quicksort es cierto que es el más rápido, pero como bien apunta cerenkov está más orientado a vectores aleatorios porque el algoritmo se resiente si el vector está ordenado o parcialmente ordenado.
Lo que tengo entendido que se suele hacer es desordenar el vector (generalmente con un método shuffle) para luego reordenarlo con este algoritmo.

Dejo el artículo de la wikipedia que nunca está de más:
http://es.wikipedia.org/wiki/Algoritmo_de_ordenamiento

El ordenamiento por montículos también debe estar bastante bien, aunque debe ser un poco complicado de montar. Sólo falta que te aburras mucho y te dé por comparar y hacer unos test :)


Estuve revisando en http://www.sgi.com/tech/stl/sort.html y en la nota #2 dice algo sobre el algoritmo que se utiliza para la función sort:
...The current implementation of sort, however, uses the introsort algorithm (D. R. Musser, "Introspective Sorting and Selection Algorithms", Software Practice and Experience 27(8):983, 1997.) whose worst case complexity is O(N log(N)). Introsort is very similar to median-of-three quicksort, and is at least as fast as quicksort on average.


Y efectivamente el algoritmo introsort es un quicksort que en el temible "peor caso" cambia a un heapsort.
http://en.wikipedia.org/wiki/Introsort
Avatar de Usuario
cerenkov
Forista Medio
Forista Medio
Mensajes: 402
Registrado: Jue Jun 17, 2010 5:23 am
Ubicación: Venezuela

Re: Ordenar valores en una secuencia: C++ Linux

Mensaje por cerenkov » Mié Ago 18, 2010 7:10 am

Creo que voy a tener que empezar por aquí:

http://www.sgi.com/tech/stl/table_of_contents.html
Responder
  • Similar Topics
    Respuestas
    Vistas
    Último mensaje