Ir ao conteúdo
  • Comunicados

    • Gabriel Torres

      Seja um moderador do Clube do Hardware!   12-02-2016

      Prezados membros do Clube do Hardware, Está aberto o processo de seleção de novos moderadores para diversos setores ou áreas do Clube do Hardware. Os requisitos são:   Pelo menos 500 posts e um ano de cadastro; Boa frequência de participação; Ser respeitoso, cordial e educado com os demais membros; Ter bom nível de português; Ter razoável conhecimento da área em que pretende atuar; Saber trabalhar em equipe (com os moderadores, coordenadores e administradores).   Os interessados deverão enviar uma mensagem privada para o usuário @Equipe Clube do Hardware com o título "Candidato a moderador". A mensagem deverá conter respostas às perguntas abaixo:   Qual o seu nome completo? Qual sua data de nascimento? Qual sua formação/profissão? Já atuou como moderador em algo outro fórum, se sim, qual? De forma sucinta, explique o porquê de querer ser moderador do fórum e conte-nos um pouco sobre você.   OBS: Não se trata de função remunerada. Todos que fazem parte do staff são voluntários.
    • DiF

      Poste seus códigos corretamente!   21-05-2016

      Prezados membros do Fórum do Clube do Hardware, O Fórum oferece um recurso chamado CODE, onde o ícone no painel do editor é  <>     O uso deste recurso é  imprescindível para uma melhor leitura, manter a organização, diferenciar de texto comum e principalmente evitar que os compiladores e IDEs acusem erro ao colar um código copiado daqui. Portanto convido-lhes para ler as instruções de como usar este recurso CODE neste tópico:  
anonymouatour

Outro Algoritmo de ordenação Quick sort

Recommended Posts

Olá amigos passei o dia todo procurando tutoriais sobre esse algoritmo mas não código e sim como ele funciona tipo o rastreio dele mas cheguei a fazer o rastreio dessa maneira

 

[5,3,2,4,6,10,9,1,7,8] dado esse vetor desordendo para ordena-lo fiz assim 10/2 = 5 a quinta posicção seria o meu pivo que no caso seria o valor 6 .

e os primeiros da esquerda 5 e da direita 8, fui fazendo a comparação com os da esquerda e todos são menores então não entendi como vou fazer agora nao estou pedindo a resposta por favor mas sim que me oriente nessa parte para eu conseguir fazer dsde já obrigado.pois se o numero 1 tivesse já ali dava pra dividir   vetor em duas partes e ia comparado o problema foi esse 

  • Curtir 1

Compartilhar este post


Link para o post
Compartilhar em outros sites

@anonymouatour       a ordenação se faz usando dois loop um dentro do outro, sendo que o segundo loop começa do valor do primeiro mais um, com isso o loop de dentro verifica todos os números com o primeiro para ver se ele é maior, se for então trocar eles de lugar, usando para isso uma variável assim :

aux = vetor[ i ];
vetor[ i ] = vetor[ j ];
vetor[ j ]= aux;

 

  • Obrigado 1

Compartilhar este post


Link para o post
Compartilhar em outros sites

Olá @anonymouatour.

 

Vou tomar como base a linguagem utilizada no Visualg ("Portugol")

 

1) ENCONTRAR O PIVÔ

 

16 horas atrás, anonymouatour disse:

[5,3,2,4,6,10,9,1,7,8] dado esse vetor desordendo para ordena-lo fiz assim 10/2 = 5 a quinta posicção seria o meu pivo que no caso seria o valor 6 .

Pelo que eu entendi, você quer encontrar a posição do meio. Logo, seria algo como:

posPivo := (posicao_inicial_do_vetor+posicao_final_do_vetor) \ 2

No caso, (1+10)\2 = 11\2 = 5. Nesse sentido, perceba que está sendo utilizado o "\" (barra deitada para esquerda), pois, se o dividendo for ímpar (como é o caso), o seu algoritmo não iria funcionar se usasse o "/". Pois 11/2 = 5.5, percebe? Não existe a posição 5.5.

 

obs.: como suposto, "\" é diferente de "/". São operadores aritméticos diferentes. É equivalente ao "div" em algumas outras linguagens. Vide referência do Visualg.

 

 

 

 

17 horas atrás, anonymouatour disse:

e os primeiros da esquerda 5 e da direita 8, fui fazendo a comparação com os da esquerda e todos são menores então não entendi como vou fazer agora

 

Simples: já estão "ordenados em relação ao pivô. Não tem problema algum... faz parte. A lógica do algoritmo é exatamente a mesma para qualquer organização dos números... o que poderia mudar seria apenas o tempo que o algoritmo iria demorar para ordená-los.

 

 

 

Adendo:

@devair1010,

12 horas atrás, devair1010 disse:

@anonymouatour       a ordenação se faz usando dois loop um dentro do outro, sendo que o segundo loop começa do valor do primeiro mais um, com isso o loop de dentro verifica todos os números com o primeiro para ver se ele é maior, se for então trocar eles de lugar, usando para isso uma variável assim :

O método de ordenação escolhido foi o Quick Sort. Acho que está usando como referência um outro, como o Bubble Sort (são lógicas diferentes).

 

 

 

No aguardo.

  • Curtir 1
  • Obrigado 1

Compartilhar este post


Link para o post
Compartilhar em outros sites
  • Autor do tópico
  • Então no caso eu precisaria fazer comparação com o lado direito ou dividir em duas partes?

    adicionado 0 minutos depois

    Visto que o lado esquerdo "está ordernado"

    adicionado 1 minuto depois

    E depois junte novamente

    adicionado 37 minutos depois

    Porque também vi que está faltando o 1 se ele tivesse ali seria mais fácil jjj

    adicionado 37 minutos depois

    No lado esquerdo jj

    • Curtir 1

    Compartilhar este post


    Link para o post
    Compartilhar em outros sites

    @anonymouatour,

     

    34 minutos atrás, anonymouatour disse:

    Então no caso eu precisaria fazer comparação com o lado direito ou dividir em duas partes?

     

    Visto que o lado esquerdo "está ordernado"

     

    E depois junte novamente

    O que diz o algoritmo sobre isso? apenas sigas os passos que deveria seguir... a questão do seu exemplo já ter o lado esquerdo ao pivô já ordenado ou não, não quer dizer nada. Sigas as etapas e pronto. Ao final, o vetor estará ordenado.

     

    De um modo geral, pelo que eu vi, o Quick Sort não é um método trivial... ou seja, tem uma certa complexidade. Um dos pontos chaves do método é a questão do uso de recursividade no processo (é o mais comum, pelo que eu vi, dá para fazer sem também)... você precisa ter uma noção sobre como funciona essa tal de recursividade antes.

     

    Então, você já trabalha com procedimentos e funções? basicamente a recursividade consiste em um procedimento invocar a se mesmo e funciona de forma que, cada vez que a uma instância invocada terminar, a próxima instrução vai continuar exatamente onde este último foi chamado. E vai seguindo o fluxo... da mesma forma que poderá invocar novamente a si mesmo, ou terminar... se terminar, volta para onde foi chamado e continua... a ideia é que vai continuar de onde parou sempre e está estruturado de tal forma que a lógica funciona.

     

    Abaixo encontrei um vídeo que explica como funciona o Quick Sort. Tenta dar uma estudada nele.

     

    obs.: eu não tenho certeza (não almocei ainda, rs... preciso assistir com mais calma), mas acho que ela confunde umas partes (que não comprometem o entendimento), por exemplo quando o pivô é o 52 meio que em diante, onde ela compara logo o lado direito já dizendo que já está ordenado, mas acho o algoritmo segue da esquerda para direita, ou seja, primeiro vai ordenando todo o lado esquerdo, com as suas recursividades quando necessário, e só após chegaria no a conclusão que o 52 já está ordenado (resumindo: ela conclui o 52 já está ordenado antes da hora).... mas veja... não tenho certeza, foi uma impressão... tenho que ver com mais calma.

     

    De um modo geral, o vídeo explica bem o funcionamento, dá uma boa noção da recursividade e para onde vai o i e o j... dos pouco que o vi, foi o melhor... a maioria apenas segue os passos, mas não explica por que deveria ser assim ou assado.

     

     


     

    No aguardo.

    • Curtir 1
    • Obrigado 1

    Compartilhar este post


    Link para o post
    Compartilhar em outros sites
  • Autor do tópico
  • Então amigo eu seguir alguns procedimentos conseguir fazer só a metade do lado esquerdo a do direito embolei 

    Olha o meu passo que tinha feito 

    A= [5,3,2,4,6,10,9,1,7,8]                       Cores = Esquerdo, Direito , Pivô

     

    5<6 ? Sim

    A= [5,3,2,4,6,10,9,1,7,8]   

    3 <6 ? Sim

     

    A= [5,3,2,4,6,10,9,1,7,8]   

     

    2 < 6 ? Sim

     

    A= [5,3,2,4,6,10,9,1,7,8

     

    4<6 ?sim

     

    A= [5,3,2,4,6,10,9,1,7,8

    6< 6 

     

    Agora foi para o outro lado porque  6 não é menor que 6 é igual

     

    A= [5,3,2,4,6,10,9,1,7,8

    8>6? sim 

     

    A= [5,3,2,4,6,10,9,1,7,8] 

    7>6?sim

     

    A= [5,3,2,4,6,10,9,1,7,8] 

     

    1>6? não então troca com 6

     

    A= [5,3,2,4,1,10,9,6,7,8] 

    ai eu dividir no meio   

     

    [5,3,2,4,1]        [10,9,6,7,8] 

     

    Conseguir resolver a parte esquerda

     

    mas a direita não

    [5,3,2,4,1

    5<2? não 

    passa para o lado direito 

    1>2?não

     

    então troca o 5 e o 1

    [1,3,2,4,5] 

     

     

    [1,3,2,4,5] 

     

    3<2 ?não

    4>2 ?sim

     

    [1,3,2,4,5] 

     

    3<2? não então troca

     

    [1,2,3,4,5] sendo assim essa parte está ordenada, só não conseguir ordenar a outra 

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    adicionado 6 minutos depois

    Olha o conflito que deu  10 9 6 7 8 

     

    pivo é o 6 

    10 esquerdo

    8 direito

     

    10,6?não então passa para o lado direito

    8>6? sim anda para o numero  7

    7>6? sim anda para o 6 

    6>6? não é igual então troca com o 10

     

    6,9,10,7,8

    6<10?sim

    9<10sim?

    10<10?não 

    ai me complicou essa parte não entendi mais nada

     

     

    • Curtir 1

    Compartilhar este post


    Link para o post
    Compartilhar em outros sites

    Posta as regras que está usando para eu poder analisar

    adicionado 30 minutos depois

    Adendo:

    25 minutos atrás, anonymouatour disse:

    ai eu dividir no meio   

    Acho que esta etapa está errada.. não é ainda para "dividir". Só para quando o j for menor que o i. E mesmo assim não é para simplesmente dividir, mas sim "fazer uma chamada recursiva". Dê uma analisada no vídeo que postei.

     

     

    No aguardo.

    adicionado 41 minutos depois

    ...após parar, vai fazer da posição inicial até o j. Depois do i até a posição final... algo assim.

    • Curtir 1
    • Obrigado 1

    Compartilhar este post


    Link para o post
    Compartilhar em outros sites
  • Autor do tópico
  • Tentei analisar mas viajei man na maionese não entendi kkkna parte recursiva bagunçou minha cabeça mas estou seguindo o que ela diz no início é mais a parte recursiva e por diante que embolei

    • Curtir 1

    Compartilhar este post


    Link para o post
    Compartilhar em outros sites
    Em 10/11/2017 às 17:33, anonymouatour disse:

    Tentei analisar mas viajei man na maionese não entendi kkkna parte recursiva bagunçou minha cabeça mas estou seguindo o que ela diz no início é mais a parte recursiva e por diante que embolei

     

    Dê uma pesquisada sobre recursividade. Veja de um modo geral. Recursividade é a base do problema.

     

     

     

     

     

    Mas seria mais ou menos o seguinte. Toda vez o que programa invoca uma função qualquer, o computador simplesmente vai executar o que tem que executar, e ao terminar a função, continua a partir do momento que foi chamado. Ex.:

    leia(x)
    escreva("Você digitou",x)
    fimAlgoritmo

    Ao invocar a função leia(), este vai fazer o que tem que fazer e ao terminar o programa vai para próxima linha após ele. Após invoca o escreva(), este vai fazer o que tem que fazer e ao terminar o programa vai para próxima linha após ele. Após invoca o fimAlgoritmo...

     

    Agora imagine uma qualquer, função A(), que ao executar o que tem que fazer, precisa chamar outra função B()... ou seja, a função B() fará o que tem que fazer, e ao terminar o programa vai para próxima linha após ele dentro de A(), que continuará executando o que tem que executar até terminar e voltar para onde ela foi invocada. Deu para entender?

     

    Na recursividade, apenas acontece que a função A() vai chamar a própria função A().  Seria como A() invocando B(), mas B() sendo sendo o próprio A(). Como dentro de A() chama a si mesmo, está estrutura obrigatoriamente tem que está preparada para de algum modo parar... se a condição de parar não for preparada, o programa iria ficar em loop infinito.

     

    No caso do QuikSort(), ao chegar no ponto que precisa dividir (i deixa de ser menor igual a j), ela verifica se precisa analisar o lado esquerdo da lista. Após terminar o esquerdo, verificará se precisa analisar o direito dela. Acontece que ao analisar o lado esquerdo, essa nova lista também pode ser subdividida em outras duas, onde o QS irá verificar o esquerdo dessa nova lista. Esse outra subista também pode ser dividida... por ai vai. Até que não possa mais, e voltar para o ponto anterior a último que foi invocada... verificará a lado direito, que por sua vez pode ser subdividida e ser analisada o seu lado esquerdo, que pode ser dividida novamente e ser analisada o lado esquerdo deste... etc etc etc.

     

    Assista o vídeo e perceba que:

    1. particiona a lista (faz aquelas trocas lá);
    2. verifica se tem uma nova lista ao lado esquerdo de j e invoca um QS() com ela;
    3. verifica se tem uma nova lista ao lado direito de i e invoca um QS() com ela;

    No caso, perceba que o item 2 e 3 são uma invocação do QS, logo seriam os próprios 3 itens...

    1. particiona a lista (faz aquelas trocas lá);
    2. verifica se tem uma nova lista ao lado esquerdo de j e invoca um QS() com ela;
    	1. particiona a lista (faz aquelas trocas lá);
    	2. verifica se tem uma nova lista ao lado esquerdo de j e invoca um QS() com ela;
    	3. verifica se tem uma nova lista ao lado direito de i e invoca um QS() com ela;
    3. verifica se tem uma nova lista ao lado direito de i e invoca um QS() com ela;
    	1. particiona a lista (faz aquelas trocas lá);
    	2. verifica se tem uma nova lista ao lado esquerdo de j e invoca um QS() com ela;
    	3. verifica se tem uma nova lista ao lado direito de i e invoca um QS() com ela;

    Entende? cada vez que a condição é válida e um QS é necessário, é iniciado uma nova recursividade.
     

    Um exemplo aleatório:

    1. particiona a lista (faz aquelas trocas lá);
    2. verifica se tem uma nova lista ao lado esquerdo de j e invoca um QS() com ela;
       1. particiona a lista (faz aquelas trocas lá);
       2. verifica se tem uma nova lista ao lado esquerdo de j e invoca um QS() com ela;
          1. particiona a lista (faz aquelas trocas lá);
          2. verifica se tem uma nova lista ao lado esquerdo de j e invoca um QS() com ela;
             1. particiona a lista (faz aquelas trocas lá);
                1. particiona a lista (faz aquelas trocas lá);
                2. verifica se tem uma nova lista ao lado esquerdo de j e invoca um QS() com ela;
                3. verifica se tem uma nova lista ao lado direito de i e invoca um QS() com ela;
             2. verifica se tem uma nova lista ao lado esquerdo de j e invoca um QS() com ela;
             3. verifica se tem uma nova lista ao lado direito de i e invoca um QS() com ela;
          3. verifica se tem uma nova lista ao lado direito de i e invoca um QS() com ela;
             1. particiona a lista (faz aquelas trocas lá);
             2. verifica se tem uma nova lista ao lado esquerdo de j e invoca um QS() com ela;
             3. verifica se tem uma nova lista ao lado direito de i e invoca um QS() com ela;
       3. verifica se tem uma nova lista ao lado direito de i e invoca um QS() com ela;
          1. particiona a lista (faz aquelas trocas lá);
          2. verifica se tem uma nova lista ao lado esquerdo de j e invoca um QS() com ela;
          3. verifica se tem uma nova lista ao lado direito de i e invoca um QS() com ela;
    3. verifica se tem uma nova lista ao lado direito de i e invoca um QS() com ela;
       1. particiona a lista (faz aquelas trocas lá);
       2. verifica se tem uma nova lista ao lado esquerdo de j e invoca um QS() com ela;
       3. verifica se tem uma nova lista ao lado direito de i e invoca um QS() com ela;
          1. particiona a lista (faz aquelas trocas lá);
          2. verifica se tem uma nova lista ao lado esquerdo de j e invoca um QS() com ela;
          3. verifica se tem uma nova lista ao lado direito de i e invoca um QS() com ela;

     

    Compartilhar este post


    Link para o post
    Compartilhar em outros sites

    Crie uma conta ou entre para comentar

    Você precisar ser um membro para fazer um comentário






    Sobre o Clube do Hardware

    No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

    Direitos autorais

    Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

    ×