Tarea #5 [solución]

Ordenamiento de vectores por selección

      Complete la implementación del método estático ordene() para que funcione de acuerdo a su especificación. Esta estrategia de ordenamiento se llama ordenamiento por selección, pues en cada iteración del ciclo interno se obtiene el índice del siguiente elemento menor, para intercambiarlo dejándolo en su posición final.

      Recuerde usar DrJava como platforma de desarrollo. También recuerde pulsar el botón [Test] para activar el programa usando pruebas tipo JUnit (es más complicado ejecutar el programa activando el botón "run"). Recuerde: agregue su algoritmo dentro del bloque marcado "{ *** RELLENE CON SU ALGORITMO *** }"... ¡No modifique ninguna otra parte del programa!

      Para esta tarea programada usted debe enviarme estos archivos:

1. TestOrdenados.java
2. CARNET.docx

      En el documento CARNET.docx deben describir su experiencia de aprendizaje para completar esta tarea. Explique qué hizo, cómo lo hizo y por qué lo hizo. En especial, es importante que incluya la traza de ejecución de su programa, para que muestre paso a paso cómo procesa el vector y cómo la va ordenando. Por ejemplo, para el vector V[]=={7,6,5,4,3,2,1}; la traza de ejecución se vería más o menos así:

V[] 7 6 5 4 3 2 1 V[] 1 6 5 4 3 2 7 i==0 V[] 1 2 5 4 3 6 7 i==1 V[] 1 2 3 4 5 6 7 i==2 V[] 1 2 3 4 5 6 7 i==3 V[] 1 2 3 4 5 6 7 i==4 V[] 1 2 3 4 5 6 7 i==5

      Una forma de obtener la traza de ejecución es modificar el programa para que la produzca. Para esto es necesario incluir instrucciones de impresión en el sitio apropiada; estas instrucciones deben ser removidas después de que usted ya obtuvo la el resultado deseado.

Consulta:

Profe: aquí está la tarea. ¿Me da puntos extra?

/// Ordenamiento de Burbuja
public static void ordene( int V[] ) {
    if ( V.equals(null) ) { // V[] no existe todavía
        return;
    }
    int temp;
    final int N = V.length;
    for ( int i=0; i<N; i++ ) {
        for( int j=0; j<N; j++ ) {
            if ( V[j] > V[i] ) { // desordenado
                temp = V[i];     // intercambia
                V[i] = V[j];
                V[j] = temp;
            }
        }
    }
}

Respuesta:

Es cierto que tu programa ordena, pero no usás el ordenamiento de selección. Por eso, con tu solución actual no vas a obtener más de 3/10 de nota.
Tu trabajo consiste en rellenar con tu implementación el bloque marcado: "** RELLENE CON SU ALGORITMO **".
El resto del programa no necesita ninguna modificación y es un error cambiarlo.
Te recomiendo implementar el método que está mencionado en el enunciado de la tarea programada.

      Entregue su tarea por correo electrónico, como lo hizo anteriormente.

