Data structure enhancements for in-place sorting of a singly lin

Details Data structure enhancements for in-place sorting of a singly lin Data structure enhancements for in-place sorting of a singly lin

1995-10-18

1997-09-23

Black, Thomas G.

395611, 395612, 395613, 395614, 395615, 39549701, G06F 708, G06F 700

Patent

active

056714068

ABSTRACT:
An apparatus and method for performing a skip list insertion sort on a singly linked list of elements is provided. Each element to be sorted includes a key, an element pointer in an element pointer field and a flag bit. Also provided is an indexed array of pointer arrays. If an element is to be inserted at a node level greater than zero, a free pointer array is allocated by storing an index corresponding to the allocated pointer array in the element pointer field and setting the corresponding flag bit. If a free pointer array is not available, then the node level of the element is forced to zero. If the level of the element is either assigned as or forced to zero, the flag bit is not set and the pointer array itself occupies the element pointer field as the element pointer instead of the index. Thus, the pointer to the element pointer field will point directly to the specified pointer array location without having to index into the array of pointer arrays. The skip list insertion search part of the sorting routine for each subsequent item to be inserted then tests the flag bit when traversing the list to determine whether the pointer array is in the array of pointer arrays or the element pointer field itself.

REFERENCES:
patent: 5121493 (1992-06-01), Ferguson
patent: 5175857 (1992-12-01), Inoue
patent: 5263160 (1993-11-01), Porter, Jr. et al.
patent: 5274805 (1993-12-01), Ferguson et al.
patent: 5278987 (1994-01-01), Chiang et al.
patent: 5303367 (1994-04-01), Leenstra, Sr. et al.
patent: 5551018 (1996-08-01), Hansen
patent: 5557786 (1996-09-01), Johnson, Jr.
patent: 5560006 (1996-09-01), Layden et al.
patent: 5577243 (1996-11-01), Sherwood et al.
William, Pugh, "Skip Lists, A Probabilistic Alternative to Balance Trees" Communications of the ACM, V33, N6, Jun. 1990, pp. 668-676.
Gupta, Gouind, "Sorting by Hashing and Inserting", 17th Ann. ACM Conf. Communications of the ACM, 21 Feb. 1989-23 Feb. 1989.
Kirschenhoffer, Peter, "Analysis of an Optimized Search Algorithm for Skip Lists", Theoretical Computer Science, V144, N1-2, Jun. 26, 1995, pp. 199-220.
Horowitz et al., "Fundamentals of Data Structures", Computer Science Press, 1983, pp. 106-200.

Affiliated with

Also associated with

Rating

Data structure enhancements for in-place sorting of a singly lin does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Data structure enhancements for in-place sorting of a singly lin, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data structure enhancements for in-place sorting of a singly lin will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1942196