Quicksort

Estruturas de Dados e Algoritmos em Python

Miriam Antona

Software engineer

Quicksort

  • Segue o princípio de dividir para conquistar
  • Implementado por muitas linguagens
  • Técnica de partição
    • Pivô
    • itens menores que o pivô -> esquerda
    • itens maiores que o pivô -> direita
  • Elementos à esquerda são ordenados recursivamente
  • Elementos à direita são ordenados recursivamente
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados.

Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O primeiro elemento está em azul.

  • Partição de Hoare
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O primeiro elemento está em azul. Há dois ponteiros. O ponteiro da esquerda aponta para o segundo elemento e o da direita para o último.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O primeiro elemento está em azul. Há dois ponteiros. O ponteiro da esquerda aponta para o terceiro elemento e o da direita para o último.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O primeiro elemento está em azul. Há dois ponteiros. O ponteiro da esquerda aponta para o terceiro elemento e o da direita aponta para o quinto.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O primeiro elemento está em azul. Há dois ponteiros. O ponteiro da esquerda aponta para o terceiro elemento e o da direita aponta para o quinto. Há duas setas indicando que o terceiro e o quinto elementos serão trocados.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O primeiro elemento está em azul. Há dois ponteiros. O ponteiro da esquerda aponta para o terceiro elemento e o da direita aponta para o quinto. O terceiro e o quinto elementos foram trocados.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O primeiro elemento está em azul. Há dois ponteiros. O ponteiro da esquerda aponta para o quarto elemento e o da direita para o quinto.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O primeiro elemento está em azul. Há dois ponteiros. O ponteiro da esquerda aponta para o quarto elemento e o da direita para o quarto elemento.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O primeiro elemento está em azul. Há dois ponteiros. O ponteiro da esquerda aponta para o quarto elemento e o da direita para o terceiro.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O primeiro elemento está em azul. Há dois ponteiros. O ponteiro da esquerda aponta para o quarto elemento e o da direita para o terceiro. Há duas setas indicando que o primeiro e o terceiro elementos serão trocados.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O terceiro elemento está em azul. O primeiro e o terceiro foram trocados.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O terceiro elemento está em verde.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O terceiro elemento está em verde e os dois primeiros em laranja, representando a parte esquerda da lista.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O primeiro elemento está em azul, o segundo em laranja e o terceiro em verde. Os ponteiros esquerdo e direito apontam para o segundo elemento.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O primeiro elemento está em azul, o segundo em laranja e o terceiro em verde. Os ponteiros esquerdo e direito apontam para o segundo elemento. Há duas setas indicando que o primeiro e o segundo serão trocados.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O primeiro elemento está em azul, o segundo em laranja e o terceiro em verde. Os ponteiros esquerdo e direito apontam para o segundo elemento. O primeiro e o segundo foram trocados.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O primeiro elemento está em laranja e o segundo e o terceiro em verde.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O primeiro, o segundo e o terceiro elementos estão em verde.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O primeiro, o segundo e o terceiro elementos estão em verde. A parte direita da lista está em laranja.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O primeiro, o segundo e o terceiro elementos estão em verde. O primeiro elemento da parte direita está em azul. O ponteiro esquerdo aponta para o segundo elemento da parte direita e o direito para o último elemento da parte direita.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O primeiro, o segundo e o terceiro elementos estão em verde. O primeiro elemento da parte direita está em azul. Os ponteiros esquerdo e direito apontam para o segundo elemento da parte direita da lista.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O primeiro, o segundo e o terceiro elementos estão em verde. O primeiro elemento da parte direita está em azul. O ponteiro esquerdo aponta para o primeiro elemento da parte direita e o direito para o segundo.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O primeiro, segundo, terceiro e quarto elementos estão em verde, e o quinto e o sexto em laranja.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O primeiro, segundo, terceiro e quarto elementos estão em verde. O elemento está em azul. Os ponteiros esquerdo e direito apontam para o último elemento.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O primeiro, segundo, terceiro e quarto elementos estão em verde. O elemento está em azul. Os ponteiros esquerdo e direito apontam para o último elemento. Há duas setas indicando que o quinto e o sexto serão trocados.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. O primeiro, segundo, terceiro e quarto elementos estão em verde. O elemento está em azul. Os ponteiros esquerdo e direito apontam para o último elemento. O quinto e o sexto foram trocados.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - na prática

Um esquema de uma lista com números desordenados. Todos os elementos estão em verde porque estão ordenados.

  • Partição de Hoare
    • Mova o ponteiro da esquerda até achar valor maior que o pivô
    • Mova o ponteiro da direita até achar valor menor que o pivô
Estruturas de Dados e Algoritmos em Python

Quicksort - implementação

def quicksort(my_list, first_index, last_index):

    if first_index < last_index:

        partition_index = partition(my_list, first_index, last_index)

        quicksort(my_list, first_index, partition_index)

        quicksort(my_list, partition_index + 1, last_index)
Estruturas de Dados e Algoritmos em Python

Quicksort - implementação

def partition(my_list, first_index, last_index):

    pivot = my_list[first_index]
    left_pointer = first_index + 1
    right_pointer = last_index

    while True: 
        while my_list[left_pointer] < pivot and left_pointer < last_index:
            left_pointer += 1

        while my_list[right_pointer] > pivot and right_pointer >= first_index:
            right_pointer -= 1

        if left_pointer >= right_pointer:
            break

        my_list[left_pointer], my_list[right_pointer] = my_list[right_pointer], my_list[left_pointer]

    my_list[first_index], my_list[right_pointer] = my_list[right_pointer], my_list[first_index]

    return right_pointer
Estruturas de Dados e Algoritmos em Python

Quicksort - implementação

my_list = [6, 2, 9, 7, 4, 8] 
quicksort(my_list, 0, len(my_list) - 1)
print(my_list)

[2, 4, 6, 7, 8, 9]
Estruturas de Dados e Algoritmos em Python

Quicksort - complexidade

  • Pior caso: $O(n^2)$
  • Muito eficiente!
    • Caso médio: $\Theta(n\log{}n)$
    • Melhor caso: $\Omega(n\log{}n)$
  • Complexidade de espaço: $O(n\log{}n)$
Estruturas de Dados e Algoritmos em Python

Vamos praticar!

Estruturas de Dados e Algoritmos em Python

Preparing Video For Download...