Doubt about recursion

Question

Doubt about recursion

Navigation

#1 by (1 votes)

0

I understand that the following problem refers to the data sorting solution using a Quicksort or at least that is supposed to be, and I have been asked to find the error by which the program gets stuck, but no matter how much I searched I find it, supposedly the error is in the void QT

/ Update /

I made the debugger, with the modifications that I mention right away and the result it gives me is not what I expected, I do not know if it is a code error or if I really do not find how to fix the error ...

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

using namespace std;

int d(int A[], int b, int z)//Arreglo, izquierda, derecha
{
    int l,r,p,t;
    p=A[b];//Pivote igual a posición  del arreglo
    l=b;//l igual a izquierda (0)
    r=z;//r igual a la derecha (9)
    while (l<r)//Mientras izquierda (0) sea menor a (9)
    {
        while(A[r]>p)//Mientras posición r del arreglo (9) sea mayor a 0
            r--;
        while (l<r && A[l]<=p)
            l++;

        if(l<r)//Si izquierda menor que derecba
        {
            t=A[r];//T igual a arreglo posición r
            A[l]=A[r];//Arreglo posición izquierda igual a arreglo derecha
            A[r]=t;//Arreglo drecha igual a t
        }
    }
    t=A[r];
    A[r]=A[b];
    A[b]=t;
    return r;
}

void QT(int A[],int b,int z)//b izquierda y z derecha
{
    int p;
    if (b<z||b>=z)//-----Cambio
        p=d(A,b,z);
    if (b<z)//--Agregué esta condicion para poder dar fin a la función QT 
        QT(A,b,p-1);
    if (b>z)//--Agregué para dar salida a la siguiente QT
        QT(A,p+1,z);//----No se implementa
}

int main()
{
    int Arr[3]={2,3,1};
    int i;
    printf("ANTES DE QS:");
    for(i=0;i<3;i++)//----Cambio
    printf("%i,",Arr[i]);
    printf("\n \n");

    QT (Arr,0,2);//-----Cambio
    printf("DESPUES DE QS:");
    for(i=0;i<3;i++)//-----Cambio
        printf("%i,",Arr[i]);//Imprime 1,1,2 ni idea por que

    return 0;
}

c++ quicksort

asked by prografail 11.03.2018 в 21:08

source

1 answer

Group 4 in 4 in Java In clause where does not discriminate a subtraction

score 1 · Accepted Answer

The QuickSort algorithm is a fast sorting algorithm, it works in 3 phases:

An element that makes the pivot is selected, ideally it should be the central value of the list, this algorithm has a better performance when the pivot that is chosen is the center one.

The list is reorganized in such a way that the elements below the pivot are on the left and the major elements are on the right.

The list is separated into two sublists, one is the left part of the pivot and the other the right, and the whole process (recursion) is repeated to these two sublists.

From: User: RolandH, CC BY-SA 3.0 , Link , Wikipedia

Make a lot of corrections to the code, starting with the headers, because you included the string.h library if you did not use it, one of the things to keep in mind, is the location of the pivot, this is fundamental for the Algorithm performance, there are several methods to improve this which I do not use any, I just place it in the middle of the list, looking for a bit of "luck" to make it a convenient data, so to speak.

You can find this code in many places where you look for quickSort, change the logic in how it is applied by each programmer, but the algorithm always tends to do the same.

I only use one function instead of two because that way I feel more comfortable, now one of the doubts that you had was why he called the function twice, well the list is separated into two sublists, one with the lower values to the pivot, and the other with the higher values, those two conditional what they do to verify that it is finished ordering a sublist, to enter to order the other.

Keep in mind that being recursive, it will be called as many times as necessary, depending on the size of the list, a very large list will be separated into two sublists, which in turn can be separated into more sublists and so recursively until ordering the entire list.

#include <iostream>

#define N_ARRAY 5

void quick_sort(int arr[],int inicio,int fin);

int main()
{
    int arr[N_ARRAY]={2,3,1,5,4};

    std::cout << "ANTES DE QS:" << std::endl;
    for(int i = 0; i < N_ARRAY; i++)//----Cambio
        std::cout << arr[i] << std::endl;

    std::cout << "\n\n";

    quick_sort(arr, 0, N_ARRAY);
    std::cout << "DESPUES DE QS:" << std::endl;

    for(int i = 0; i < N_ARRAY; i++)
        std::cout << arr[i] << std::endl;

    return 0;
}

void quick_sort(int arr[],int inicio,int fin)
{   
    int inicioAux = inicio, finAux = fin;
    int pivote = arr[static_cast<int>((inicio + fin) / 2)];

    while( inicioAux < finAux)
    {
        while(arr[inicioAux] < pivote)
            ++inicioAux;
        while(arr[finAux] > pivote)
            --finAux;

        if( inicioAux <= finAux)
        {
            int temp = arr[inicioAux];
            arr[inicioAux] = arr[finAux];
            arr[finAux] = temp; 
            ++inicioAux;
            --finAux;
        }
    }

    if( inicio < finAux)
        quick_sort(arr, inicio, finAux);
    if(inicioAux < fin)
        quick_sort(arr, inicioAux, fin);
}