FilesExpand file tree

 master

/

sorting_linear.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

49 lines (35 loc) · 1.32 KB

 master

/

sorting_linear.py

Copy path

Top

File metadata and controls

• Code
• Blame

49 lines (35 loc) · 1.32 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

"""

Task:

Implement an algorithm to sort 1,000,000 32-bit integers, using only 350K of memory.

The numbers could be any number from 0 to 9,999,999

The numbers are in a file, one line per number. There are no duplicates.

Output the numbers, one to a line, to a file.

The algorithm must be linear-time.

"""

class Bitsort(object):

def __init__(self, max_number):

self._int_bits = 32

self._buckets = (max_number // self._int_bits) + 1

self._bit_array = [0] * self._buckets

def save_number(self, number):

bucket = number // self._int_bits

bit_number = number % self._int_bits

self._bit_array[bucket] |= 1 << bit_number

def get_sorted_numbers(self):

for index, bits in enumerate(self._bit_array):

base = index * self._int_bits

if not bits: # skips empty buckets

continue

for j in range(self._int_bits):

if bits & (1 << j):

yield base + j

def main():

bitsorter = Bitsort(9999999)

with open("numbers.txt", "r") as in_file:

for line in in_file:

bitsorter.save_number(int(line.rstrip()))

out_file = open("out.txt", "w", 4096)

for number in bitsorter.get_sorted_numbers():

out_file.write(str(number) + "\n")

if __name__ == "__main__":

main()