Sign in to follow this  
icoN

Quicksort - Help Urgente

Recommended Posts

O pessoal, to tentando implementar o quicksort. Montei esse algoritmo aqui mas está dando um pequeno erro na hora de ordenar, alguns ele está deixando errado e tal.. Algm pode da uma mao?

Valeu! (Pus umas flags sinalizadoras e vi que ele não está entrando no segundo laço, mas n sei porque!)

void QSort (int vet[], int ini, int fim)

     {int i=ini;
      int f=fim;  
      int pivo = vet[ini];
      int esq=1;
      int aux;
      
if (fim  > ini)

{      
        printf ("Fim > Ini! Pivo vale %i\nO vetor é: \n", pivo);
        for (aux=ini; aux<fim+1; aux++)
            printf (" %i ",vet[aux]);
            getch();
        

        
           do    {
                   
                                    
                   
                       if (vet[f]<pivo)
                           { 
                             printf ("Pivo na esquerda. Trocando %i com %i\n Novo vetor é\n", vet[i], vet[f]);
                             esq=0;
                             aux=vet[f];
                             vet[f]=vet[i];
                             vet[i]=aux;
                             
                             i++;
                             for (aux=ini; aux<fim+1; aux++)
                                 printf (" %i ",vet[aux]);
                             getch();
                            }
                         else
                            { printf ("Sem troca! Decrementa fim!\n");
                             getch();
                             f--; }
                        
                    else      
                    if (esq=0)
                    
                     
                        if (vet[i]>=pivo)
                            { printf ("Pivo na direita. Trocando %i com %i \n Novo vetor é \n", vet[i], vet[f]);
                            
                              aux=vet[i];
                              vet[i]=vet[f];
                              vet[f]=aux;
                              f--;
                              esq=1;
                              for (aux=ini; aux<fim+1; aux++)
                                printf (" %i ",vet[aux]);
                            getch();
                              }
                         else 
                            { printf ("Sem troca! Incrementa ini!\n");
                              getch();
                              i++; }
                              
                             
                                      
               }  while (i < f);
               
               
          
               
               
           QSort (vet, ini, i-1);
           QSort (vet, i+1, fim);
   
   }   
   
  }   /*end da função */
Sério pessoal, to precisando muito de ajuda! Esse problema ai eu simplesmente não consigo ver a solução :/ Dei uma limpada no codigo, pra quem prefere ver sem flags e tal.
void QSort (int vet[], int ini, int fim)

{     int i=ini;
      int f=fim;  
      int pivo = vet[ini];
      int esq;
      int aux;
      
      esq=1;
     
      
if (fim  > ini)

{      
       

        
           while (i < f) 
           
             { 
               
               if (esq=1)  
                  {
                    if (vet[f]<pivo)
                        { aux=vet[f];
                          vet[f]=vet[i];
                          vet[i]=aux;
                          esq=100;
                          i=i+1;
                         }
                     else      
                        f=f-1;
                        }
                           
               else                 
                    {
                    
                    if (pivo<vet[i])
                       {  aux=vet[f];
                          vet[f]=vet[i];
                          vet[i]=aux;
                          esq=1;
                          f=f-1;
                       }
                   else 
                      i=i+1;
                      
                      }                            
                   
               }                     
                             
                                      
                 
               
               
          
               
               
           QSort (vet, ini, i-1);
           QSort (vet, i+1, fim);
   
   }   
   
  }

Valeu ai!

Share this post


Link to post
Share on other sites

if (esq=1)

Não deveria ser if(esq==1) ?

Duas dicas, primeiro use getchar que é padrão ansi, depois tente compilar seus programans no gcc

com gcc -Wall -ansi -pedantic qsort.c -o qsort.exe (se estiver no Linux não precisa de .exe =) )

o compilador irá te informar de possiveis erros no seu código.

A linguagem permite if(esq=1), mas este é um valor sempre true e que altera a sua variável.

Share this post


Link to post
Share on other sites

Poxa velho, valeu ai! Funcionou mesmo! Nem tinha reparado direito que faltava o igual ali, tava mais preocupado em ver a sistemática de funcionamento do ordenamento e não reparei naquilo :D Valeu ai!

Share this post


Link to post
Share on other sites

Certo, vou dar uma olhada sim. Existe uma função QuickSort na linguagem C++ que realiza a ordenação pelo quicksort. Sabe qual a sintaxe dela? E qual a biblioteca? É para um trabalho de análise das diferentes implementações do algoritmo... Valeu ai!

Share this post


Link to post
Share on other sites

a funcao se chama qsort e é da stdlib.h

Ela possui o seguinte prototipo:

void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))

base é o vetor que voce quer ordenar

nmemb é o numero de elementos no vetor

size é o sizeof do tipo do vetor

compar é uma funcao de comparacao que devolve 0 se forem iguais, < 0 se o primeiro é maior que o segundo e >0 caso contrario.

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this