Recursividade em SelectSort e InsertSort sem repetição

[Alessandra Alves]

Bom dia! Eu sou nova nesse fórum e preciso (desesperadamente) da ajuda de vocês. Eu estou começando a programar e ando tendo problemas. Essa semana eu comecei a programar em C++ e nosso professor nos passou um trabalho que eu não consegui fazer. O tópico é esse:

1) Implementar recursivamente em C ou C++ (não empregar repetição - decompor o problema)

a ) O método da seleção

b ) O método da inserção

Alguém aí pode me ajudar, por favor???

Obrigada,

Alessandra.

[goldbach]

Isso pode ajudar:

Selection

Insertion

Editado Janeiro 6, 2013 por goldbach

[Alessandra Alves]

Isso pode ajudar:

Selection

Insertion

Obrigada, goldbach. Mas esses códigos tem repetição :( O professor disse que eu não posso usar nenhum for.

[goldbach]

Bom ... não entende o porquê de restringir a instrução for, mas você pode substituir a instrução com o truque abaixo:

#include <stdio.h>

void method1()
{
    int i;

    for(i = 0; i < 10; i++)
    {
        printf("A");
    }
}

void method2()
{
    int i = 1;

repeat:
    printf("A");
    
    if(i++ < 10) goto repeat;
    else return;
}

int main()
{
    method1();
    printf("\n");
    method2();
}

A função method2() faz a mesma coisa que a função method1(), porém sem usar a instrução for.Boa Sorte.

[Alessandra Alves]

Bom ... não entende o porquê de restringir a instrução for, mas você pode substituir a instrução com o truque abaixo:

#include <stdio.h>

void method1()
{
    int i;

    for(i = 0; i < 10; i++)
    {
        printf("A");
    }
}

void method2()
{
    int i = 1;

repeat:
    printf("A");
    
    if(i++ < 10) goto repeat;
    else return;
}

int main()
{
    method1();
    printf("\n");
    method2();
}

A função method2() faz a mesma coisa que a função method1(), porém sem usar a instrução for.Boa Sorte.

Eu não entendi como esse código funciona :( Será que você poderia me explicar? Por favor...

[goldbach]

Vou tentar te explicar ... Você disse que seu professor restringiu o uso da instrução for, o que eu quis te mostrar é como substituir essa instrução.Vou explicar o que eu fiz com a função method1():

.Localizei a instrução for.

.Substitui a instrução for por um rótulo.

.Coloquei o código que ira se repetir "dentro" do rótulo.

.Usei a instrução goto para repetir este "bloco" de código.

.Inicializei as variaveis necessárias antes da declaração do rótulo.

.Coloquei o código que encerra o ciclo no final do rótulo.

Para que você entenda melhor, eu implementei duas funções: selectionSort() e selectionSort1(),as duas são recursivas e somente a primeira faz uso da instrução for, contudo ambas conseguem ordenar um vetor de inteiros.

#include <stdio.h>

void selectionSort(int *input, int length, int startIndex)
{
    if(startIndex >= length - 1) return;
    
    int minIndex = startIndex;
    
    for(int index = startIndex + 1; index < length; index++)
    {
        if (input[index] < input[minIndex])
        {
            minIndex = index;
        }
    }
    
    int temp = input[startIndex];
    input[startIndex] = input[minIndex];
    input[minIndex] = temp;
    
    selectionSort(input, length, startIndex + 1);
}

void selectionSort1(int *input, int length, int startIndex)
{
    if(startIndex >= length - 1) return;
    
    int minIndex = startIndex;
    
// start loop for
    
    int index = startIndex + 1;

repeat:
    if (input[index] < input[minIndex])
    {
        minIndex = index;
    }
    
    if(++index < length) goto repeat;

// end loop for

    int temp = input[startIndex];
    input[startIndex] = input[minIndex];
    input[minIndex] = temp;
    
    selectionSort(input, length, startIndex + 1);
}



int main()
{
    int input[]  = {9, 3, 4, 2, 7, 5, 1, 6, 0, 8};
    int input1[] = {9, 3, 4, 2, 7, 5, 1, 6, 0, 8};

    selectionSort(input, 10, 0);
    printf("{%d, %d, %d, %d, %d, %d, %d, %d, %d, %d}\n", input[0], input[1], input[2], input[3],
         input[4], input[5], input[6], input[7], input[8], input[9]);

    selectionSort1(input1, 10, 0);
    printf("{%d, %d, %d, %d, %d, %d, %d, %d, %d, %d}", input1[0], input1[1], input1[2], input1[3],
         input1[4], input1[5], input1[6], input1[7], input1[8], input1[9]);

    return 0;
}

[Alessandra Alves]

Vou tentar te explicar ... Você disse que seu professor restringiu o uso da instrução for, o que eu quis te mostrar é como substituir essa instrução.Vou explicar o que eu fiz com a função method1():

.Localizei a instrução for.

.Substitui a instrução for por um rótulo.

.Coloquei o código que ira se repetir "dentro" do rótulo.

.Usei a instrução goto para repetir este "bloco" de código.

.Inicializei as variaveis necessárias antes da declaração do rótulo.

.Coloquei o código que encerra o ciclo no final do rótulo.

Para que você entenda melhor, eu implementei duas funções: selectionSort() e selectionSort1(),as duas são recursivas e somente a primeira faz uso da instrução for, contudo ambas conseguem ordenar um vetor de inteiros.

#include <stdio.h>

void selectionSort(int *input, int length, int startIndex)
{
    if(startIndex >= length - 1) return;
    
    int minIndex = startIndex;
    
    for(int index = startIndex + 1; index < length; index++)
    {
        if (input[index] < input[minIndex])
        {
            minIndex = index;
        }
    }
    
    int temp = input[startIndex];
    input[startIndex] = input[minIndex];
    input[minIndex] = temp;
    
    selectionSort(input, length, startIndex + 1);
}

void selectionSort1(int *input, int length, int startIndex)
{
    if(startIndex >= length - 1) return;
    
    int minIndex = startIndex;
    
// start loop for
    
    int index = startIndex + 1;

repeat:
    if (input[index] < input[minIndex])
    {
        minIndex = index;
    }
    
    if(++index < length) goto repeat;

// end loop for

    int temp = input[startIndex];
    input[startIndex] = input[minIndex];
    input[minIndex] = temp;
    
    selectionSort(input, length, startIndex + 1);
}



int main()
{
    int input[]  = {9, 3, 4, 2, 7, 5, 1, 6, 0, 8};
    int input1[] = {9, 3, 4, 2, 7, 5, 1, 6, 0, 8};

    selectionSort(input, 10, 0);
    printf("{%d, %d, %d, %d, %d, %d, %d, %d, %d, %d}\n", input[0], input[1], input[2], input[3],
         input[4], input[5], input[6], input[7], input[8], input[9]);

    selectionSort1(input1, 10, 0);
    printf("{%d, %d, %d, %d, %d, %d, %d, %d, %d, %d}", input1[0], input1[1], input1[2], input1[3],
         input1[4], input1[5], input1[6], input1[7], input1[8], input1[9]);

    return 0;
}

Agora eu entedi! Muitíssimo obrigada!