Difficulties with quickSort algorithm in C

Asked

Viewed 253 times

-1

I need to do a college work involving quicksort, but I’m finding difficulties in the code:

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

#define RA 8

int quickSort(int *vec[], int left, int right, int qtd );
int partition(int *vec[], int left, int right);
void troca(int *x,int *y);

main(){
    int vet[RA] = {1,8,3,6,2,5,2,5};
    int left = 0;
    int right = left + 1;
    int qtd;

    printf("Antes do QuickSort: ");
    printf("\n[ ");
    for(int i = 0; i <= RA; i++){
        printf("%d ",vet[i]);
    }
    printf(" ]\n");

    quickSort(&vet[RA], left, right, qtd);
}

int quickSort(int vec[], int left, int right, int qtd){
    int r;
    if (right > left){
        r = partition(&vec,left,right);
        qtd = quickSort(&vec,left, r - 1, qtd);
        qtd = quickSort(&vec, r+1, right, qtd);
    }
    return (qtd + 1);
}

int partition(int *vec[], int left, int right){
    int i, j;
    i = left;
    for(j = left + 1; j <= right; j++){
        if(vec[j] < vec[left]){
            i++;
            troca(&vec[i], &vec[j]);
        }
    }
    troca(&vec[left],&vec[i]);
    return i;
}

void troca(int *x,int *y, int aux){
    aux = *x;
    *x = *y;
    *y = aux;
}

Return me the following errors:

Estrutura 2.cpp In function 'int main()':

[Error] cannot convert 'int*' to 'int**' for argument '1' to 'int quickSort(int**, int, int, int)'

In function 'int partition(int**, int, int)':

[Error] cannot convert 'int**' to 'int*' for argument '1' to 'void troca(int*, int*)'

[Error] cannot convert 'int**' to 'int*' for argument '1' to 'void troca(int*, int*)'

I have the slight impression that I did something wrong in passing parameters.

c quicksort

  • What don’t you understand? What you tried to solve the situation?

  • @Mauroalmeida errors seem to draw attention to the passing of parameters, but when modifico returns more errors.

  • 1

    Do you know the difference between memory addresses and pointers? Use of '&' and '*'?

  • @Mauroalmeida * vc will be accessing the contents of the variable in memory, and & vc will be indicating the address of the variable in memory.

  • exact, that’s it. Your problem is passing parameters as address in the case of the array. The array is already a pointer to memory.

  • @Mauroalmeida yes ,but where exactly the passage would be wrong?

  • Vc passes a memory address to the quicksort Function and puts in the method signature that the parameter is an int *vec[], but in the implementation already puts as int vec[].

  • to get the value of the pointer you have to put * before the variables that are pointers and not the &

  • understood the mistake or need more tips? I did not want to give answer, it is better when we get there.

  • @Mauroalmeida No, I still don’t understand but I’m analyzing the code and it’s really better when the solution snaps in my head.

  • 1

    Another thing I don’t understand is the number of parameters your swap function has. The signature has two and the implementation has 3. I think the implementation with 3 parameters does not make sense because the auxiliary variable should be started within the method and not as a parameter.

  • And in the uses of this function you never put the third parameter.

  • @Mauroalmeida as so third parameter?

  • 1

    On one side you have int quickSort(int *vec[] but the other has int quickSort(int vec[] so the compiler doesn’t know which one you want. And the same for here void troca(int *x,int *y) Down below is like this void troca(int *x,int *y, int aux).

Show 9 more comments

1 answer

0

Code tests, below some comment of the unnecessary parts of the code:

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

void troca(int x,int y){
  int aux;
    aux = x;
    x = y;
    y = aux;
}

int partition(int vec[], int left, int right){
    int i, j;
    i = left;
    for(j = left + 1; j <= right; j++){
        if(vec[j] < vec[left]){
            i++;
            troca(vec[i], vec[j]);
        }
    }
    troca(vec[left],vec[i]);
    return i;
}

int quickSort(int vec[], int left, int right, int qtd){
    int r;
    if (right > left){
        r = partition(vec,left,right);
        qtd = quickSort(vec,left, r - 1, qtd);
        qtd = quickSort(vec, r+1, right, qtd);
    }
    return (qtd + 1);
}

int main(){
    int vet[8] = {1,8,3,6,2,5,2,5};
    int left = 0;
    int right = left + 1;
    int qtd;

    printf("Antes do QuickSort: ");
    printf("\n[ ");
    for(int i = 0; i < 8; i++){
        printf("%d ",vet[i]);
    }
    printf(" ]\n");

    quickSort(&vet[8], left, right, qtd);
}

Problems encountered: 1). Paragraph 1 for of the main function should be < nay <= 'cause I’d print out memory junk.

for(int i = 0; i <= RA; i++){
    printf("%d ",vet[i]);
}
printf(" ]\n");

2). You declared variables without pointer, then required them to have in the functions they had pointer.

int quickSort(int *vec[], int left, int right, int qtd );
int partition(int *vec[], int left, int right);
void troca(int *x,int *y);

3). The placement of & within the function quicksort,partition and :

qtd = quickSort(&vec,left, r - 1, qtd);
        qtd = quickSort(&vec, r+1, right, qtd);

//

for(j = left + 1; j <= right; j++){
        if(vec[j] < vec[left]){
            i++;
            troca(&vec[i], vec[j]);
        }
    }
    troca(&vec[left],vec[i]);

Browser other questions tagged c quicksort

You are not signed in. Login or sign up in order to post.