Algoritmo de Selection Sort para strings

[Patrícia Chaves]

Estou a tentar fazer o algoritmo de Selection Sort para ordenar vectores do tipo string. O código que implementei é o seguinte:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define D 3
void OrdenacaoSeleccao(const char V[], int N)
{
int passo, i;
char aux[100];  
for(passo = 0; passo < N-1; passo++)
{  

 for(i = passo + 1; i < N; i++)
 {  
  if(strcmp(&V[passo],&V[i])>0)
  {	
strcmp(aux,&V[passo]);  
strcmp(&V[passo], &V[i]);  
strcmp(&V[i], aux);  
  }  
 }	
}
}

int main()
{
char vetor[D];
int i;
printf("Introduza algumas strings no vetor!!!\n");
for(i=0;i<D;i++)
{
 printf("String %d: ", i+1);
 scanf("%s", &vetor[i]);
}

OrdenacaoSeleccao(vetor,D);
for(i=0;i<D;i++)
{
 printf("String: %s", vetor[i] );
}
system("pause");
return 0;
}

Só está a dar erro quando tento imprimir no ecrã o vector ordenado!!!

Alguém me pode ajudar?

Edited May 23, 2012 at 10:18 AM by softklin
Adicionado GeSHi

[HappyHippyHippo]

o algoritmo está mal implementado

- para os elementos do array do indice (i = 1 a N-1)
 - j = i
 - enquanto j != 0 e array[j-1] > array[j]
- troca array[j] por array[j-1]
- j = j-1

tu tens

- para os elementos do array do indice (i = 0 a N-2)
 - j = i+1
 - para todos os elementos de j até N-1
  ...

PS : epa .. os espaços da indentação foram para o caneco ... vou por dentro das tags code

Edited May 22, 2012 at 05:06 PM by HappyHippyHippo

[Patrícia Chaves]

Seria possível traduzir isso para código? não estou a conseguir perceber. o código tem uma coisa mal que me enganei por distracção, deve ser assim:

void OrdenacaoSeleccao(char V[], int N)
{ 
int passo, i; 
char aux[100];  
for(passo = 0; passo < N-1; passo++)
{  

 for(i = passo + 1; i < N; i++)
 {   
  if(strcmp(&V[passo],&V[i])>0)
  {	
   strcpy(aux,&V[passo]);   
   strcpy(&V[passo], &V[i]);   
   strcpy(&V[i], aux);  
  }  
 }	
}
}

[pmg]

As implementacoes colocadas aqui nao sao para o selection sort. No algoritmo selection sort, o que se faz e trocar o elemento mais pequeno do array com o primeiro elemento; o mais pequeno do "array que sobra" com o primeiro elemento do "array que sobra" e assim sucessivamente.

As implementacoes aqui apresentadas parecem ser do bubble sort.

Outra coisa no que respeita ao codigo orignal da Patricia: um objecto declarado com

char vetor[3];

pode conter 3 caracteres ou uma string com comprimento maximo 2.

[Patrícia Chaves]

pmg eu estou a implementar o selection sort e não o bubble sort.

obrigado pela dica do vector isso já modifiquei.

[pmg]

pmg eu estou a implementar o selection sort e não o bubble sort.

A mim parece-me mais o insertion sort (enganei-me quando disse bubble sort).

Repara que no selection sort, so se faz uma troca de elementos por cada nivel exterior dos loops; tu tens a troca de V[ passo ] com V[ i ] dentro do loop interior.

Edit: descobri uma pagina com comparacoes de diferentes algoritmos que me parece interssante 🙂

Edited May 22, 2012 at 06:03 PM by pmg

[HappyHippyHippo]

As implementacoes aqui apresentadas parecem ser do bubble sort.

ups ... deve ser do calor 😄 nem pensei no que estava a dizer 😄

- para os elementos do array do indice (i = 1 a N-1)
 - min = i - 1;
 - para os elementos do array do indice (j = i a N-1)
   - se array[j] < array[min]
     - min = j
 - se min != i
   - trocar array[i] por array[min]

[Patrícia Chaves]

A mim parece-me mais o insertion sort (enganei-me quando disse bubble sort).

Repara que no selection sort, so se faz uma troca de elementos por cada nivel exterior dos loops; tu tens a troca de V[ passo ] com V[ i ] dentro do loop interior.

Edit: descobri uma pagina com comparacoes de diferentes algoritmos que me parece interssante 🙂

Ah sim nisso tens razão está dentro do ciclo, mas não é por isso que dava mal 😞