Outro Algoritmo de ordenação Quick sort

anonymouatour · 9 de novembro de 2017

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

devair1010 · 9 de novembro de 2017

@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;

Simon Viegas · 10 de novembro de 2017

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.

anonymouatour · 10 de novembro de 2017

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

Simon Viegas · 10 de novembro de 2017

@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.

anonymouatour · 10 de novembro de 2017

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]

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

Simon Viegas · 10 de novembro de 2017

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.

anonymouatour · 10 de novembro de 2017

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

Simon Viegas · 11 de novembro de 2017

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;