Browse Prior Art Database

Order N Algorithm for Building a Sorted View of an Array

IP.com Disclosure Number: IPCOM000108664D
Original Publication Date: 1992-Jun-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 7 page(s) / 196K

Publishing Venue

IBM

Related People

Blais, MN: AUTHOR [+2]

Abstract

A method for producing a sorted view of an array is disclosed. The algorithm is of order N, and the data may be sorted on multiple keys.

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

Order N Algorithm for Building a Sorted View of an Array

       A method for producing a sorted view of an array is
disclosed.  The algorithm is of order N, and the data may be sorted
on multiple keys.

      Sorting an array of records on one or more keys has long been a
basic task performed by computers.  Most modern sorting algorithms
are order Nlog(N); i.e., require c * N * log(N) units of time to
complete, where N is the number of records in the array to be sorted
and c is a constant.  A faster sort is always desirable, even if it
can only be used under special circumstances.

      This article describes an algorithm which will produce a view
of an array of records which is sorted on one or more keys.  The
order of this algorithm is N; i.e., the amount of time required to
produce the view is directly proportional to the number of records in
the array to be sorted.  The primary restriction on this algorithm is
that the key values must be limited to a known range of discrete
values.

      The solution to this problem involves a three-step process:
      -    During the first step, an array of counts is built to
accumulate the number of times each distinct key value is
encountered.  This array will have m dimensions, where m is the
number of key values on which the sort is being performed.
      -    The second step turns these counts into indexes into a
linear array which will eventually hold the sorted view of the list.
This is done by initially finding the first non-zero count and
changing it to 1. Subsequent non-zero counts are changed to the sum
of all previous non-zero counts plus 1.
      -    The third step builds the sorted view of the data by
sequentially processing the data to be sorted, storing the loop index
in the view array at the position specified by the key fields from
the data array indexed by the loop index.

      The algorithm is best illustrated by an example. Consider the
case where a company has different levels of employees.  Employees
enter the company as new hires.  As time passes and skills are
accumulated, an employee is promoted to associate worker level.  As
more time passes, and more skills are accumulated, an employee is
promoted through the ranks and may eventually achieve the...