Ordenação recursiva de Vetor em c++

[lucasoad399]

Pessoal, estou há mais de 6h tentando fazer esse exercício, mas por algum motivo o código não compila. Sei que o algoritmo de ordenação está correto, mas a parte que a função chama a si mesma dá algum problema e por algum motivo não volta para main(), talvez caindo num loop/recursão infinito(a);

 

Basicamente, é um exercício de Deitel, em que devo ordenar um array recursivamente. Devo pegar o menor e por no array[0], depois avaliar e por e segundo menor no array[1], até o limite do array. Segue o código do que consegui fazer até agora:

 

#include <iostream>

using namespace std;


void selectionSort(int vetor[], int limite, int comeco=0)
{
    int menor=vetor[comeco];
    int aux, pos;


    for(int i=comeco; i<limite;i++)
    {
        if(menor>vetor[i])
        {
            menor=vetor[i];
            pos=i;

        }


    }

    aux=vetor[comeco];
    vetor[comeco]=menor;
    vetor[pos]=aux;

    comeco++;

    if(comeco<limite-1)
    selectionSort(vetor, limite, comeco);




}

                        
int main()
{
    int array1[8]={100,3,25, 103,104, 200,1,64};

    selectionSort(array1, 8);

    cout<<"ARRAYS ORDENADOS:\n";


    for(int i=0;i<8;i++)
        cout<<array1[i]<<"  ";
    cout<<endl;





    return 0;
}

Por favor, se alguém puder ajudar, faz diferença, porque já estou me sentindo burro. kkkk.

[Carlos Zanon]

Quando você passa o vetor, sem informar que ele é um ponteiro (diretamente) ele vai tratar este vetor como uma variável de escopo local e não como endereço de memória que você passou anteriormente. Você precisa trata-lo como ponteiro dentro da sua função de ordenação.

 

Ele ordena apenas dentro da função e quando sua execução termina, continua da mesma forma.

 

Estude sobre ponteiros, se não, vai continuar cometendo os mesmos erros...

 

Muda:

1 hora atrás, lucasoad399 disse:

void selectionSort(int vetor[], int limite, int comeco=0)

 

Para:

1 hora atrás, lucasoad399 disse:

void selectionSort(int *vetor, int limite, int comeco=0)

 

Mude:

1 hora atrás, lucasoad399 disse:

int menor=vetor[comeco];

 

Para:

1 hora atrás, lucasoad399 disse:

int menor=*(vetor+comeco);

 

 

Faça as adaptações necessárias, nas comparações e nas definições dos valores...

 

1 hora atrás, lucasoad399 disse:

aux=*(vetor+comeco);

*(vetor+comeco)=menor;

*(vetor+pos)=aux;

 

Depois diga se deu certo :v

[lucasoad399]

@Carlos Zanon Esse é um do últimos exercícios do livro de Deitel antes de chegar em ponteiro. Então, creio que devo resolver isso sem ponteiro. Mas de qualquer forma, sei que as funções passam arrays por referência (sei que o conceito se assemelha ao vetor), de modo que consigo ordenar o primeiro ponto se tirar o if (comeco<limite-1), mas não consigo implementar a recursão.

adicionado 12 minutos depois

Fiz uma pequena alteração e pelo menos agora tá voltando pra main, só que um dos números se repete quando ordeno

 

#include <iostream>

using namespace std;


void selectionSort(int vetor[], int limite, int comeco=0)
{
    int menor=vetor[comeco];
    int aux, pos;


    for(int i=comeco; i<limite;i++)
    {
        if(menor>vetor[i])
        {
            menor=vetor[i];
            pos=i;

        }


    }

    aux=vetor[comeco];
    vetor[comeco]=menor;
    vetor[pos]=aux;

    comeco++;

    if(comeco<limite-1)
    {
        selectionSort(vetor, limite, comeco);
    }


}



int main()
{
    int limite=8;
    int array1[limite]={100,3,25, 103,104, 200,7,64};

    selectionSort(array1, limite);

    cout<<"ARRAYS ORDENADOS:\n";


    for(int i=0;i<8;i++)
        cout<<array1[i]<<"  ";
    cout<<endl;





    return 0;
}

 

[Carlos Zanon]

Tenta por um "break;" dentro do laço ali dentro do if...

Não é que ele volta, é que como o laço continua sua execução ao encontrar um número maior que ele, ele não faz a troca, só faz a troca quando encontra o ultimo número maior que ele, podendo fazer com que ele não seja ordenado corretamente... podendo manter o número menor no começo :v

 

        if(menor>vetor[i])
        {
            menor=vetor[i];
            pos=i;

            break;

        }

[lucasoad399]

Não funcionou.

[Carlos Zanon]

13 horas atrás, lucasoad399 disse:

Não funcionou.

 

Se eu te falar que rodei teu código aqui e o erro é extremamente besta...

A Variável 'pos' sua, não estava inicializada para quando você fazia a mudança de valores sem que o laço encontra-se um valor para ela... dai crash...

 

Mudei o for, porque se você já tem a posição inicial, não precisa testa-la novamente... e também aquele if no fim com limite-1, o -1 não precisa, só se você usar <=

 

Muda aqui:

17 horas atrás, lucasoad399 disse:

int aux, pos;

 

Para:

17 horas atrás, lucasoad399 disse:

int aux, pos = comeco;

 

Aqui:

17 horas atrás, lucasoad399 disse:

    for(i=comeco; i<limite;i++)

 

Para:

17 horas atrás, lucasoad399 disse:

    for(i=comeco + 1; i<limite;i++)

 

 

E Aqui:

17 horas atrás, lucasoad399 disse:

    if(comeco<limite-1)

 

Para:

17 horas atrás, lucasoad399 disse:

    if(comeco<limite)

 

 

Eu fiz um algoritmozinho pro selectionSort também, só vi que era o selection quando dei mais atenção :x

Se você quiser visualizar o que eu fiz, segue aqui no tópico:

 

Eu fiz em C esse, costume de de fazer assim :v

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

void selectionSort(int[], int, int);

int main()
{
	int vetor[8] = {100,3,25, 103,104, 200,1,64};
	int i;
	
	selectionSort(vetor, 0, 8);
	
	for(i = 0; i < 8; i++)
	{
		printf("%d\n", vetor[i]);
	}
	
	printf("\n\nFinalizada a ordenacao...\n\n");
	return 0;
}

void selectionSort(int vetor[], int inicio, int fim)
{
	int valorMin, valorIndex;
	int aux, i;

	// Se já atingiu o limite máximo de execução
	// Então para a recursão.
	if(inicio >= fim)
		return;

	// O Indice inicial é o parametro
	// inicial de comparação para fazer a troca
	valorMin = vetor[inicio];
	valorIndex = inicio;

	// Varre a partir do próximo item, pois não é
	// necessário testar o mesmo item considerando que ele é
	// menor até o momento.
	for(i = inicio + 1; i < fim; i++)
	{
		// valor para a posição atual com i
		int valor = vetor[i];

		if(valor < valorMin)
		{
			valorMin = valor;
			valorIndex = i;
		}
	}

	if(valorIndex != inicio)
	{
		aux = vetor[inicio];
		vetor[inicio] = valorMin;
		vetor[valorIndex] = aux;
	}

	selectionSort(vetor, inicio + 1, fim);
}

 

 

 

 

[lucasoad399]

Valeu, man. Vou testar. Posso te adicionar no whatsapp, man? 73-991325558