[Resolvido] Algoritmo de ordenar vector

[Guest skinie18]

Boas, a situação é eu tenho 1 variável e 2 vectores:

short n_elem = 5;
int vec1[n_elem];
int vec2[n_elem];

O primeiro esta cheio de numero ao acaso:

vec1[0] = 9;
vec1[1] = 1;
vec1[2] = 6;
vec1[3] = 3;
vec1[4] = 10;

Ou seja no indice 0 o conteúdo é 9, no índice 1 o conteúdo é 1,...

O meu objectivo é passar para o vec2[] os incides do vec1[] ordenados de forma crescente sem alterar nunca o vec1.

Exemplo:

vec1 -> 9, 1, 6, 3, 10

vec2 -> 1, 3, 2, 0, 4

Nota: É claro que este problema se resolvia muito facilmente com um terceiro vector temporário, mas o meu objectivo é fazer um algoritmo eficiente que nao use muitas variáveis para o processo.

A minha pergunta é: Qual o melhor algoritmo para resolver este problema? Gostava que me ajudassem com algumas palavras de como vossês resolviam o problema.

Edited October 4, 2012 at 07:00 PM by Guest

[pmg]

Implementa um quick sort (ou outro algoritmo de ordenação) sobre um array de indices.

vec1 -> 9, 1, 6, 3, 10

vec2 -> 0, 1, 2, 3, 4

ordena o vec2, mas compara os valores vec1[vec2].

[HappyHippyHippo]

para este problema, como o número de elementos é bem pequeno, qualquer algoritmo fará o que pretendes bem rápido.

tenta um grande número (de algoritmos) que assim sempre vais praticando.

Edited October 4, 2012 at 07:19 PM by HappyHippyHippo

[Guest skinie18]

Boas, já consegui fazer um algoritmo da forma como queria. Obrigado pela ajuda pmg.

Inicializei o vec2 aos indices do vec 2, ex:.

vec1 -> A,B,C,D,E

vec2 -> 0,1, 2, 3,4

Depois para fazer as comparações fiz:

if(vec1[vec2[i]] > vec1[vec2[i+1]])

E ia fazendo as substituições dos índices nas vec2.

Obrigado pelas ajudas 😉

Edited October 4, 2012 at 06:59 PM by skinie18

[pmg]

Pois, é isso mesmo.

Queres meter aqui o teu codigo?

Pode ser que alguem tenha sugestoes de alteracao ...

[Guest skinie18]

Para já é melhor nao. Porque este é o trabalho que é suposto ser entregue na Faculdade. E há vários alunos que estão a tentar resolver este problema(de várias maneiras), as soluções são para ser apresentadas na próxima semana. Eu ja vi algumas resoluções para este problema mas a maior parte implica fazer 3 ou 4 for's usar arrays auxiliares ou inicializar variáveis a um numero tipo 999999999 e etc... Como eu nao achei que nenhuma dessas soluções era boa ou correcta do ponto de vista da eficiência eu fiz a pergunta aqui no Portugal a programar onde principalmente o teu comentário me deixou a pensar e me levou a minha conclusão final. Espero entao que os colegas que estão a resolver o mesmo problema atinjam as mesmas conclusões que eu, ou melhores! 😉

Nota: Como é obvio o P@P é conhecido entre os meus colegas programadores e nao quero chapar o codigo aqui e eles nao terem o trabalho de raciocinar ate chegar a solução. (É como ver um filme que já se conhece o fim... Nao tem piada...)

Edited October 4, 2012 at 09:02 PM by skinie18

[pmg]

Ok, tens uma boa razao para manter o teu codigo privado.

Como é obvio, depois dos trabalhos de todos os colegas terem sido entregues e avaliados, podes sempre rever o topico e publicar o teu codigo nessa altura para mais comentarios / sugestoes / criticas.

Happy Coding!

[Guest skinie18]

Fica ai o código que eu fiz:

#include <stdio.h>
int main(int argc, const char * argv[]) {
   short n_elem = 5; // Numero de elementos do array
   short i = 0; // Variavel temporaria de for

   int vec[n_elem]; // Array Principal
   int newVec[n_elem]; // Array com indices do array principal ordenados por ordem crescente

   /* -- Ler os 5 elementos -- */
   do{
    printf("Insira o elemento %d do array: ", (i+1));
    scanf("%d", &vec[i]);
    fflush(stdin);
    i++;
   }while(i != n_elem);

   /* -- Inicializar newVec aos indices por ordem -- */
   for (i=0; i<n_elem; i++) {
    newVec[i]= i;
   }

   short flag = 1; // flag que conta quantas trocas o bubble sort faz

   /* -- Bubble Sort -- */
   while(flag != 0){
    flag = 0;
    for (i=0; i<(n_elem-1); i++) {
	    if(vec[newVec[i]] > vec[newVec[i+1]]){
		    int tmp = newVec[i];
		    newVec[i] = newVec[i+1];
		    newVec[i+1] = tmp;
		    flag++;
	    }
    }
   }

   /* -- Apresentar o array de indices no ecra -- */
   for (i=0; i<n_elem; i++) {
    printf("%d", newVec[i]);
   }
   printf("\n");


   return 0; //end
}

[pmg]

Nao esta nada mal.

Vou sugerir duas alteracoes:

1) faz o bubble sort uma funcao separada

2) melhora o bubble sort para nao estar a comparar elementos que ja sabes que estao na posicao final.

De cada vez que o ciclo for interior corre, o elemento mais alto restante é levado para o fim do array. Mas no ciclo seguinte vais comparar desnecessariamente este ultimo elemento com o anterior (e no terceiro ciclo vais comparar os 2 ultimos, ..., ...)

Pontos de estilo:

a) a funcao main nunca usa argc ou argv. Nao precisas de os definir (quanto menos coisas houver, menos coisas podem correr mal), ficando a funcao assim

int main(void) { /* ... */ }

b) o fflush(stdin) nao te adianta nada ao programa. Se nao o utilizares o teu programa pode correr (ou ser compilado) em implementacoes onde essa funcionalidade nao esta definida.

c) em vez de definires a veriavel temporaria de for a nivel da funcao main, podes defini-la apenas para cada ciclo

/* aqui, a variavel i nao existe */
   for (int i = 0; i < n_elem; i++) {
       /* ... aqui a variavel i existe ... */
}
/* aqui, a variavel i nao existe */

[HappyHippyHippo]

c) em vez de definires a veriavel temporaria de for a nivel da funcao main, podes defini-la apenas para cada ciclo

é preciso notar que isto não é possivel para algums compiladores ou versões de compiladores (mais antigos ou restritos), por isso fica só a nota que se der erro, pode ser disso e não da simplificação.

[pmg]

é preciso notar que isto não é possivel para algums compiladores ou versões de compiladores (mais antigos ou restritos), por isso fica só a nota que se der erro, pode ser disso e não da simplificação.

Obrigado pela chamada de atencao.

O programa original usa pelo menos 2 "novidades" do C99 (VLA e codigo misturado com declaracoes), por isso a "novidade" que eu sugeri, muito provavelmente, tambem ira funcionar 🙂