Autor Tema: Algoritmo de ordenamiento rápido en C

0 Usuarios y 1 Visitante están viendo este tema.

30 Agosto, 2013, 01:16 pm
Leído 1919 veces

xamo

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 373
  • Karma: +0/-0
  • Sexo: Femenino
Hola, estaba intentando resolver el siguiente ejercicio de examen y me han surgido un par de problemitas. Espero que me podáis ayudar:

Ejercicio.
(No olvides crear módulos de funciones)

El algoritmo de ordenamiento rápido, el cual fue creado por el científico británico en computación C. A. R. Hoare, permite ordenar los elementos de un vector. El algoritmo trabaja de la siguiente forma:

1. Elegir un elemento del vector a ordenar, al que llamareos pivote. Tomaremos el que se encuentra en mitad del vector. Si el vector tiene un número par de elementos, tomaremos el de la izquierda o el de la derecha por convenio.
2. Recolocar los demás elementos del vector a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote se colocarán a su derecha.
3. El vector queda separado en dos subvectores: uno formado por los elementos a la izquierda del pivote, y otro por los elementos a su derecha.
4. Repetir este proceso de forma recursiva para cada subvector mientras éstos contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

Implente un programa en C que ordene los elementos de un vector mediante el algoritmo de ordenamiento rápido. Dicho programa debe contener:

- Los elementos (de tipo entero) que contiene el vector deben ser pasados por la línea de comandos del Sistema Operativo.
- El vector que contiene los números a ordenar debe ser creado con memoria dinámica.
- La función que ordene los elementos del vector debe ser recursiva y tendrá la siguiente cabecera:

void OrdRapido (int* v, int *ini, int *fin)

donde v es el vector a ordenar, ini es el índice del primer elemento del vector (pasado por referencia) y fin es el índice del último elemento del vector (pasado por referencia)


Mi intento es el siguiente:



(he tenido que sacrificar la indentación, porque si no me tomaba v[i] para poner el texto en cursiva)
 #include<stdio.h>
 #include<stdlib.h>

 void OrdRapido (int v[], int ini, int fin );

 int main (){
int n, i;

/* Pedimos la longitud del vector al usuario*/
printf("Introduce la longitud del vector de enteros a ordenar\n");
scanf ("%d", &n);

int v[n];

/*Reservamos memoria dinámica*/
 /* Me da error*/
 // v = (int*)malloc(n);

/*Pedimos los elementos*/
for (i=0; i<n; i++){
printf("Introduce el elemento %d\n", i+1);
scanf("%d", &v[i]);
  }

int ini = 0;
int fin = n-1;

/*Usamos la funcion recursiva OrdRapido sobre el vector v*/
OrdRapido (v, ini, fin);

/*Mostramos por pantalla el resultado*/

printf("El vector ordenado es: \n");

for (i=0; i<n; i++){
printf("%d ", v[i]);
}

system ("pause");
return 0;
}

 void OrdRapido (int v[], int ini, int fin){
int i, j, central, pivote;

central = (ini + fin)/2;
pivote = v[central];

i = ini;
j = fin;

do{
while (v[i] < pivote) i++;
while (v[j] > pivote) j--;

if (i<=j)
{
int tmp;
tmp = v[i];
v[i] = v[j];
v[j] = tmp; /*intercambiamos v[i] con v[j]*/
i++;
j--;
}
} while(i <= j);

if (ini < j) OrdRapido(v, ini, j); /*mismo proceso con subvector izquierdo*/
if (i < fin) OrdRapido (v, i, fin); /*mismo proceso con subvector derecho*/

 }



Mis problemas son:
- No sé hacer el programa mediante paso por referencia. (Lo he hecho mediante paso al valor). ¿Qué cambios habría que hacer para conseguirlo? Lo que yo hice fue definir ini, y fin como punteros pero me daba error.
- Mi último problema es que no sé crear el vector con memoria dinámica. Es la primera vez que me están saliendo en ejercicios.

Muchas gracias por vuestra ayuda y perdón por la longitud del mensaje.
Saludos.

30 Agosto, 2013, 04:36 pm
Respuesta #1

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Citar
he tenido que sacrificar la indentación

Para evitar eso hay que usar las etiquetas [nobbc]  [/nobbc].
Ahí no se pierde nada, aunque no podrás poner colores.


30 Agosto, 2013, 11:35 pm
Respuesta #2

xamo

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 373
  • Karma: +0/-0
  • Sexo: Femenino
Acabo de poner los tags y no ocurre nada.  :(
Gracias y saludos.

31 Agosto, 2013, 06:45 am
Respuesta #3

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Es que lo que hace falta es poner el programa ya indentado, como lo tienes en tu IDE, y luego copiarlo dentro de los tags:


#include <stdio.h>
int main(void) {
    for (int i = 0; i < 100; i++)
       printf("%d al cuadrado es... %d\n", i, i*i);

    getchar();
    return 0;
}



Igual por esta vez no te preocupes.