To access the full text documents, please follow this link: http://hdl.handle.net/2099.1/10241

Two-way replacement selection
Martínez Palau, Xavier
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV; Larriba Pey, Josep; Domínguez Sal, David
The performance of external sorting is highly dependant on the length of the runs generated. One of the most commonly used run generation strategies is Replacement Selection (RS) because, on average, it generates runs that are twice the size of the memory available. However, the length of the runs generated by RS is downsized for data with certain characteristics,like inputs sorted inversely with respect to the desired output order. The goal of this project is to propose and analyze two-way replacement selection (2WRS), which is a generalization of RS obtained by implementing two heaps instead of the single heap implemented by RS. The appropriate management of these two heaps allows generating runs larger than the memory available in a stable way, i.e. independent from the characteristics of the datasets. Depending on the changing characteristics of the input dataset, 2WRS assigns a new data record to one or the other heap, and grows or shrinks each heap, accommodating to the growing or decreasing tendency of the dataset. On average, 2WRS creates runs of at least the length generated by RS, and longer for datasets that combine increasing and decreasing data subsets. We tested both algorithms on large datasets with different characteristics and 2WRS achieves speedups at least similar to RS, and over 2.5 when RS fails to generate large runs. . El projecte consisteix en desenvolupar un algorisme d'ordenació externa basat en Replacement Selection, de manera que solucioni els problemes inherents a replacement selection. L'estudiant haurà de dissenyar i implementar l'algorisme, fer un estudi estadístic de la seva eficiència, i comparar la eficiència en temps del nou algorisme amb replacement selection.
Àrees temàtiques de la UPC::Matemàtiques i estadística
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat
Algorithms
Sorting
External sorting
Replacement selection
Merge sort
Run formation
Algorismes
Classificació AMS::68 Computer science::68W Algorithms
Attribution-NonCommercial-ShareAlike 3.0 Spain
http://creativecommons.org/licenses/by-nc-sa/3.0/es/
info:eu-repo/semantics/masterThesis
Universitat Politècnica de Catalunya
         

Show full item record

Related documents

Other documents of the same author

Martínez Palau, Xavier; Domínguez Sal, David; Larriba Pey, Josep
Barbu, Lucia Gratiela; Martínez Palau, Xavier; Oller Martínez, Sergio Horacio; Barbat Barbat, Horia Alejandro
 

Coordination

 

Supporters