Funcionamento do QuickSort

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Pesquisa e Ordenação de Dados
Quicksort
ALEXSANDRO F. DOS SANTOS
SISTEMAS DE INFORMAÇÃO – TURMA 2015.1
ALGORITMO QUICKSORT
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
PIVÔ
34
23
42
65
18
54
ALGORITMO QUICKSORT
34
23
42
65
18
54
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
42
PIVÔ
ALGORITMO QUICKSORT
34
23
42
65
18
54
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
42
PIVÔ
ALGORITMO QUICKSORT
34
23
42
65
18
54
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
42
PIVÔ
ALGORITMO QUICKSORT
34
23
42
65
18
54
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
42
PIVÔ
ALGORITMO QUICKSORT
34
23
42
65
18
54
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
42
PIVÔ
ALGORITMO QUICKSORT
34
23
42
65
18
54
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
42
PIVÔ
ALGORITMO QUICKSORT
34
23
18
65
42
54
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
42
PIVÔ
ALGORITMO QUICKSORT
34
23
18
65
42
54
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
42
PIVÔ
ALGORITMO QUICKSORT
34
23
18
65
42
54
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
42
PIVÔ
ALGORITMO QUICKSORT
34
23
18
65
42
54
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
42
PIVÔ
ALGORITMO QUICKSORT
34
23
18
65
42
54
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
42
PIVÔ
ALGORITMO QUICKSORT
34
23
18
65
42
54
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
42
PIVÔ
ALGORITMO QUICKSORT
34
23
18
42
65
54
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
42
PIVÔ
ALGORITMO QUICKSORT
34
23
18
42
65
54
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
42
PIVÔ
ALGORITMO QUICKSORT
34
23
18
42
65
54
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
42
PIVÔ
ALGORITMO QUICKSORT
34
23
18
42
65
54
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
42
PIVÔ
ALGORITMO QUICKSORT
34
23
18
42
65
54
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
42
PIVÔ
ALGORITMO QUICKSORT
34
23
18
42
65
54
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
42
PIVÔ
ALGORITMO QUICKSORT
34
23
18
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
23
PIVÔ
ALGORITMO QUICKSORT
34
23
18
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
23
PIVÔ
ALGORITMO QUICKSORT
34
23
18
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
23
PIVÔ
ALGORITMO QUICKSORT
34
23
18
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
23
PIVÔ
ALGORITMO QUICKSORT
18
23
34
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
23
PIVÔ
ALGORITMO QUICKSORT
18
23
34
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
23
PIVÔ
ALGORITMO QUICKSORT
18
23
34
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
23
PIVÔ
ALGORITMO QUICKSORT
18
23
34
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
23
PIVÔ
ALGORITMO QUICKSORT
18
23
34
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
23
PIVÔ
ALGORITMO QUICKSORT
18
23
34
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
23
PIVÔ
ALGORITMO QUICKSORT
65
54
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
54
PIVÔ
ALGORITMO QUICKSORT
65
54
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
54
PIVÔ
ALGORITMO QUICKSORT
65
54
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
54
PIVÔ
ALGORITMO QUICKSORT
65
54
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
54
PIVÔ
ALGORITMO QUICKSORT
54
65
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
54
PIVÔ
ALGORITMO QUICKSORT
54
65
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
54
PIVÔ
ALGORITMO QUICKSORT
54
65
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
54
PIVÔ
ALGORITMO QUICKSORT
54
65
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
54
PIVÔ
ALGORITMO QUICKSORT
54
65
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
54
PIVÔ
ALGORITMO QUICKSORT
18
23
34
42
54
65
ESCOLHA UM PIVÔ ALEATÓRIO
AVANCE O PONTEIRO DA ESQUERDA ENQUANTO O VALOR FOR MENOR QUE O PIVÔ
RETROCEDA O PONTEIRO DA DIREITA ENQUANTO O VALOR FOR MAIOR QUE O PIVÔ
TROQUE OS VALORES APONTADOS
REPITA O PASSO 2 ATÉ QUE OS PONTEIROS SE ENCONTREM
REPITA TODO O PROCESSO COM CADA SUBLISTA
PIVÔ