Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Algoritmo de ordenação FlashSort

+1 voto
22 visitas
perguntada Jun 25 em Ciência da Computação por CP (32 pontos)  

Introduzir o algoritmo FlashSort apresentando exemplos,ideia, escopo e complexidade.

Compartilhe

1 Resposta

+1 voto
respondida Jun 25 por CP (32 pontos)  

O algoritmo de ordenação Flash Short não emprega um método baseado na comparação de todos os elementos contidos em um vetor, utilizando um estrutura de permutação.

Devido a esse motivo, o algoritmo possui tempo O(n).

Basicamente, o FlashSort determina a divisão do vetor A com n elementos em m classes, cada qual contendo n/m elementos, de modo aproximado. Identifica-se três etapas: classificação, permutação, inserção.

A fim de compreender as três etapas, considere a seguinte lista A não ordenada:

A imagem será apresentada aqui.

O primeiro passo é determinar os valores máximo e mínimo:

\[A_{max} = 89, A_{min}=3\]

Para determinar a qual classe pertence cada elemento da lista A toma-se a função k:
\[k(A(i)) = 1 + int \left((m-1) \frac{A(i)-A_{min}}{A_{max}-A_{min}}\right)\]
sendo m o número de classes. Fixando o número de classes em 4, tem-se que:

A imagem será apresentada aqui.

O total de elementos em cada classe é:

A imagem será apresentada aqui.

Enquanto que o acumulado em cada classe é:

A imagem será apresentada aqui.

A consideração da quantidade acumulada por classe é necessária a o posicionamento dos elementos na etapa de permutação. Nessa etapa os elementos de uma mesma classe são agrupados. Antes de iniciar a permutação, os elementos máximo e 1 são trocados:

A imagem será apresentada aqui.

A permutação é iniciado pelo elemento 1, o qual será o valor máximo. Esse pertencerá à classe 4, cujo acumulado atinge valor 20, desse modo, o elemento 1 será posicionado na entrada 20 e o valor acumulado reduzido em 1. Em seguida, o número 12 que estava posicionado na entrada 20 é analisado. Sendo esse pertencente à classe 1, será alocada na entrada 6 e o valor acumulado para essa classe reduzido para 5. Com o término do processo de permutação tem-se:

A imagem será apresentada aqui.

Após a fase de permutação, os elementos de cada classe são ordenados:

A imagem será apresentada aqui.

Uma implementação do algoritmo em Python é:

import math
from collections import deque
from random import randint

A = [45, 56, 7, 10, 34, 89, 33, 3, 13, 67, 53, 23, 39, 50, 47, 49, 78, 65, 46, 12]
def flashsort(a, m):  # 'a' é a lista a ser ordenada, enquanto que 'm' é o número de classes
    ad = deque(a)
    a_min = min(ad)
    a_max = max(ad)

    # Definindo a qual classe cada elemento pertence:
    c = (m-1)/(a_max-a_min)
    classe = []
    for i in range(m):
        classe.append(0)

    for i in range(len(ad)):  # Aqui identifica-se quantos elementos estarão presentes em 
       # cada classe
        k = 1+math.floor(c*(ad[i]-a_min))
        classe[k-1] += 1

    for i in range(1, len(classe)):  # Aqui identifica-se em qual posição da lista inicia-se cada 
    # classe
        classe[i] = classe[i] + classe[i-1]

    # Trocando o primeiro elemento pelo elemento máximo:
    ad[ad.index(max(ad))] = ad[0]
    ad[0] = a_max

    move = 0
    aux = [ad[0]]
    j = 0

    # Ordenando as classes
    while move < (len(ad)):
        k = 1+math.floor(c*(aux[j]-a_min))
        aux.append(ad[classe[k - 1] - 1])
        ad[classe[k - 1] - 1] = aux[j]
        j += 1
        classe[k - 1] -= 1
        move += 1
    """
    O elemento máximo é duplicado quando se posiciona o elemento na última entrada
    (Lembrar que o elemento é inicialmente posicionado na primir entrada)
    O último elemento que foi colocado em aux é então trocado pelo valor máximo que 
    estava na 
    posição inicial foi movido pela lista
    """
    h = ad.index(a_max)
    ad[h] = aux[len(aux)-1]

    # Ordenando os elementos dentro das classes
    o = deque()
    for j in range(len(ad)-1):  # Percorre-se a lista realizado a primeira troca
        if ad[j] > ad[j + 1]:
            o.append(j)
            # Salva-se as posições em que foram feitas alterações, pois demais alterações 
            # serão feitas nesses pontos
            h = ad[j]
            ad[j] = ad[j + 1]
            ad[j + 1] = h

    while len(o) > 0:
        if ad[o[0]-1] > ad[o[0]] and o[0] != 0:
            s = ad[o[0]]
            ad[o[0]] = ad[o[0]-1]
            ad[o[0]-1] = s
            o.append(o[0] - 1)
            o.popleft()
        else:
            o.popleft()

    return ad

if __name__ == '__main__':
    print(flashsort(A, 4))

Observações:

TREVISAN, A. L. ALGORITMOS DE ORDENAÇÃO NA OTIMIZAÇÃO DO VALOR ORDENADO. 2008. Dissertação (Mestrado em Matemática Aplicada) - Instituto de Matemática, Estatística e Computação Científica, Universidade Estadual de Campinas, Campinas.
Disponível em: http://repositorio.unicamp.br/bitstream/REPOSIP/307470/1/Trevisan_AndreLuis_M.pdf

comentou 6 dias atrás por Adriana Molinari (106 pontos)  
A eficiência do algoritmo FlashSort depende da escolha da quantidade de classes, haja vista que o incremento do número de classes eleva o número de operações na fase de classificação, enquanto a redução amplia o número de operações na fase de inserção.
Comparando a eficiência desse método com o QuickSort, nota-se maior eficiência do FlashSort tomando listas cujos dados exijam consideráveis operações durante a comparação de elementos. Considerando o exemplo de uma lista com 500 entradas em ordem decrescente, caso seja fixado 20 classes para o FlashSort, este exibirá tempo de execução inferior ao QuickSort em 0.11, enquanto adotando 4 e 100 classes, a diferença se torna 0.06 e 0.04, respectivamente.
...