Problema con ordenamiento quicksort en C (lenguajec)

[rackdon]

Buenas noches.
He escrito el siguiente código pero me da error al final, la función quicksort funciona bien si elimino las 2 últimas líneas pero entonces no termina de ordenar el arreglo.
¿Podría alguien decirme donde está el error?
Muchas gracias

Código: [Seleccionar]

// Ejercicio 7.24: Ordenamiento Quicksort //

#include <stdio.h>

void quicksort ( int arreglo[], int tamanio, int inicio, int fin);
void intercambio (int *ptr1, int *ptr2);
void particion (int arreglo[], int tamanio, int izq, int dcha);

main()
{
    int i;
    int arreglo [10] = {37,2,6,4,89,8,10,12,68,45};

    printf("Arreglo desordenado\n\n");
    for(i = 0; i < 10; i++)
    {
        printf("%d ", arreglo[i]);
    }

    quicksort(arreglo, 10, 0, 9);

    printf("\n\nArreglo ordenado\n\n");

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


    return 0;
}

void quicksort( int arreglo[], int tamanio, int inicio, int fin)
{
    int i, elemento, lim_elemento;

    if (inicio >= fin )
    {
        return;
    }

    else
    {
        for (i = fin; arreglo[i] > arreglo[inicio]; i--)
        {
            ;
        }

        intercambio(&arreglo[inicio], &arreglo[i]);
        elemento = i;

        for (i = inicio; arreglo[i] < arreglo[elemento]; i++)
        {
            ;
        }

        intercambio(&arreglo[elemento], &arreglo[i]);
        lim_elemento = elemento;
        elemento = i;

        for (i = lim_elemento-1; arreglo[i] > arreglo[elemento]; i--)
        {
            ;
        }

        intercambio(&arreglo[elemento], &arreglo[i]);
        lim_elemento = elemento;
        elemento = i;

        for (i = lim_elemento+1; arreglo[i] < arreglo[elemento]; i++)
        {
            ;
        }

        intercambio(&arreglo[elemento], &arreglo[i]);
        lim_elemento = elemento;
        elemento = i;

        printf("\n%d\n\n", i);

        particion(arreglo, 10, 0, elemento -1);
        particion(arreglo, 10, elemento + 1, 9);

    }
}

void particion (int arreglo[], int tamanio, int izq, int dcha)
{
    quicksort(arreglo, 10, izq, dcha);
}

void intercambio (int *ptr1, int *ptr2)
{
    int temp;
    temp = *ptr1;
    *ptr1 = *ptr2;
    *ptr2 = temp;
}

La otra variante de código que he escrito es las siguiente, pero me ocurre lo mismo.

Código: [Seleccionar]

// Ejercicio 7.24: Ordenamiento Quicksort //

#include <stdio.h>

void quicksort ( int arreglo[], int tamanio, int inicio, int fin);
void intercambio (int *ptr1, int *ptr2);
int particion (int arreglo[], int tamanio, int izq, int dcha);

main()
{
    int i;
    int arreglo [10] = {37,2,6,4,89,8,10,12,68,45};

    printf("Arreglo desordenado\n\n");
    for(i = 0; i < 10; i++)
    {
        printf("%d ", arreglo[i]);
    }

    quicksort(arreglo, 10, 0, 9);

    printf("\n\nArreglo ordenado\n\n");

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


    return 0;
}

void quicksort( int arreglo[], int tamanio, int inicio, int fin)
{
    int posicion;

    if (inicio >= fin )
    {
        return;
    }

    else
    {
        posicion = particion(arreglo, tamanio, inicio, fin);

        quicksort(arreglo, 10, inicio, posicion -1);
        quicksort(arreglo, 10, posicion + 1, fin);

    }
}

