This is an assingment i've been working on but since this is a merge between two previous developments i need a little help solving my issue here that would be highly appreciated.
In a nutshell what this program needs to do is recieve a .txt file create a vector holding all this values and apply them some sorting algorithms. Here's the code i wrote so far but as i said before what i think i need is a function to convert the vector values to an int array but i'm stuck there, so any help is appreciated.
Main.cpp
#include <iostream>
#include <string>
#include "TxtFileManager.h"
#include "Vector.h"
using namespace std;
void sort(Vector *v, int * temp, int izq, int der);
float merge(Vector *v, int *temp, int izq, int centro, int der);
void mergeSort(Vector *v, long n);
int main()
{
float rta = 0;
TxtFileManager t;
string f = "list[50000].txt";
cout << "Desafio 1 AED2: Cuenta de inversiones." << endl;
cout << endl << "Comienza carga del archivo en un arreglo en memoria..." << endl;
Vector *vec = t.readNumbers(f);
cout << endl << "Arreglo creado con " << vec->length() << " elementos" << endl;
cout << "Contenido: " << endl;
cout << vec->toString() << endl;
mergeSort(vec,vec->length());
}
void mergeSort(Vector *v, long n)
{
int *temp = new int[n];
sort(v, temp, 0, n - 1);
delete [] temp;
}
void sort(Vector *v, int * temp, int izq, int der)
{
if(izq < der)
{
int centro = (izq + der) / 2;
sort(v, temp, izq, centro);
sort(v, temp, centro + 1, der);
merge(v, temp, izq, centro, der);
}
}
float merge(Vector *v, int *temp, int izq, int centro, int der)
{
float ci = 0;
for(int i = izq; i <= der; i++) temp[i] = v[i]; //error
int i = izq, j = centro + 1, k = izq;
while(i <= centro && j <= der)
{
if(temp[i] <= temp[j])
{
v[k] = temp[i];
i++;
}
else
{
v[k] = temp[j];
j++;
ci = centro - i +1;
}
k++;
}
while(i <= centro)
{
v[k] = temp[i];
k++;
i++;
}
return ci;
}
Also i've attached the entire nbeans proyect if anyone is willing to try it.
Thanks in advance and sorry for my english (second language).
Vector.cpp
#include "Vector.h"
//***********************Métodos públicos
Vector::Vector()
{
init(10);
}
Vector::Vector(int tam)
{
init(tam);
}
Vector::~Vector()
{
delete []v;
}
/**
* Retorna la capacidad total del arreglo (o sea, su tamaño físico). Es el valor
* con el cual se indicó el tamaño del vector al crearlo con new.
* @return la capacidad total del arreglo.
*/
int Vector::capacity()
{
return t;
}
/**
* Retorna la cantidad de casillas en uso del arreglo (o sea, su tamaño lógico o
* nivel de utilización. Este valor indica, además, el índice de la primera
* casilla libre el vector, comenzando desde la izquierda.
* @return la cantidad real de casillas usadas.
*/
int Vector::length()
{
return n;
}
/**
* Equivale a append(x). Se incluye por razones de comodidad: algunos
* programadores prefieren llamar add() al método que agregar un elemento al
* final de una estructura.
* @param x el valor a agregar.
* @return true si el agregado pudo hacerse.
* @see append(x).
*/
bool Vector::add(int x)
{
return append(x);
}
/**
* Agrega el valor x al final del vector (o sea, en la primera casilla libre
* comenzando desde la izquierda. Retorna true si la operación tuvo exíto, o
* false si el arreglo no tenía ya lugar libre.
* @param x el valor a agregar.
* @return true si el agregado pudo hacerse.
*/
bool Vector::append(int x)
{
// si no hay espacio disponible, retornar false...
if(n >= t) return false;
// ... si hay espacio, agregar x en la casilla n...
v[n] = x;
// correr n a la casilla siguiente, y salir con true...
n++;
return true;
}
/**
* Recupera el valor en la casilla i, sin eliminarlo del vector. Si i no es
* un índice válido, el método provoca la interrupción del programa.
* @param i el índice de la casilla a acceder.
* @return el valor en la casilla i del vector.
*/
int Vector::get(int i)
{
// controlar validez del índice...
if(i < 0 || i >= n)
{
// si el índice se fué de rango, abortar el programa...
cout << "Indice fuera de rango: get(" << i << ")" << endl;
system("pause");
exit(1);
}
// si el índice es correcto, retornar el valor pedido...
return v[i];
}
/**
* Almacena el valor x en la casilla i. El valor anteriormente guardado en
* la casilla i, es reemplazado por x. Si la operación pudo realizarse, el
* método retorna true. Si no pudo realizarse (por índice fuera de rango),
* retorna false. Note que si i es igual a la cantidad de elementos realmente
* usados, entonces el valor x se agrega al final (en caso de haber espacio).
* @param i el índice de la casilla donde x será almacenado.
* @param x el valor a almacenar.
* @return true si x pudo almacenarse con éxito.
*/
bool Vector::set(int i, int x)
{
// controlar validez del índice... y salir con false si hay algo mal...
if(i < 0 || i > n || (i == n && n >= t)) return false;
// si todo anduvo bien, asignar x en la casilla i, y salir con true.
// notar que (i == n && n < t) es válido (inserta en la primera libre)...
v[i] = x;
return true;
}
/**
* Busca el valor x en el vector, con el algoritmo de búsqueda secuencial. Si lo
* encuentra, retorna el índice de su posición. Si no lo encuentra, retorna -1.
* @param x el valor a buscar.
* @return el índice de la casiila que contiene a x, o -1 si x no se encuentra.
*/
int Vector::linear_search(int x)
{
for(int i = 0; i < n; i++)
{
if(x == v[i]) return i;
}
return -1;
}
/**
* Busca el valor x en el vector, con el algoritmo de búsqueda binaria. Si lo
* encuentra, retorna el índice de su posición. Si no lo encuentra, retorna -1.
* El algoritmo asume que el vector está ordenado de menor a mayor: si esta
* consigna no se cumple, el algoritmo no funcionará correctamente.
* @param x el valor a buscar.
* @return el índice de la casiila que contiene a x, o -1 si x no se encuentra.
*/
int Vector::binary_search(int x)
{
int izq = 0, der = n - 1;
while(izq <= der)
{
int c = (izq + der) / 2;
if(x == v[c]) return c;
if(x < v[c]) der = c - 1;
else izq = c + 1;
}
return -1;
}
/**
* Ordena el vector, aplicando el algoritmo de Selección Directa.
*/
void Vector::selection_sort()
{
for(int i = 0; i < n - 1; i++)
{
for(int j = i + 1; j < n; j++)
{
if(v[i] > v[j])
{
int aux = v[i];
v[i] = v[j];
v[j] = aux;
}
}
}
}
/**
* Ordena el vector, aplicando el algoritmo Quick Sort.
*/
void Vector::quick_sort()
{
sort(0, n-1);
}
/**
* Determina y retorna la cantidad de inversiones que tiene el vector,
* suponiendo un orden natural de menor a mayor.
* @return la canatidad de inversiones que tiene el vector...
*/
int Vector::inversions_count()
{
int ci = 0;
// TO DO... este es trabajo de los alumnos...
return ci;
}
/**
* Crea y retorna una cadena de caracteres, lista para visualizar en consola,
* con el contenido del vector.
* @return una cadena con los elementos del vector.
*/
string Vector::toString()
{
char cad[50];
string res("[");
for (int i=0; i<n; i++ )
{
sprintf(cad, "%d", v[i]);
res.append(cad);
if(i < n - 1) res.append(" ");
}
res.append("]");
return res;
}
//***********************Métodos privados
// auxiliar de los constructores...
void Vector::init(int tam)
{
// si el tamaño pedido no es válido, por default asumir 10...
t = tam;
if(t <= 0) t = 10;
// crear el vector... controlar desborde de memoria...
v = new (nothrow) int[t];
if(!v)
{
// si algo salió mal, cancelar el programa...
cout << "Error: falta memoria para crear el vector..." << endl;
system("pause");
exit(1);
}
// iniciar en cero cada una de las casillas...
for(int i = 0; i < t; i++)
v[i] = 0;
// índice de la primera casilla libre, comenzando desde la izquierda??
n = 0;
}
// parte recursiva del quicksort...
void Vector::sort(long izq, long der)
{
long i, j;
int x, y;
i = izq;
j = der;
x = v[( izq + der ) / 2 ];
do
{
while(v[i] < x && i < der) i++;
while (x < v[j] && j > izq) j--;
if (i <= j)
{
y = v[i];
v[i] = v[j];
v[j] = y;
i++;
j--;
}
}
while (i <= j);
if (izq < j) sort(izq, j);
if (i < der) sort(i, der);
}
TxtFileManager.cpp
#include "TxtFileManager.h"
TxtFileManager::TxtFileManager()
{
}
TxtFileManager::~TxtFileManager()
{
}
/**
* Crea un archivo de texto con numeros aleatorios posiblemente repetidos
* (valores entre 1 y n).
*
* @param n la cantidad de numeros a grabar en el archivo.
*/
void TxtFileManager::saveNumbers(int n, string f)
{
// convertir el nombre del archivo a una cadena estandar...
const char * name = f.c_str();
// controlar validez de n...
if(n <= 0) n = 100;
// crear el objeto que accede al archivo y abrir el archivo...
ofstream m(name);
// si el archivo no se abrió, abortar...
if(! m.is_open())
{
cout << "Error al abrir el archivo para grabar...";
system("pause");
exit(1);
}
// primera linea: la cantidad de numeros que tendra el archivo, mas un salto de linea...
char sn[50];
sprintf(sn, "%d", n);
m << sn << "\n";
// y luego, n lineas: una por cada numero, aleatorio en [1, n]...
srand(time(NULL));
for(int i = 1; i <= n; i++)
{
// un entero entero aleatorio entre 1 y n (incluidos ambos)...
int x = rand() % n + 1;
//grabar el numero como cadena, con salto de linea al final...
sprintf(sn, "%d", x);
m << sn << "\n";
}
// cerrar el archivo y terminar...
m.close();
}
/**
* Crea un Vector de numeros con el contenido del archivo f.
*
* param f el nombre del archivo desde el cual deben leerse los datos.
* return una Vector con todos los numeros que traia el archivo.
*/
Vector * TxtFileManager::readNumbers(string f)
{
// convertir el nombre del archivo a una cadena estandar...
const char * name = f.c_str();
// abrir el archivo de texto...
ifstream m(name);
// si el archivo no se abrió, o no se puede leer... abortar...
if(!m.is_open() || !m.good())
{
cout << "Error al abrir el archivo para leer...";
system("pause");
exit(1);
}
// la primera linea del archivo nos da el valor de n...
// ... leerla, y convertirla a int...
string xs;
getline(m, xs);
int n = atoi(xs.c_str());
// crear el Vector a retornar...
Vector *vec = new Vector(n);
// leer el resto del archivo...
while(m.good())
{
// leer y convertir a entero la siguiente linea...
getline(m, xs);
n = atoi(xs.c_str());
// agregar el entero al Vector en orden de llegada...
vec->append(n);
}
// cerrar el archivo y retornar el Vector...
m.close();
return vec;
}
