/= 3, is a network N levels deep with 1/2.N.(N - 1) comparators, as shown in Fig. 1. This sorting..."/> Sorting Scheme for Bubble Ladder Structure - IP.com
Browse Prior Art Database

Sorting Scheme for Bubble Ladder Structure

IP.com Disclosure Number: IPCOM000085116D
Original Publication Date: 1976-Feb-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 4 page(s) / 100K

Publishing Venue

IBM

Related People

Chen, TC: AUTHOR [+3]

Abstract

In Knuth, The Art of Computer Programming, Vol 3, "Sorting and Searching", Addison-Wesley, Menlo Park, California, 1973, at pages 241 and 640, it is stated that the "odd-even transposition sort" for N numbers, N >/= 3, is a network N levels deep with 1/2.N.(N - 1) comparators, as shown in Fig. 1. This sorting algorithm is straightforward and fast. Its efficiency can be attributed to the implied requirement that provision must be made to permit simultaneous interchanges of numbers (or records in general).

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 4

Sorting Scheme for Bubble Ladder Structure

In Knuth, The Art of Computer Programming, Vol 3, "Sorting and Searching", Addison-Wesley, Menlo Park, California, 1973, at pages 241 and 640, it is stated that the "odd-even transposition sort" for N numbers, N >/= 3, is a network N levels deep with 1/2.N.(N - 1) comparators, as shown in Fig. 1. This sorting algorithm is straightforward and fast. Its efficiency can be attributed to the implied requirement that provision must be made to permit simultaneous interchanges of numbers (or records in general).

Next, consider the six-rung bubble ladder shown in Figs. 1a-d, each rung holds a single (equal-length) record. In between rungs, there exist the individually controllable mode control switches. With switches operated in the bypass mode (S = 0), the record in each rung will loop within the rung, and the time required to complete one looping is called one cycle. On the other hand, with the switches operated in the crossover mode (S = 1), two neighboring rungs can interchange their records in one cycle.

It is clear that the bubble ladder structure does have the capability of simultaneous interchange of neighboring records, by setting the mode control switches to crossover mode. Consequently, an N-record sequence can be sorted or permuted to any prescribed order in no more than N cycles. As will be seen later, the final scheme is even twice as fast as this.

Let it be assumbed that (the perimeter of) each rung of the bubble ladder is composed of R bubble positions. The time to move one such position is called a microcycle. To interchange two neighboring records in the manner described above, implies that every element of a record has to travel R bubble positions in R microcycles or one cycle. Consequently, it takes K cycles (or KR microcycles) to "move" a record K rungs away, using this interchange scheme. However, it is possible to achieve this "movement" in half of the cycles by letting individual record elements travel only half of the bubble positions (lower sides alternating with upper sides of intervening rungs) required in the above scheme.

Thus, it takes only K/2 cycles for one half of a given record in rung i to reach either rung i + K or rung i - K. An additional half-cycle is needed for the other half to reach the destination. Consequently, for sorting an N-record sequence, the upper limit of sorting time on the bubble ladder using this scheme is (N + 1)/2 cycles.

Mode control switches regulate the interchanges as a result of comparing the keys of involved r...