-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathLSD.py
More file actions
64 lines (45 loc) · 1.16 KB
/
LSD.py
File metadata and controls
64 lines (45 loc) · 1.16 KB
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
50
51
52
53
54
55
56
57
58
59
60
import os, sys
class LSDSort():
def __init__(self, a=[]):
self.a = a
self.R = 256 #ascii
self.aux = [0]*(len(a))
def sort(self):
N = len(self.a)
print 'self.a: {}'.format(self.a)
length = len(self.a[0])
print 'length=',length
for d in range(length-1,-1,-1):
bucket = [0] * (self.R + 1)
print bucket
#compute the times each character appear
for i in range(0,N):
lsd = self.a[i][d]
bucket[ord(lsd)]+=1
print 'first bucket:{}'.format(bucket)
#cumulative to compute the actual position
for i in range(0,self.R):
bucket[i+1] += bucket[i]
print 'after cumlative:{}'.format(bucket)
# aux variable
for i in range(0,N):
lsd = self.a[i][d]
print 'lxb:',bucket[ord(lsd)], 'N=',N,'i=',i
self.aux[bucket[ord(lsd)]] = self.a[i]
bucket[ord(lsd)] += 1
print 'aux= {}'.format(self.aux)
import pdb;pdb.set_trace()
#copy back
self.a = self.aux
def printList(self):
print self.a
def UnitTest():
data=[]
with open ("airport.csv", "r") as myfile:
for line in myfile.readlines():
data.append(line.replace('\n', ''))
print data
RS = LSDSort(data)
RS.sort()
RS.printList()
UnitTest()