How to apply "goto" in quicksort? (c, c ++)

1

I'm doing a job for my college where I ask that a quicksort algorithm be done in C, using "goto" as much as I can.

In the code below I applied "goto" to my knowledge, but I would like someone to help me apply "goto" to the rest of the algorithm.

#include<stdio.h>

void quickSort(int *vetor, int inicio, int fim)
{

int i, j, meio, aux;

init0:

i = inicio;
j = fim;
meio = vetor[(inicio + fim) / 2];

init1:

if (i <= j) {

init2:  
if(vetor[i] < meio){
i++;
goto init2;
}

init3:  
if(vetor[j] > meio){
j--;
goto init3;
}

if(i <= j)
{
aux = vetor[i];
vetor[i] = vetor[j];
vetor[j] = aux;
i++;
j--;
}

goto init1;

}

if(inicio < j) {
quickSort(vetor, inicio, j);
}

if(i < fim){
//quickSort(vetor, i, fim);
inicio=i;
goto init0;
}

}

int main(){

int arr1[10] = { 55, 44, 32, 11, 68, 97, 92, 30, 62, 74 };
int pivot, j, e, i, aux;

i=0;
j=9;

quickSort(arr1, i, j);

i=0;
inicio3:
if (i<10) {
printf("%d ,", arr1[i]);
i++;
goto inicio3;
}

}
    
asked by anonymous 18.04.2017 / 04:16

1 answer

2

The goto is a non-conditional jump, can be considered the basis for all flow control .

With a combination of if and goto you can create any flow control, I think this is the purpose of the peculiar exercise.

Although your code is already reduced to if s. I recommend that you write the normal way code and then replace the flow controls by constructions using goto (if not resolved), as in the examples:

if / else

if(x==0)
{
    printf("verdadeiro\n");
}
else
{
    printf("falso\n");
}
printf("fim if else\n");

Can be represented with goto s:

if(x==0)
    goto if_1; //se o if for verdadeiro, executa essa expressão
    goto else_1; //se for falso, ignora a expressão anterior e executa essa

if_1:
    printf("verdadeiro\n");
    goto fim_if_else1;

else_1:
    printf("falso\n");
    goto fim_if_else1;

fim_if_else_1:
    printf("fim if else\n");

for

Data:

int a=0;
int b=5;
int x;

The loop:

for(x=a; x<b; x++)
{
    printf("{for entre [%d e %d)} x = %d,  \n", a, b, x);
}
printf("fim [for]\n");

Can be made explicit using goto s:

inicio_for_1:
    x=0;
verifica_for_1:
    if(x<b) 
        goto corpo_for_1;
        goto fim_for_1;
corpo_for_1:
    printf("{for entre [%d e %d)} x = %d,  \n", a, b, x);
incremento_for_1:
    x++;
    goto verifica_for_1;
fim_for_1:
    printf("fim [for]\n");

do ... while

The code

int x = 5;
do
{
    x--;
    printf("%d\n", x);
}
while(x>0);
printf("fim do{...}while(...)\n");

can be represented as:

inicio_dowhile_1:
    int x=5;
corpo_dowhile_1:
    x--;
    printf("%d\n", x);
verifica_dowhile_1:
    if(x>0)
        goto corpo_dowhile_1;
fim_dowhile_1:
    printf("fim do{...}while(...)\n");

Function call

C requires the main function, where the program starts. Other functions can be encoded within this, and arguments can be declared as local variables. You will be emulating a function call and parameter passing:

int func1(int x, int y)
{
    return x*y;
}

int main(void)
{
    int r = func1(4,5);
    printf("%d", r);
}

It can be represented like this:

int main(void)
{
    //espaço para declarar todas variáveis necessárias
    int func1_argx;
    int func1_argy;
    int func1_resultado;
    int r;

    //equivalente a chamar função:
        func1_argx = 4; //define primeiro argumento
        func1_argy = 5; //define segundo argumento
        goto func1_interna; //~chama função~
    ponto_retorno:  //nomeia ponto de retorno

    //resto do código da main
        r = func1_resultado;
        printf("%d", r);

    goto main_final; //vai para o final do main, ignorando código da função

    //parte reservada para função:
    func1_interna:
        func1_resultado = func1_argx*func1_argy;
        goto ponto_retorno;

    main_final: ;
}

In addition to replacing flow controllers, you can make a code as complex and confusing as you like, giving rise to what is called spaghetti code , but I do not think your teacher is looking for something like this ...

This answer has didactic purposes, try to understand the equivalence of constructions =)

Maybe your course will go to low-level languages later ... At the hardware level the execution controls are implemented by tests on registers and jumps, something directly related to if s and goto s.     

18.04.2017 / 20:10