int particion (int arreglo[], int tamanio, int inicio, int fin)
{
    int i, elemento, lim_elemento;

    for (i = fin; arreglo[i] > arreglo[inicio] ; i--)
        {
            ;
        }

        intercambio(&arreglo[inicio], &arreglo[i]);
        elemento = i;

        for (i = inicio; arreglo[i] < arreglo[elemento] ; i++)
        {
            ;
        }

        intercambio(&arreglo[elemento], &arreglo[i]);
        lim_elemento = elemento;
        elemento = i;

        for (i = lim_elemento-1; arreglo[i] > arreglo[elemento]; i--)
        {
            ;
        }

        intercambio(&arreglo[elemento], &arreglo[i]);
        lim_elemento = elemento;
        elemento = i;

        for (i = lim_elemento+1; arreglo[i] < arreglo[elemento]; i++)
        {
            ;
        }

        intercambio(&arreglo[elemento], &arreglo[i]);
        lim_elemento = elemento;
        elemento = i;

        return elemento;


}

void intercambio (int *ptr1, int *ptr2)
{
    int temp;
    temp = *ptr1;
    *ptr1 = *ptr2;
    *ptr2 = temp;
}


[dongo]

hola, buenas... le he metido a tu programa una serie de lineas de depuración para ver que iba pasando y no le veo lógica a las operaciones que va realizando el procedimiento. Incluso conforme va avanzando, el array resultante no tiene nada que ver con el de origen...XDD.

