Welcome, guest | Sign In | My Account | Store | Cart

The recipe illustrates a Python implementation of the bitsort algorithm. This algorithm is illustrated in the book "Programming Pearls" by Jon Bentley. The bitsort algorithm provides a very efficient way to sort large numbers in disk files.

Python, 26 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Python implementation of bitsort algorithm from "Programming Pearls"

def bitsort(filename, maxn):
    """ Sort a file named 'filename' which
    consists of maxn integers where each
    integer is less than maxn """

    # Initialize bitmap
    a = [0]*maxn

    # Read from file and fill bitmap
    for line in file(filename):
        n = int(line.strip())
        # Turn bits on for numbers
        if n<maxn: a[n] = 1

    # Return a generator that iterates over the list
    for n in range(len(a)):
        if a[n]==1: yield n

    
if __name__=="__main__":
    # numbers.txt should contain a list of numbers
    # each less than 1000000, one per line.
    for num in bitsort('numbers.txt',1000000):
        print num
Created by Anand on Tue, 11 Sep 2007 (PSF)
Python recipes (4591)
Anand's recipes (38)

Required Modules

  • (none specified)

Other Information and Tasks