/** @(#)TestOrdenados.java 2009 adolfo@di-mare.com Datos de prueba para {@code Ordenados}. @author Adolfo Di Mare <adolfo@di-mare.com> */ import junit.framework.*; /** Datos de prueba para la clase {@code Ordenados}. */ public class TestOrdenados extends TestCase { /** Retorna {@code true} si el vector {@code V[]} tiene valores ascendentes. * <ul><li> Un vector nulo nunca es ascendente.</li> * <li> Un vector vacío siempre es ascendente.</li></ul> */ public static boolean esAscendente( int V[] ) { if ( V.equals(null) ) { // V[] no existe todavía return false; } else if ( V.length <= 1 ) { return true; } int N = V.length-1; for ( int i=0; i<N; ++i ) { if ( V[i] > V[i+1] ) { return false; } } return true; } /** Retorna {@code true} si el vector {@code V[]} tiene valores descendentes. * <ul><li> Un vector nulo nunca es descendente.</li> * <li> Un vector vacío siempre es descendente.</li></ul> */ public static boolean esDescendente( int V[] ) { if ( V.equals(null) ) { // V[] no existe todavía return false; } else if ( V.length <= 1 ) { return true; } int N = V.length-1; for ( int i=0; i<N; ++i ) { if ( V[i] < V[i+1] ) { return false; } } return true; } /** Ordena ascendentemente los valores almacenados en el vector {@code V[]}. * <ul><li> Un vector nulo nunca queda ordenado.</li> * <li> Un vector vacío siempre está ordenado.</li></ul> */ public static void ordene( int V[] ) { if ( V.equals(null) ) { // V[] no existe todavía return; } int N = V.length; for ( int i=0; i < N-1; i++ ) { int iMenor = i; { /******************************\ * * * RELLENE CON SU ALGORITMO * * * \******************************/ } } } /** Graba el nombre {@code name} y el valor del vector {@code V[]}. */ public static void grabeVec( String name , int V[] ) { System.out.print("\n" + name + " "); for ( int i=0; i<V.length; ++i ) { System.out.print( " " + V[i] ); } } /** Invoca {@code ordene(V)} y retorna {@code true} cuando {@code V[]} queda ordenado. * Este método permite detectar un error común en las implementaciones * de los estudiantes, quienes en algunas ocasiones en lugar de ordenar el * vector, lo que hacen es reescribir todo el vector con un solo valor. Para * detectar esta anomalí, este método coteja el resultado producido por * {@code ordene(V)} con esa copia ordenada. */ public static boolean pruebe_ordene( int V[] ) { if ( V.equals(null) ) { // V[] no existe todavía return false; } int VEC_copia[]; if ( V.length < 0 ) { int VEC_000[] = {}; VEC_copia = VEC_000; } else { VEC_copia = new int[V.length]; } // copia todos los valores de V[] en VEC_copia[] for ( int i=0; i<V.length; ++i ) { VEC_copia[i] = V[i]; } // ordena VEC_copia[] usanda la burbuja de fuerza bruta for ( int i=1; i<VEC_copia.length; ++i ) { // V.length-1 veces for ( int j=0; j<VEC_copia.length-1; ++j ) { if ( VEC_copia[j] > VEC_copia[j+1] ) { int temp = VEC_copia[j]; // intercambia VEC_copia[j] = VEC_copia[j+1]; // desordenados VEC_copia[j+1] = temp; } } } // usa "ordene()" para ordenar V[] ordene(V); // compara lo que produjo "ordene()" con el vector ordenado for ( int i=0; i<V.length; ++i ) { if ( VEC_copia[i] != V[i] ) { return false; // encontró uno erróneo } } return true; // todos están en su sitio correcto } /** test -> {@code Ordenados.ordene()}. */ public void test_ordene() { { int V[]={0,1,1,1,1,1,0}; assertTrue( pruebe_ordene(V) ); } { int V[]={1,0,0,0,0,0,0}; assertTrue( pruebe_ordene(V) ); } { int V[]={1,0,0,0,0,0,1}; assertTrue( pruebe_ordene(V) ); } { int V[]={1,1,1,1,0,0,0}; assertTrue( pruebe_ordene(V) ); } { int V[]={1,1,1,1,1,1,0}; assertTrue( pruebe_ordene(V) ); } { int V[]={1,1,1,1,1,1,1}; assertTrue( pruebe_ordene(V) ); } { int V[]={1,1,1,1,2,2,2}; assertTrue( pruebe_ordene(V) ); } { int V[]={1,2,3,4,4,5,4}; assertTrue( pruebe_ordene(V) ); } { int V[]={1,2,3,4,4,5,6}; assertTrue( pruebe_ordene(V) ); } { int V[]={1,2,3,4,5,6,7}; assertTrue( pruebe_ordene(V) ); } { int V[]={1}; assertTrue( pruebe_ordene(V) ); } { int V[]={7,6,5,4,3,2,1}; assertTrue( pruebe_ordene(V) ); } { int V[]={}; assertTrue( pruebe_ordene(V) ); } } /** test -> {@code Ordenados.estaOrdenados()}. */ public void test_estaOrdenado() { { int V[]={1,2,3,4,5,6,7}; assertTrue( estaOrdenado( V ) ); } { int V[]={7,6,5,4,3,2,1}; assertTrue( estaOrdenado( V ) ); } { int V[]={1,2,3,4,4,5,6}; assertTrue( estaOrdenado( V ) ); } { int V[]={1,2,3,4,4,5,4}; assertFalse( estaOrdenado( V ) ); } { int V[]={1,1,1,1,1,1,1}; assertTrue( estaOrdenado( V ) ); } { int V[]={1,1,1,1,0,0,0}; assertTrue( estaOrdenado( V ) ); } { int V[]={1,1,1,1,2,2,2}; assertTrue( estaOrdenado( V ) ); } { int V[]={1,1,1,1,1,1,0}; assertTrue( estaOrdenado( V ) ); } { int V[]={0,1,1,1,1,1,0}; assertFalse( estaOrdenado( V ) ); } { int V[]={1,0,0,0,0,0,0}; assertTrue( estaOrdenado( V ) ); } { int V[]={1,0,0,0,0,0,1}; assertFalse( estaOrdenado( V ) ); } { int V[]={1}; assertTrue( estaOrdenado( V ) ); } { int V[]={}; assertTrue( estaOrdenado( V ) ); } } /** test -> {@code Ordenados.estaOrdenados()}. */ public void test_esAscendente() { { int V[]={1,2,3,4,5,6,7}; assertTrue( esAscendente( V ) ); } { int V[]={7,6,5,4,3,2,1}; assertTrue( esDescendente( V ) ); } { int V[]={1,2,3,4,4,5,6}; assertTrue( esAscendente( V ) ); } { int V[]={1,2,3,4,4,5,4}; assertFalse( esAscendente( V ) ); } { int V[]={1,2,3,4,4,5,4}; assertFalse( esDescendente( V ) ); } { int V[]={1,1,1,1,1,1,1}; assertTrue( esAscendente( V ) ); } { int V[]={1,1,1,1,1,1,1}; assertTrue( esDescendente( V ) ); } { int V[]={1,1,1,1,0,0,0}; assertTrue( esDescendente( V ) ); } { int V[]={1,1,1,1,2,2,2}; assertTrue( esAscendente( V ) ); } { int V[]={1,1,1,1,1,1,0}; assertTrue( esDescendente( V ) ); } { int V[]={0,1,1,1,1,1,0}; assertFalse( esAscendente( V ) ); } { int V[]={0,1,1,1,1,1,0}; assertFalse( esDescendente( V ) ); } { int V[]={1,0,0,0,0,0,0}; assertTrue( esDescendente( V ) ); } { int V[]={1,0,0,0,0,0,1}; assertFalse( esAscendente( V ) ); } { int V[]={1}; assertTrue( esAscendente( V ) ); } { int V[]={1}; assertTrue( esDescendente( V ) ); } { int V[]={}; assertTrue( esDescendente( V ) ); } } /** Retorna {@code true} si el vector {@code V[]} está ordenado. * <ul><li> El orden puede ser ascendente o descendente.</li> * <li> Un vector nulo nunca está ordenado.</li> * <li> Un vector vacío siempre está ordenado.</li></ul> */ public static boolean estaOrdenado( int V[] ) { return (estaOrdenado_v1(V) && estaOrdenado_v2(V) && estaOrdenado_v3(V)); /* Esta implementación prueba las 3 implementaciones que están a * a continuación. */ } /** Retorna {@code true} si el vector {@code V[]} está ordenado. * <ul><li> El orden puede ser ascendente o descendente.</li> * <li> Un vector nulo nunca está ordenado.</li> * <li> Un vector vacío siempre está ordenado.</li></ul> */ public static boolean estaOrdenado_v1( int V[] ) { return (esAscendente(V) || esDescendente(V)); } /** Retorna {@code true} si el vector {@code V[]} está ordenado. * <ul><li> El orden puede ser ascendente o descendente.</li> * <li> Un vector nulo nunca está ordenado.</li> * <li> Un vector vacío siempre está ordenado.</li></ul> */ public static boolean estaOrdenado_v2( int V[] ) { if ( V.equals(null) ) { // V[] no existe todavía return false; } else if ( V.length <= 1 ) { return true; } boolean ascendentes = true; int N = V.length-1; for ( int i=0; i<N; ++i ) { // determina si hay ascendentes if ( V[i] < V[i+1] ) { ascendentes = true; break; } else if ( V[i] > V[i+1] ) { ascendentes = false; // ... o si hay descendentes break; } else { // como son iguales, continúa... } } if ( ascendentes ) { // verifica ascendentes for ( int i=0; i<N; ++i ) { if ( V[i] > V[i+1] ) { return false; } } } else { // verifica descendentes for ( int i=0; i<N; ++i ) { if ( V[i] < V[i+1] ) { return false; } } } return true; } /** Retorna {@code true} si el vector {@code V[]} está ordenado. * <ul><li> El orden puede ser ascendente o descendente.</li> * <li> Un vector nulo nunca está ordenado.</li> * <li> Un vector vacío siempre está ordenado.</li></ul> */ public static boolean estaOrdenado_v3( int V[] ) { if ( V.equals(null) ) { // V[] no existe todavía return false; } else if ( V.length <= 1 ) { return true; } int i; int N = V.length-1; for ( i=0; i<N; ++i ) { if ( V[i] != V[i+1] ) { // se brinca los iguales del principio break; } } if ( i == N ) { // todos iguales ==> sí es ascendente return true; } else if ( V[i] < V[i+1] ) { for ( ; i<N; ++i ) { // verifica ascendentes if ( V[i] > V[i+1] ) { return false; } } } else { // verifica descendentes for ( ; i<N; ++i ) { if ( V[i] < V[i+1] ) { return false; } } } return true; } } // EOF: TestOrdenados.java

Soluciones

Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 2009
Derechos de autor reservados © 2009