EVAP - 7 ORDENAMIENTO

ORDENAMIENTO

Los algoritmos de ordenación son un tema de constante estudio en las ciencias informáticas.

El ordenamiento por burbuja es bastante sencillo, consiste en evaluar pares de elementos contiguos del arreglo y si el primero es mayor que el siguiente los intercambia (los más chicos quedan abajo). Todo ésto sucede dentro de dos ciclos for que recorren el arreglo. El ciclo más interno realiza las comparaciones, y se asegura ya en la primera pasada completa que el elemento más grande del arreglo suba a la posición más alta.

Conceptos Preliminares

·          Clave: La parte de un registro por la cual se ordena la lista. Por ejemplo, una lista de registros con campos nombre, direccion y telefono se puede ordenar alfabéticamente de acuerdo a la clave nombre. En este caso los campos direccion y telefono no se toman en cuenta en el ordenamiento.

·          Criterio de ordenamiento (o de comparación): EL criterio que utilizamos para asignar valores a los registros con base en una o más claves. De esta manera decidimos si un registro es mayor o menor que otro. En el pseudocódigo presentado más adelante simplemente se utilizarán los símbolos < y >, para mayor simplicidad.

·          Registro: Un grupo de datos que forman la lista. Pueden ser datos atómicos (enteros, caracteres, reales, etc.) o grupos de ellos, que en C equivalen a las estructuras.

Tipos de Ordenamiento:

Ordenamiento Burbuja

//Ordena el número de números que usted quiera.

//Codificado por: Danny Henderson

??=include<iostream>

using namespace std;

int main()

??<

    int i,j,k,cn;

    int n??('cn'??);

    cout<<"Cantidad de numeros que desea Ingresar: ";cin>>cn;

    for(i=0;i<cn;i++)

    {

        cout<<"Ingrese  numero "<<i+1<<" : ";

        cin>>n[i];

    }

    for(i=1;i<cn;i++)

    {

        for(j=0;j<cn-i;j++)

        {

            if(n[j]>n[j+1])

            {k=n[j+1]; n[j+1]=n[j]; n[j]=k;}

        }

    }

    for(i=0;i<cn;i++)

    {

        cout<<n[i]<<endl;

    }

    cin.ignore(); return 0;

??>

Ordenamiento por selección

//Selection sort

//Codificado por sAfOrAs

#include<iostream>

using namespace std;

#include"leearreglo.h"

#define largo 50

void seleccionsort (int  A[], int n)

{

        int min,i,j,aux;

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

        {

              min=i;

              for(j=i+1; j<n; j++)

                    if(A[min] > A[j])

                       min=j;

              aux=A[min];

              A[min]=A[i];

              A[i]=aux ;

        }

}

void main ()

