Ordenar enteros usando la Librería de Plantillas Estándar (STL)

Para una salida como ésta:

Serie desordenada de valores
214 129 42 97 205 607 317 407 573 800 800 1117
Serie ordenada de valores
42 97 129 205 214 317 407 573 607 800 800 1117
En la serie ordenada asigna un orden repitiendo valores si es necesario
1 2 3 4 5 6 7 8 9 10 10 11
Enlaza los ordenes de la serie ordenada a la serie desordenada
5 3 1 2 4 9 6 7 8 10 10 11 

cuya lógica deseo incorporar en el código al cual se refiere este artículo:

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

fue que desarrollé el siguiente programa:

//Programa para ordenacion de datos

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
#include <iterator>
#include <algorithm>

using namespace std;

int main() {

    system ("clear");

    ifstream label1 ("datos.in");

	int n, i, j, k;

	int *a, *b, *index1, *index2;

	label1 >> n;  // numero de datos

	a = new int [n]; b = new int [n]; index1 = new int [n]; index2 = new int [n];

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

		index1[i] = 0;

	}

	cout << "\n";

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

		label1 >> a[i];

		b[i] = a[i];

	}

	vector<int> unVector_no_orden (b, b+n); 
	vector<int> unVector_orden (a, a+n); 
	vector<int> unIndex1(index1, index1+n);
	vector<int> unIndex2(index2, index2+n);

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

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

	cout << "\n";

	sort (unVector_orden.begin(), unVector_orden.begin()+n);

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

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

	cout << "\n";

	k = 1;

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

		unIndex2[i] = k;

		if (unVector_orden[i] == unVector_orden[i + 1]) {k += 0;}

			else {k += 1;}

	}

	cout << "En la serie ordenada asigna un orden repitiendo valores si es necesario\n";

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

	cout << "\n";

	cout << "Enlaza los ordenes de la serie ordenada a la serie desordenada\n";

	// Funciona pero lo ideal seria que no recorriese nuevamente la lista sino que descartara
	// los ya verificados

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

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

			if(unVector_no_orden[j] == unVector_orden[i]) unIndex1[j] = unIndex2[i]; 

		}

	}

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

	cout << "\n";

	delete a, b, index1, index2;

	return 0;

}

empleando recursos de la Standard Template Library (STL). La incorporación de tales elementos fue posible gracias a la ayuda de hades2k5, forista de Espacio Linux.

El algoritmo de ordenamiento de enteros que emplea la STL es el introsort, es decir, un quicksort que en el temible “peor caso” cambia a un heapsort. Para mayores detalles pueden consultar:

http://www.sgi.com/tech/stl/sort.html

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

http://www.sgi.com/tech/stl/table_of_contents.html

El datos.in de este ejemplo es:

12
214 129 42 97 205 607 317 407 573 800 800 1117
Esta entrada fue publicada en Código C++ y etiquetada , . Guarda el enlace permanente.

Una respuesta a Ordenar enteros usando la Librería de Plantillas Estándar (STL)

  1. Pingback: Ordenar enteros usando el algoritmo de mezcla |

Responder

Por favor, inicia sesión con uno de estos métodos para publicar tu comentario:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s