//////////////////////////////////////////////////////////////////////////////
// Administración de una Lista de Alumnos
// ======================================
// Ejemplo de uso de 2 algoritmos de búsqueda y 2 de ordenamiento, incluyendo QuickSort
//
//////////////////////////////////////////////////////////////////////////////
using System;
namespace OrdyBusqueda1
{
class Alumno
{
string nombre;
float nota;
public Alumno(string v1, float v2) { nombre = v1; nota = v2; }
public float Nota { get { return (nota); } }
public string Nombre { get { return (nombre); } }
// Se reemplaza el método ToString para luego usar directamente el objecto Alumno en un WriteLine.
public override string ToString()
{
return (nombre + ": " + nota.ToString());
}
}
class ListaAlumnos
{
Alumno[] lista;
public ListaAlumnos(int cantidad)
{
// Listas de nombres y aplellidos para armar los nombres aleatoriamente
string[] nombres = { "Juan", "Pedro", "Jorge", "Oscar", "Manuel", "Humberto", "Cecilia", "Andrea", "Alejandra", "Paula" };
string[] apellidos = { "Pérez", "Soto", "González", "Ahumada", "Muñoz", "Cáceres", "Araneda" };
Random rn = new Random(DateTime.Now.Millisecond);
lista = new Alumno[cantidad]; // Se dimensiona de acuerdo a la cantidad indicada
for (int i = 0; i < cantidad; i++)
{
// Se crea un nuevo alumno generándole un nombre completo aleatorio y una nota también aleatoria
string nomcompleto = nombres[rn.Next(0, nombres.Length)] + " " + apellidos[rn.Next(0, apellidos.Length)];
lista[i] = new Alumno(nomcompleto, (float)rn.Next(10, 71) / 10);
}
}
//////////////////////////////////////////////////////////////////////////////////
// ALGORITMO: Ordenamiento Recursivo por Selección (ordenado por nota)
public void OrdenarRecursivo(int cantidad)
{
if (cantidad <= 1) return;
int mayor = 0;
// Busca el mayor de todos
for (int i = 1; i < cantidad; i++)
if (lista[i].Nota > lista[mayor].Nota)
mayor = i;
if (mayor < cantidad - 1)
{
Alumno aux = lista[cantidad - 1];
lista[cantidad - 1] = lista[mayor];
lista[mayor] = aux;
}
OrdenarRecursivo(cantidad - 1);
}
//////////////////////////////////////////////////////////////////////////////////
// ALGORITMO: Ordenamiento Recursivo QuickSort, que utiliza método auxiliar: Particionar()
int Particionar(int desde, int hasta)
{
int izq = desde-1; // Se comienza de uno menos, para asegurar el do-while()
int der = hasta+1; // Idem
Alumno pivote = lista[(desde + hasta) / 2];
Console.WriteLine("Particionando: {0} {1}", desde, hasta);
while (izq < der)
{
do izq++; while (pivote.Nota > lista[izq].Nota);
do der--; while (pivote.Nota < lista[der].Nota);
if (izq < der)
{
Alumno aux = lista[der];
lista[der] = lista[izq];
lista[izq] = aux;
}
Console.WriteLine(".{0}/{1}.{2} y {3},{4}", izq, der, pivote.Nota, lista[izq].Nota, lista[der].Nota);
}
Console.WriteLine(".");
return (der);
}
void QuickSort(int desde, int hasta)
{
if (desde < hasta)
{
int p = Particionar(desde, hasta);
QuickSort(desde, p);
QuickSort(p + 1, hasta);
}
}
//////////////////////////////////////////////////////////////////////////////////
// ALGORITMO: Búsqueda Lineal Recursiva
int BuscarRec(string nombre, int cantidad)
{
if (cantidad == 0) return (-1);
if (lista[cantidad - 1].Nombre == nombre) return (cantidad - 1);
else return (BuscarRec(nombre, cantidad - 1));
}
//////////////////////////////////////////////////////////////////////////////////
// ALGORITMO: Búsqueda Binaria Recursiva - asume que la lista está ordenada alfabéticamente
int BuscarBin(string nombre, int desde, int hasta)
{
if (desde > hasta) return (-1);
int pm = (desde + hasta) / 2;
if (lista[pm].Nombre == nombre) return (pm);
if (lista[pm].Nombre.CompareTo(nombre) < 0) return (BuscarBin(nombre, pm + 1, hasta));
else return (BuscarBin(nombre, desde, pm - 1));
}
//////////////////////////////////////////////////////////////////////////////////
// ALGORITMO: Búsqueda Binaria Recursiva - asume que la lista está ordenada por nota
int BuscarBin(float nota, int desde, int hasta)
{
if (desde > hasta) return (-1);
int pm = (desde + hasta) / 2;
if (lista[pm].Nota == nota) return (pm);
if (lista[pm].Nota < nota) return (BuscarBin(nota, pm + 1, hasta));
else return (BuscarBin(nota, desde, pm - 1));
}
// Métodos genéricos de Búsqueda y Ordenamiento: PUBLICOS
// En ellos se puede reemplazar por el algoritmo que se seleccione
public int Buscar(string nombre) { return (BuscarBin(nombre, 0, lista.Length - 1)); }
public int Buscar(float nota) { return (BuscarBin(nota, 0, lista.Length - 1)); }
public void Ordenar() { QuickSort(0, lista.Length - 1); }
public void Mostrar()
{
for (int i = 0; i < lista.Length; i++)
Console.WriteLine(lista[i]);
}
}
class MainApp
{
static void Main()
{
ListaAlumnos l = new ListaAlumnos(30);
l.Mostrar(); Console.WriteLine("--------------------");
l.Ordenar();
l.Mostrar();
// Se implementa búsqueda por nota, ya que la lista está ordenada por nota
Console.Write("Ingrese nota a buscar: ");
float nota = float.Parse(Console.ReadLine());
int pos = l.Buscar(nota);
if (pos >= 0) Console.WriteLine("LO ENCONTRE");
else Console.WriteLine("NO");
Console.ReadLine();
}
}
}
