Selection Sort C

[Guest IceE_90]

Boa tarde antes de mais..

É o seguinte eu sou aida um verdadeiro amador em C, e aventurei me já a tentar fazer o codigo em C, o meu trabalho que estou a elaborar é o Selection Sort Algorithm decerta forma o meu codigo nao está a funcionar, queria que ele ordena-se os números por ordem crescente, os que o utilizador inseri-se, e mostra-se no ecrâ passo a passo por ordem, só que.. nada disso acontece !!

Será que podiam me ajudar ? :X

#include <stdio.h>
#include <stdlib.h>
void SelectionSort (int array_size = 3, int a[array_size]) {
system("color 3d");
int num_user;
for (num_user = 0; num_user < array_size - 1; ++num_user) {
  int next_num, min, temp;
  min = num_user;
  for (next_num = num_user+1; next_num < array_size; ++next_num) {
   if (a[next_num] < a[min])
    min = next_num;
  }
  temp = a[num_user];
  a[num_user] = a[min];
  a[min] = temp;
}
}

[renafi]

Não te falta ai o método Main? E dava jeito ler os dados do utilizador e depois colocar no ecra o resultado final. Como é que fizeste este código?

[Guest IceE_90]

Pois é isso, eu fiz isso em conjunto, e falta esse pequenos pormenores, e agora nao sei onde os colocar :X

[Localhost]

IceE_90, não percebi muito bem o teu código mas fiz aqui um rapidamente que te pode ajudar, acho eu... É assim, no meu código eu só testei com 2 elementos no array mas tu podes testar com mais e podes inclusive adaptar às tuas necessidades. Atenção o meu código não é nada de especial nem nada eficiente! Não estejas à espera de fazer grande coisa com ele...

Sem mais demoras aqui vai o code:

#include <stdio.h>

void sort()
{
   int array[2] = {2,1};
   printf("Qual é o numero de elementos? ");
   int num;
   scanf("%d", &num);
   int i;
   for(i=0; i<num-1; i++)
   {
      int next;
      next = array[i+1];
      if(next < array[i])
      {
         int temp;
         temp = array[i];
         array[i] = next;
         array[i+1] = temp;
      }
   }
   for(i=0;i<num; i++)
   {
      printf("%d\n",array[i]); 
   }
}

int main()
{
   sort();
   return 0;
}

[Guest IceE_90]

Txiii, bem só esse pequeno código deu me um sorriso na boca, mas pa ser mais explicito o que queria e gostava de saber fazer era o utilizador colocava os números ou seja (scanf), e de seguida o programa iria ordenar os números do user, passo a passo, de um a um, pela sequência crescente, desde o número mais pequeno que o utilizador escolheu para o maior.

Por exemplo isto

Nºs do utilizador: 5 7 3 9 2 1

--> 1 5 7 3 9 2

--> 1 2 5 7 3 9

--> 1 2 3 5 7 9

--> 1 2 3 5 7 9

--> 1 2 3 5 7 9

--> 1 2 3 5 7 9

[Localhost]