Yo intentaría replantear bien el ejercicio, puedes siempre buscar algun algoritmo de ordenación y aplicarlo... para que reinventar la rueda....(http://es.wikipedia.org/wiki/Ordenamiento_de_burbuja)

Y nada, te paso tu ejercicio modificado con las lineas que yo e he incluido para que veas...

Código: [Seleccionar]

// Ejercicio 7.24: Ordenamiento Quicksort //

#include <stdio.h>
#include <iostream>




void quicksort ( int arreglo[], int tamanio, int inicio, int fin);
void intercambio (int *ptr1, int *ptr2);
void particion (int arreglo[], int tamanio, int izq, int dcha);

main()
{
    int i;
    int arreglo [10] = {37,2,6,4,89,8,10,12,68,45};

    printf("Arreglo desordenado\n\n");
    for(i = 0; i < 10; i++)
    {
        printf("%d ", arreglo[i]);
    }

    quicksort(arreglo, 10, 0, 9);

    printf("\n\nArreglo ordenado\n\n");

    for(i = 0; i < 10; i++)
    {
        printf("%d ", arreglo[i]);
    }
    printf("Fin DEl Programa");
    system("pause");
    return 0;
}

void quicksort( int arreglo[], int tamanio, int inicio, int fin)
{
    int i,n, elemento, lim_elemento;

    if (inicio >= fin )
    {
        return;
    }

    else
    {
        for (i = fin; arreglo[i] > arreglo[inicio]; i--)
        {
           ;
           
        }
        printf("\n  intercambio %d por %d",arreglo[inicio],arreglo[i]);
        system("pause");
        intercambio(&arreglo[inicio], &arreglo[i]);
        elemento = i;

        for (i = inicio; arreglo[i] < arreglo[elemento]; i++)
        {
            ;
         
        }
        printf("\n  intercambio %d por %d",arreglo[elemento],arreglo[i]);
        system("pause");
        intercambio(&arreglo[elemento], &arreglo[i]);
        lim_elemento = elemento;
        elemento = i;

        for (i = lim_elemento-1; arreglo[i] > arreglo[elemento]; i--)
        {
            ;
        }
        printf("\n intercambio %d por %d",arreglo[elemento],arreglo[i]);
        system("pause");
        intercambio(&arreglo[elemento], &arreglo[i]);
        lim_elemento = elemento;
        elemento = i;

        for (i = lim_elemento+1; arreglo[i] < arreglo[elemento]; i++)
        {
            ;
        }
        printf("\n  intercambio %d por %d",arreglo[elemento],arreglo[i]);
        system("pause");
        intercambio(&arreglo[elemento], &arreglo[i]);
        lim_elemento = elemento;
        elemento = i;

        for(n=0;n<=9;n++){
            printf("%d ",arreglo[n]);
        }
        system("pause");
        //printf("\n%d\n\n", i);
        particion(arreglo, 10, 0, elemento -1);
        particion(arreglo, 10, elemento + 1, 9);
       

    }
}

void particion (int arreglo[], int tamanio, int izq, int dcha)
{
    quicksort(arreglo, 10, izq, dcha);
}

void intercambio (int *ptr1, int *ptr2)
{
    int temp;
    temp = *ptr1;
    *ptr1 = *ptr2;
    *ptr2 = temp;
}


[rackdon]

Buenos dias
El problema es que es un ejercicio del libro "Como programar en c/c++" de Deitel. El planteamiento era el que he puesto, el problema creo que lo tengo al hacer la recursividad, pero no consigo ver donde está el fallo en esa recursividad.

[Mastermind]

Hola, aquí hay una explicación del quicksort que quizás pueda ayudar: https://www.aprenderaprogramar.com/foros/index.php?topic=133

Salud22

[rackdon]

Buenas tardes.

El mecanismo lo entiendo bien, el problema creo que está en la recursividad, que es lo que me da error, porque el colocar el primer elemento en su posición definitiva sí que me sale, lo malo es al intentar ordenar los 2 vectores restantes (izquierda y derecha del número colocado) aplicando la recursividad
Un saludo

[dongo]

Bueno he estado echándole el rato y he modificado las dos ultimas lineas que son las que provocan que  se genere un bucle infinito, por tanto le metido una condición de parada, aun así sigue sin funcionar completamente,pero al menos ya para. Falla en la partición derecha, la izquierda la ace bien + o - sale un 2 duplicado nose de donde..... XDD

Código: [Seleccionar]

// Ejercicio 7.24: Ordenamiento Quicksort //

#include <stdio.h>
#include <iostream>

void quicksort ( int arreglo[], int tamanio, int inicio, int fin);
void intercambio (int *ptr1, int *ptr2);
void particion (int arreglo[], int tamanio, int izq, int dcha);

main()
{
    int i;
    int arreglo [10] = {37,2,6,4,89,8,10,12,68,45};

    printf("Arreglo desordenado\n\n");
    for(i = 0; i < 10; i++)
    {
        printf("%d ", arreglo[i]);
    }

    quicksort(arreglo, 10, 0, 9);

    printf("\n\nArreglo ordenado\n\n");

    for(i = 0; i < 10; i++)
    {
        printf("%d ", arreglo[i]);
    }
    system("pause");

    return 0;
}

void quicksort( int arreglo[], int tamanio, int inicio, int fin)
{
    int i, elemento, lim_elemento;

    if (inicio >= fin )
    {
        return;
    }

    else
    {
        for (i = fin; arreglo[i] > arreglo[inicio]; i--)
        {
            ;
        }

        intercambio(&arreglo[inicio], &arreglo[i]);
        elemento = i;

        for (i = inicio; arreglo[i] < arreglo[elemento]; i++)
        {
            ;
        }

        intercambio(&arreglo[elemento], &arreglo[i]);
        lim_elemento = elemento;
        elemento = i;

        for (i = lim_elemento-1; arreglo[i] > arreglo[elemento]; i--)
        {
            ;
        }

        intercambio(&arreglo[elemento], &arreglo[i]);
        lim_elemento = elemento;
        elemento = i;

        for (i = lim_elemento+1; arreglo[i] < arreglo[elemento]; i++)
        {
            ;
        }

        intercambio(&arreglo[elemento], &arreglo[i]);
        lim_elemento = elemento;
        elemento = i;

        printf("\n%d\n\n", i);

        if(0<=elemento)
        particion(arreglo, 10, 0, elemento -1);
        if(9<=elemento)
        particion(arreglo, 10, elemento+1 , 9);

    }
}

void particion (int arreglo[], int tamanio, int izq, int dcha)
{
    quicksort(arreglo, 10, izq, dcha);
}

void intercambio (int *ptr1, int *ptr2)
{
    int temp;
    temp = *ptr1;
    *ptr1 = *ptr2;
    *ptr2 = temp;
}

La verdad que el planteamiento que has elegido con bucles for... no acabo de verlo totalmente... pero eso, la clave esta en que las dos ultimas instrucciones deben estar bajo una condición de parada sino se genera un bucle infinito. Te paso un enlace a una pagina donde sale echo con bucles while anidados...

http://codigoprogramacion.com/cursos/tutoriales-c/quicksort-en-c-algoritmo-de-ordenamiento.html#.U_Y6tfRdVrM

Y nada, échale un ojo, a ver si eres capaz de sacarlo. Un saludo

[rackdon]

Buenas noches.

Muchas gracias por mirarlo.
He probado lo que decias pero aun así me sigue saliendo core dumped, la única forma de que se ejecute el programa hasta el final es borrando las 2 lineas de recursividad jejeje.
Mañana lo mirare más a fondo a ver si lo saco....
Muchas gracias por la ayuda

[rackdon]

Buenos dias.

Ya he conseguido que funcione.
El problema estaba en los ciclos for en los que declaraba "i = lim_elemento - 1"
ó "i = lim_elemento + 1". Tenía que hacerse unicamente como lim_elemento sin añadir nada.
Pongo a continuación el código. Puede que no sea el más eficiente pero da resultado

Código: [Seleccionar]

// Ejercicio 7.24: Ordenamiento Quicksort //

#include <stdio.h>

void quicksort ( int arreglo[], int tamanio, int inicio, int fin);
void intercambio (int *ptr1, int *ptr2);
int particion (int arreglo[], int tamanio, int izq, int dcha);

main()
{
    int i;
    int arreglo [10] = {37,2,6,4,89,8,10,12,68,45};

    printf("Arreglo desordenado\n\n");
    for(i = 0; i < 10; i++)
    {
        printf("%d ", arreglo[i]);
    }

    quicksort(arreglo, 10, 0, 9);

    printf("\n\nArreglo ordenado\n\n");

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


    return 0;
}

void quicksort( int arreglo[], int tamanio, int inicio, int fin)
{
    int posicion;

    if (inicio >= fin )
    {
        return;
    }

    else
    {
        posicion = particion(arreglo, tamanio, inicio, fin);
        //recursividad//
        quicksort(arreglo, tamanio, posicion + 1, fin);
        quicksort(arreglo, tamanio, inicio, posicion -1);
    }
}

int particion (int arreglo[], int tamanio, int inicio, int fin)
{
    int i, elemento = inicio, lim_elemento;

    for (i = fin; arreglo[i] > arreglo[elemento] && arreglo[i] != arreglo[elemento]; i--)
        {
            ;
        }
    intercambio(&arreglo[elemento], &arreglo[i]);
    elemento = i;

    for (i = inicio; arreglo[i] < arreglo[elemento] && arreglo[i] != arreglo[elemento]; i++)
    {
        ;
    }
    intercambio(&arreglo[elemento], &arreglo[i]);
    lim_elemento = elemento;
    elemento = i;

    for (i = lim_elemento; arreglo[i] > arreglo[elemento] && arreglo[i] != arreglo[elemento]; i--)
    {
        ;
    }
    intercambio(&arreglo[elemento], &arreglo[i]);
    lim_elemento = elemento;
    elemento = i;

    for (i = lim_elemento; arreglo[i] < arreglo[elemento] && arreglo[i] != arreglo[elemento]; i++)
    {
        ;
    }
    intercambio(&arreglo[elemento], &arreglo[i]);

    return i;
}

void intercambio (int *ptr1, int *ptr2)
{
    int temp;
    temp = *ptr1;
    *ptr1 = *ptr2;
    *ptr2 = temp;
}


[dongo]

Estupendo, gracias por aportar la solución, puede ser útil para otros compañeros.