Classificacao por intercalacao : um metodo confiavel
View/ Open
Date
1995Author
Type
Abstract in Portuguese (Brasil)
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. ...
In
Revista de Informatica Teorica e Aplicada. Porto Alegre. vol. 2, n. 2 (out.1995), p. 55-70
Source
National
Collections
-
Journal Articles (39552)Exact and Earth Sciences (6036)
This item is licensed under a Creative Commons License