Classificacao por intercalacao : um metodo confiavel
Visualizar/abrir
Data
1995Tipo
Resumo
Apresentamos neste artigo a análise do desempenho do método de classificação por intercalação, conhecido como straight two-way merge sorting [KNU73]. A análise deste método permite concluir que seu de sempenho é bastante uniforme, independentemente do arranjo inicial das chaves, pois o mesmo se mantém na faixa logarítmica em qual quer caso, o que o torna recomendável nas aplicações em que o tempo de classificação é limitado a um teto. O resultado da análise também mostra que, curiosamente, o pi ...
Apresentamos neste artigo a análise do desempenho do método de classificação por intercalação, conhecido como straight two-way merge sorting [KNU73]. A análise deste método permite concluir que seu de sempenho é bastante uniforme, independentemente do arranjo inicial das chaves, pois o mesmo se mantém na faixa logarítmica em qual quer caso, o que o torna recomendável nas aplicações em que o tempo de classificação é limitado a um teto. O resultado da análise também mostra que, curiosamente, o pior caso para o método é de desempenho bastante próximo do caso médio. Ao final, são feitas considerações a respeito da alternativa de explorar a existência de seqüências natu- .. rais nas chaves a serem ordenadas. A análise deste caso, denominado natural two-way merge sorting [KNU73], mostra que as seqüências na turalmente encontradas nas chaves possuem tamanho médio pequeno, sendo que o esforço necessário para identificá-Ias não produz ganhos em relação ao primeiro caso. ...
Abstract
This work presents the performance analisys of the sorting proce dure known as straight two-way merge sorting [KNU73].The results of such analisys allow to conclude that its perforrnance is very uniform, independently of the initial arrangement of the keys, since the perfor mance function is oflogarithmic order in any case. This characteristic makes the method usable in applications in which the response time is bounded, as in the real time control processes systems. We also show that its perfo ...
This work presents the performance analisys of the sorting proce dure known as straight two-way merge sorting [KNU73].The results of such analisys allow to conclude that its perforrnance is very uniform, independently of the initial arrangement of the keys, since the perfor mance function is oflogarithmic order in any case. This characteristic makes the method usable in applications in which the response time is bounded, as in the real time control processes systems. We also show that its performance in the worst case is curiously very dose of that of medium case. At last, we discuss the hypothesis of explore the occurence of natural sequencesin the initial arrangement of the keys. The analisys of this case, known as natural two-way merge sor ting [KNU73],showsthat such sequences have a small medium size, which does not pays the effort. ...
Contido em
Revista de Informatica Teorica e Aplicada. Porto Alegre. vol. 2, n. 2 (out.1995), p. 55-70
Origem
Nacional
Coleções
-
Artigos de Periódicos (40031)Ciências Exatas e da Terra (6103)
Este item está licenciado na Creative Commons License