elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Arreglado, de nuevo, el registro del warzone (wargame) de EHN


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  [Aporte] explicacion del funcionamiento de Quicksort
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: [Aporte] explicacion del funcionamiento de Quicksort  (Leído 2,956 veces)
Blaster

Desconectado Desconectado

Mensajes: 190


Ver Perfil
[Aporte] explicacion del funcionamiento de Quicksort
« en: 18 Abril 2013, 19:33 pm »

Hola a todos, vengo a hecer este humilde aporte, yo ya habia abrido un post sobre esto donde pedia que me expliquen para comprender como funcionaba el Algoritmo de Quicksort pero luego de muchas horas de romperme la cabeza tratando de desmenusarlo por completo al fin lo logre. Alli abajo dejo una sencilla pero detallada explicacion de como lo entendi yo, si he errado en algo porfavor haganmelo saber:

Código
  1. int dividir(int *cad, int inc, int end)
  2. {
  3.       int j;
  4.       int pibote, valor_pivote;
  5.       int temp;
  6.  
  7.       pibote = inc;
  8.       valor_pivote = cad[pibote];
  9.  
  10.       for (j = inc+1; j <= end; j++)
  11.       {
  12.           if (cad[j] < valor_pivote)
  13.           {
  14.                pibote++;
  15.  
  16.                temp = cad[j];
  17.                cad[j] = cad[pibote];
  18.                cad[pibote] = temp;
  19.            }
  20.       }
  21.       temp = cad[inc];
  22.       cad[inc] = cad[pibote];
  23.       cad[pibote] = temp;
  24.  
  25.       return pibote;
  26. }
  27.  
  28. void quicksort(int *array, int inicio, int fin)
  29. {
  30.    int pivote;
  31.  
  32.    if(inicio < fin)
  33.    {
  34.      pivote = dividir (array, inicio, fin);
  35.  
  36.      quicksort(array, inicio, pivote-1); //ordeno la lista de los menores
  37.      quicksort(array, pivote+1, fin); //ordeno la lista de los mayores
  38.    }
  39. }

Supongamos que tenemos un array con estos valores:
 
Código
  1. cad[] = {5, 2, 10, 7, 4};

En este caso tomamos como pibote al 5 y con el ciclo for recorremos el array desde la posicion 1 hasta la 4; y justo abajo tenemos un if con la condicion de que si el valor contenido en el array es menor al pibote, se ejecutara el bloque de instrucion siguiente.
En este caso, en el primer recorrido se encuentra al 2 menor al pibote, por lo tanto se cumple la condicion de la que hablabamos. Primeramente el valor del pibote aumenta a uno segun esta declaracion (pibote++;).

Luego a la variable auxiliar (temp) le asignamosel valor de 2 ya que en ese instante el indice [j] contendra el valor de 1 donde esta guardada 2, luego a (cad[j]) le asignamos (cad[pibote]) recuerden que pibote ahora vale 1 y no olvidar que tambien [j]
Se dieron cuenta cad[j] conservo su valor y en esta parte ocurrio lo mismo
(cad[pibote] = temp;) por que los dos [j] y [pibote] trabajaroncon las mismas posiciones osea 1 y no se produjeron intercambios.

Continuamos con el primer recorrido y detectamos que 4 es menor al pibote se cumple la condicion pibote aumenta a 2 ya que valia 1, luego hacemos los cambios (temp) contendra a 4 y (cad[j]) la ultima posicion le asignamos 10 recuerden que [j] vale 4, luego a cad[pibote] le asignamos temp osea 4 recuerden que [pibote] vale 2.

Como ven se intercambiaron  10 y 4; ahora nuestro array quedara asi:

Código
  1. cad[] = {5, 2, 4, 7, 10};
  2.  

Ahora ya salimos del primer recorrido en esta parte hacemos los intercambios
pertinentes con estas declaraciones:

Código
  1. temp = cad[inc];
  2. cad[inc] = cad[pibote];
  3. cad[pibote] = temp;

Con los valores finales de pibote al salir del ciclo en este caso es 2
como se daran cuenta aca ocurre un intercambio, deben saber que (inc) vale 0 su
valor no varia mientras no se ejecute la funcion recursiva, y e obvio que se
intercambiaron 4 y 5 ahora el array pasa asi:

Código
  1. cad[] = {4, 2, 5, 7, 10};

Al salir pibote retorna 2 y se ejecuta la funcion que ordena la lista de los menores
como ven a (pivote-1) pasa a valer solo 1, osea solo podemos leer los valores
cad[] = {4, 2}; ahora el 4 actua como pibote y (inc) sigue valiendo 0 ahora en este
recorrido encuentra que 2 es menor al pibote y aumenta pibote a 1 como ya es de predecir  en esta parte no se produciran intercambios.

Salimos de ciclo, y hacemos los intercambios con las declaraciones de abajo,
pibote termina con un valor final de 1 y (inc) sigue con 0; se intercambian los valores quedando asi nuestro array:

Código
  1. cad[] = {2, 4, 5, 7, 10};

 Y de esta forma quedo ordenado nuestro array; creo que luego se volvio a ejecutar la parte que ordena la lista de los mayores pero sin realizar cambios.
 Espero que a algunos iniciados en esto de la programacion le sirva para aprender de este algoritmo y a los que ya dominan este tema me corrija si he fallado en algo

Saludos!!  ;D


« Última modificación: 4 Mayo 2013, 16:49 pm por двоичный » En línea

85

Desconectado Desconectado

Mensajes: 206



Ver Perfil WWW
Re: [Aporte] explicacion del funcionamiento de Quicksort
« Respuesta #1 en: 20 Abril 2013, 02:00 am »

podés hacer otros tutoriales de otros tipos de ordenamientos, ya que estás en el tema. para expandirte a otros algoritmos.
No revisé tu código mayormente porque es casi lo mismo que el de la wiki XD, igual se que la intención de todo esto es hacer un tutorial, así que bien
salu2



En línea

Me cerraron el Windows Live Spaces, entonces me creé un WordPress XD
http://etkboyscout.wordpress.com/
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Quicksort
Java
mapers 4 3,938 Último mensaje 20 Septiembre 2010, 07:16 am
por mapers
grafica de Quicksort
Java
mapers 3 4,671 Último mensaje 20 Septiembre 2010, 19:31 pm
por 1mpuls0
[Aporte] Probar funcionamiento de un DSN creado con driver SQLserver
Java
horny3 0 1,342 Último mensaje 20 Julio 2012, 22:49 pm
por horny3
[Aporte] Probar funcionamiento de un DSN creado con driver SQLserver
Java
horny3 0 1,419 Último mensaje 20 Julio 2012, 23:11 pm
por horny3
Explicación quicksort usando recursividad
PHP
Giankaa 2 2,560 Último mensaje 7 Junio 2016, 03:36 am
por Giankaa
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines