Ir ao conteúdo
  • Cadastre-se
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

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

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

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

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora





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

×