Eu percebi o que tu querias dizer mas como eu disse o meu code é ineficiente, eu vou então tentar fazer aqui uma coisa porreira para ti (:

EDIT: A verdade é que se tentares pôr o meu code dentro de um laço ainda maior ele vai conseguir pôr-te tudo em ordem pois vai estar a ordenar tantas vezes que vai acabar por ordená-lo, no entanto é muito lento dessa maneira!

[pedrosorio]

Eu percebi o que tu querias dizer mas como eu disse o meu code é ineficiente, eu vou então tentar fazer aqui uma coisa porreira para ti (:

EDIT: A verdade é que se tentares pôr o meu code dentro de um laço ainda maior ele vai conseguir pôr-te tudo em ordem pois vai estar a ordenar tantas vezes que vai acabar por ordená-lo, no entanto é muito lento dessa maneira!

Atenção. É importante perceber o problema com que estamos a lidar antes de tentar ajudar. Aquilo que tu implementaste não é um selection sort. Um selection sort procura o mínimo da lista e coloca-o na primeira posição, e repete esta operação para o resto da lista (i.e. excepto o primeiro elemento da actual) até chegar ao fim.

http://en.wikipedia.org/wiki/Selection_sort

[Localhost]

Vou então colocar aqui o meu code altamente lento mas competente na sua tarefa, o que ele faz é o mesmo que o outro mas vai fazê-lo 100 vezes, ou seja vai organizá-lo tantas vezes que o organiza xD

O que o meu outro fazia era ver se o elemento em que estava era maior que o próximo e se fosse trocava-os, o que acabava por acontecer era que se o ultimo fosse menor que o primeiro nao era ordenado, mas vê agora os resultados ...

#include <stdio.h>

void sort()
{
   int array[10]={10,5,4,3,2,1,40,30,70,21};
   printf("Qual é o numero de elementos? ");
   int num;
   scanf("%d", &num);
   int i,j=0;
   while(j<100)
   {
      for(i=0; i<num-1; i++)
      {
         int next;
         next = array[i+1];
         if(next < array[i])
         {
          int temp;
          temp = array[i];
          array[i] = next;
          array[i+1] = temp;
         }
       j++;
      }
   }
   for(i=0;i<num; i++)
   {
     printf("%d\n",array[i]);
   }
}

int main()
{
   sort();
   return 0;
}

Se quiseres uma coisa mais eficiente tenta adaptar a alguma coisa que queiras. Procura também por quick sort e tenta perceber o código. Só mais uma coisa, não tentes reinventar a roda porque não vais conseguir nada mais rápido que aqueles mais conhecidos, no entanto é sempre bom ver estas iniciativas aqui no forúm (:

p.s. Bem vindo à comunidade  😕

[pedrosorio]

Isso continua a não ser um algoritmo de ordenação. Funcionará para todos os arrays com menos de 102 posições, mas não é um algoritmo de ordenação que funcione em geral.

Ele não está a tentar reinventar a roda, está a tentar implementar o selection sort.

[Localhost]

Ok, eu não vi essa parte do selection sort, pensei que ele só queria um algoritmo que ordenasse um array. Hoje está-me tudo a correr mal  ?

Desculpa lá (:

[Guest IceE_90]

Obrigado pelas dicas, vou treinar aqui um pouco, para ver se tambem adapto algumas coisinhas para aperfeiçoar, no entanto é normal acontecer isto no inicio, ainda tou muito a lés do que é o C.

Se bem que o codigo nao é "o tal" , ha que fazer mais proccuras da minha parte 😕

E obrigado pelas boas vindas 🙂

[Localhost]

Pá o mais importante desse sort é encontrar o menor pela primeira vez depois de o teres tens tudo feito. Agora que me falaram nisto estou a pensar numa maneira xD

[Guest IceE_90]

loool, pois realmente...

[Localhost]

pedrosorio, podias-me ver isto e dar uma ajuda?

#include <stdio.h>

void solve()
{
   int array[2] = {2,1};
   int min;
   int i;
   printf("Elementos: ");
   int num;
   scanf("%d", &num);
   for(i=0; i<num; i++)
   {
      min = array[0];
      int t;
      for(t=0; t<num; t++)
      {
         if(array[t] < array[min])
         {
            int j;
            for(j=t;t<num;t++)
            {
               if(array[j] < array[t])
               {
                  array[i] = array[j];
               }
            }
         }
      }
   }
   for(i=0;i<num;i++)
   {
      printf("%d\n", array[i]);
   }
}

int main(void)
{
   solve();
   return(0);
}

[pedrosorio]

O pseudo-código terá que ser algo deste género:

para i=0 até n
      achar mínimo do array entre i e n
      trocar mínimo com o elemento na posição i
      print do array todo
fim

Ou seja, começar com o array todo (i=0), achar o mínimo, colocá-lo na posição inicial e fazer print. Em seguida considerar o array todo a partir da 2ª posição (i=1), achar o mínimo, colocá-lo na posição i=1 e fazer print do array completo, etc. até à posição n. Na realidade a última iteração é inútil porque quando chegamos à posição n o array está todo ordenado.

Para simplificar as coisas experimenta fazer aqueles processos descritos no pseudo-código em funções separadas. Algo deste estilo:

int achar_minimo(int *array, int i, int n) {
//codigo para achar a posicao do minimo do array entre a posicao i e n
}

void trocar_minimo(int *array, int i, int min) {
//codigo para trocar os elementos na posicao i e na posicao min
}
void print_array(int *array, int n) {
//codigo para fazer print dos elementos do array
}

void selection_sort(int *array, int n) {
   int i,min;
   for(i=0; i<n; i++) {
      min = achar_minimo(array,i,n);
      trocar_minimo(array,i,min);
      print_array(array,n);
   }
}

int main(void) {
   int ordenar[6] = {2, 6, 1, 10, 3, 5};
   selection_sort(ordenar,6);
   return 0;
}

[Localhost]

O pseudo código já eu tinha percebido... Só não percebo é como é que vou achar o elemento mais pequeno do array...

[pedrosorio]

O pseudo código já eu tinha percebido... Só não percebo é como é que vou achar o elemento mais pequeno do array...

Por isso é que coloquei numa função à parte para te concentrares apenas nisso e não teres interferências com o resto do código.

[Localhost]

Ok, vou ver.

[Localhost]

É isto?

#include <stdio.h>

int solve(){
   int array[6] = {70,60,50,40,30,20};
   int cont;
   int num = 6;
   int min2;
   int swap;
   for(cont = 0; cont<num; cont++){
      int min=cont+1;
      for(min2=min; min2<num; min2++){
         if(array[min2] < array[min]){
             swap = array[cont];
             array[cont] = array[min2];
             array[min2] = swap;
         }   
      }
   }
   for(cont=0;cont<num;cont++){
      printf("%d\n", array[cont]);
   }
   return(0);
}

int main(void){
   solve();
   return(0);
}

[pedrosorio]

É isto?

#include <stdio.h>

int solve(){
   int array[6] = {70,60,50,40,30,20};
   int cont;
   int num = 6;
   int min2;
   int swap;
   for(cont = 0; cont<num; cont++){
      int min=cont+1;
      for(min2=min; min2<num; min2++){
         if(array[min2] < array[min]){
             swap = array[cont];
             array[cont] = array[min2];
             array[min2] = swap;
         }   
      }
   }
   for(cont=0;cont<num;cont++){
      printf("%d\n", array[cont]);
   }
   return(0);
}

int main(void){
   solve();
   return(0);
}

Isso é uma reedição do primeiro código que colocaste neste tópico e que nada tem a ver com o selection sort. Pelos vistos não percebeste bem o pseudo-código.