Browse Prior Art Database

Aggregation Sorting

IP.com Disclosure Number: IPCOM000100626D
Original Publication Date: 1990-May-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 8 page(s) / 229K

Publishing Venue

IBM

Related People

Douglas, CC: AUTHOR [+2]

Abstract

A technique is described whereby any iterative sorting algorithm can accelerate applications by implementing a method of aggregation and disaggregation.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 26% of the total text.

Aggregation Sorting

       A technique is described whereby any iterative sorting
algorithm can accelerate applications by implementing a method of
aggregation and disaggregation.

      The concept implements a few iterates of an iterative sorting
algorithm and then applies an auxiliary aggregation/disaggregation
algorithm, termed aggr-sort, to move more data elements into place
than the iterative algorithm would have for the same cost.  The
aggr-sort may be re-applied after execution of some additional
iterative sorting steps. Therefore, the two algorithms form a
symbiotic bond.  Mod-aggr- sort is a specialized form of aggr-sort,
which requires using a variant of bubblesort as the iterative sorting
algorithm.  As a result, for this iterative sorting algorithm,
mod-aggr-sort is more efficient than aggr-sort.  The techniques are
shown in Fig. 1.

      The iterative sorting algorithm should be simple, although not
a requirement.  For a simple hardware implementation, a good choice
is bubblesort, as follows:
  algorithm bubblesort (m, data) {
         m = number of simple sort iterations
         data = collection of elements to be sorted
       do i = 1, 2, ..., m {
            swapcount = 0
            for k = 1 to (size of data - i){
                 if ( data(k) > data(k+1)) {
                       swap data(k) and data(k+1)
                       swapcount = swapcount + 1
                       }
                 }
            if ( swapcount = 0 ) return 0
            }
       return swapcount
       }

      To completely sort the data with bubblesort requires m = N
simple sort iterations.  The worst case requires N/2(N -1)
comparisons, which is unacceptably high.

      Swapping is performed by swapping pointers to the data
structures, changing pointers in a linked list, physically moving the
structures around in memory, or some other technique appropriate to
how the data is stored.

      The aggregation/disaggregation algorithms partition the data
into aggregates with s > 1 elements.  For each aggregate of elements,
a representative is maintained (denoted by (k) in the algorithm
bubblesort).  The representative might be the minimum, the average
(if such exists), or some other measure of the elements in the
collection. For example, if the aggregation factor s = 4, then
1   2   3   4   5   6   7   8
is aggregated as
1,2,3,4   5,6,7,8
with a representative associated with each of the two collections of
data.  If minimum values are used as the swapping strategy, then
 data(1) = 1  and data(2) = 5.
However, if average values are chosen as the swapping strategy, then
 data(1) = 2.5  and data(2) = 6.5.
If s had been 3 instead of 4, then after aggregating, the result
might have been
                ...