Voltar
Artigo Acesso aberto Produção Nacional
BIBTEX RIS

O Algoritmo de Ordenação Smoothsort explicado

2009; UNIVERSIDADE DO ESTADO DO RIO DE JANEIRO; Volume: 28; Linguagem: Inglês

10.12957/cadinf.2009.6469

ISSN

2317-2193

Autores

André L. Pfitzner, Paulo E. D. Pinto, Rosa Maria E. Moreira da Costa,

Tópico(s)

Coding theory and cryptography

Resumo

We present the sorting algorithm Smoothsort [1] [2], developed by Dijkstra in 1981 which, inexplicably, is not mentioned in the current literature on methods of ordering as a special one [3][4][5].Its importance comes from the fact that it has worst case complexity O(n log n) in general, restricted to O(n) for sets of data already ordered.This is an important practical situation.None of the methods described in the literature presents such behavior.In addition to describing the algorithm, we also show alternative analysis of algorithm complexity, which are not present in the original paper about the method.

Referência(s)