{

    int A[largo],n;

    do{

    cout<<"Cantidad de numeros a ingresar: ";cin>>n;

        if(n<=0||n>largo)

            cout<<"Debe ingresar un valor  > a 0 y < a "<<largo<<endl;

    }while(n<=0||n>largo);

    leeCadena(n,A);

    seleccionsort(A,n);

muestraCadena(n,A);

   

#include<iostream>

using namespace std;

void leeCadena(int cant,int n[])

{

    int i;

    for(i=0;i<cant;i++)

    {

        cout<<"Ingresa numero "<<i+1<<": ";

        cin>>n[i];

    }

     

}

void muestraCadena(int cant,int n[])

{

    int i;

    for(i=0;i<cant;i++)

    {

        cout<<n[i]<<endl;

    }

}

Ordenamiento por Inserción Directa

//Inserción Directa

//Codificado por sAfOrAs

#include<iostream>

#include"leearreglo.h"

using namespace std;

#define largo 50

void insercionDirecta(int A[],int n)

{

      int i,j,v;

      for (i = 1; i < n; i++)

        {

             v = A[i];

             j = i - 1;

             while (j >= 0 && A[j] > v)

             {

                  A[j + 1] = A[j];

                  j--;

             }

             

             A[j + 1] = v;

      }  

}

  

void main ()

{

    int A[largo],n;

    do{

    cout<<"Cantidad de numeros a ingresar: ";cin>>n;

        if(n<=0||n>largo)

            cout<<"Debe ingresar un valor  > a 0 y < a "<<largo<<endl;

    }while(n<=0||n>largo);

    leeCadena(n,A);

    insercionDirecta(A,n);

    muestraCadena(n,A);

   

}

EVAP - 6 MATRICES

                                                                    MATRICES


Una matriz es una colección de objetos similares. El caso mas simple de una matriz es un vector, que se puede declarar mediante la siguiente secuencia:

decl-specifier identifier [ constant-expression ]
decl-specifier identifier []
decl-specifier identifer [][ constant-expression] . . .
decl-specifier identifier [ constant-expression ]
[ constant-expression ] . . .

1. El especificador de declaración:

• Un especificador de clase de almacenamiento opcional.
• Especificadores const y/o volatile opcionales.
• El tipo de nombre de los elementos de la matriz.

2. El declarador:

• El identificador.
• Una expresión constante de tipo entero incluida entre corchetes, []. Si se declaran varias dimensiones con corchetes adicionales, la expresión constante se puede omitir en el primer conjunto de corchetes.
• Corchetes adicionales opcionales que encierran expresiones constantes.

3. Un inicializador opcional.

El número de elementos de la matriz viene determinado por la expresión constante. El primer elemento de la matriz es el elemento 0 y el último elemento es el elemento (n-1), donde n es el número de elementos que la matriz puede contener. El elemento constant-expression debe ser de tipo entero y debe ser mayor que 0. Una matriz de tamaño cero es válida únicamente cuando la matriz es el último campo en un struct ounion y cuando las extensiones de Microsoft (/Ze) están habilitadas.

En el ejemplo siguiente se muestra cómo definir una matriz en tiempo de ejecución:

// arrays.cpp
// compile with: /EHsc
#include <iostream>

int main() {
   using namespace std;
   int size = 3, i = 0;

   int* myarr = new int[size];

   for (i = 0 ; i < size ; i++)
      myarr[i] = 10;

   for (i = 0 ; i < size ; i++)
      printf_s("myarr[%d] = %d\n", i, myarr[i]);

   delete [] myarr;
}

Las matrices son tipos derivados y, por tanto, pueden construirse a partir de cualquier otro tipo derivado o fundamental, salvo funciones, referencias y void.

Las matrices construidas a partir de otras matrices son matrices multidimensionales. Estas matrices multidimensionales se especifican colocando en orden varias expresiones constantes entre corchetes. Por ejemplo, considere esta declaración:

int i2[5][7];

Especifica una matriz de tipo int, organizada conceptualmente en una matriz bidimensional de cinco filas y siete columnas, como se muestra en la ilustración siguiente:

Diseño conceptual de matriz multidimensional

En las declaraciones de las matrices multidimensionales que tienen una lista de inicializadores (como se describe en Inicializadores), se puede omitir la expresión constante que especifica los límites de la primera dimensión.

 Por ejemplo:

// arrays2.cpp
// compile with: /c
const int cMarkets = 4;
// Declare a float that represents the transportation costs.
double TransportCosts[][cMarkets] = { 
   { 32.19, 47.29, 31.99, 19.11 },
   { 11.29, 22.49, 33.47, 17.29 },
   { 41.97, 22.09,  9.76, 22.55 }
};

La declaración anterior define una matriz de tres filas por cuatro columnas. Las filas representan fábricas y las columnas representan los mercados a los que distribuyen las fábricas. Los valores son los costos de transporte de las fábricas a los mercados. La primera dimensión de la matriz se omite, pero el compilador la completa examinando el inicializador.

EVAP-5 VECTORES

   VECTORES

 El vector es una estructura de datos que permite agrupar elementos del mismo tipo y almacenarlos en un solo bloque de memoria juntos, uno después de otro. A este grupo de elementos se les identifica por un mismo nombre y la posición en la que se encuentran. La primera posición del array es la posición 0.

ESTRUCTURA DE UN VECTOR

La estructura de la clase vector esta pensada para operar con arreglos unidimensionales de datos, los elementos de un vector pueden ser manipulados de la misma manera que se hace con la estructura de arreglos tradicionales en C, C++; es decir, los componentes de un vector pueden ser referenciados a través de un indice numérico, de la misma manera que un arreglo cualquiera.

Por ejemplo, si A es un objeto de vector, entonces la instrucción: A(0) ; se refiere al componente 0 (primer elemento) de A. El resultado de todo esto es que usted puede navegar o iterar a través de los componentes de una lista haciendo uso de indices, o si lo prefiere a través de punteros iteradores.

FORMAS DE ACCESO

La forma de acceder a los elementos de la matriz es directa; esto significa que el elemento deseado es obtenido a partir de su índice y no hay que ir buscándolo elemento por elemento (en contraposición, en el caso de una lista, para llegar, por ejemplo, al tercer elemento hay que acceder a los dos anteriores o almacenar un apuntador o puntero que permita acceder de manera rápida a ese elemento).

Para trabajar con vectores muchas veces es preciso recorrerlos. Esto se realiza por medio de bucles. El siguiente pseudocódigo muestra un algoritmo típico para recorrer un vector y aplicar una función '' a cada una de las componentes del vector:

i = 0
mientras (i < longitud)
    #Se realiza alguna operación con el vector en la i-ésima posición
    f(v[i])
    i=i+1
fin_mientras

EJERCICIOS SOBRE VECTOR (array)

Que lea 10 números por teclado, los almacene en un array y muestre la suma, resta, multiplicación y división de todos.

#include <stdio.h>

#include <stdlib.h>

int main(void)

{

            int x,tabla[10];

            int sum,res,mul,div;

           

            for (x=0;x<10;x++)

            {

        printf("Introduzca número\n");

        scanf("%d",&tabla[x]);

    }

           

            sum=tabla[0];

    res=tabla[0];

    mul=tabla[0];

    div=tabla[0];

           

            for (x=1;x<10;x++)

            {

        sum=sum+tabla[x];

        res=res-tabla[x];

        mul=mul*tabla[x];

        div=div/tabla[x];

    }

           

            printf("Suma: %d\n",sum);

            printf("Resta: %d\n",res);

            printf("Multiplicación: %d\n",mul);

            printf("División: %d\n",div);

           

    system("PAUSE");     

    return 0;

}

 Que lea 10 números por teclado, los almacene en un array y los ordene de forma ascendente.

#include <stdio.h>

#include <stdlib.h>

int main()

{

  float aux, numeros[10];

  int i,j,n=10;

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

                    printf("Escriba un número");

                    scanf("%f",&numeros[i]);

      }

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

  {

   for(j=i+1;j<n;j++)

   {

       if(numeros[i]<numeros[j])

       {

           aux=numeros[i];

           numeros[i]=numeros[j];

           numeros[j]=aux;

       }

   }

  }

  for (i=n-1;i>=0;i--){

      printf("%f\n",numeros[i]);

  }

     

  system("PAUSE");     

  return 0;

}