MSD.sort() - Code Metrics - Inspection of "Implement most significant digit radix sorting" - chen0040/pyalgs - Measure and Improve Code Quality continuously with Scrutinizer

Completed

by Xianshun

created 2017-05-02 02:17 UTC

↳ Parent: MSD

Conditions

Total Lines

Lines	0
Ratio	0 %

Changes	1
Bugs	0	Features	0

1			class LSD(object):
2			R = 256
3
4			@staticmethod
5			def sort(a):
6			W = len(a[0])
7			aux = [None] * len(a)
8
9			for d in range(W - 1, -1, -1):
10			count = [0] * (LSD.R + 1)
11
12			for i in range(len(a)):
13			count[ord(a[i][d]) + 1] += 1
14
15			for r in range(0, LSD.R):
16			count[r + 1] += count[r]
17
18			for i in range(len(a)):
19			aux[count[ord(a[i][d])]] = a[i]
20			count[ord(a[i][d])] += 1
21
22			for i in range(len(a)):
23			a[i] = aux[i]
24
25
26			class MSD(object):
27
28			R = 256
29
30			@staticmethod
31			def sort(a):
32			MSD._sort(a, 0, len(a)-1, 0)
33
34			@staticmethod
35			def _sort(a, lo, hi, d):
36			if hi - lo <= 0:
37			return
38
39			count = [0] * (MSD.R+2)
40			aux = [None] * (hi - lo + 1)
41
42			for i in range(lo, hi+1):
43			count[MSD.char_at(a[i], d) + 2] += 1
44
45			for r in range(0, MSD.R):
46			count[r+1] += count[r]
47
48			for i in range(lo, hi+1):
49			aux[count[MSD.char_at(a[i], d) + 1]] = a[i]
50			count[MSD.char_at(a[i], d) + 1] += 1
51
52			for i in range(lo, hi+1):
53			a[i] = aux[i-lo]
54
55			for r in range(MSD.R):
56			MSD._sort(a, lo + count[r], lo + count[r+1] -1, d+1)
57
58			@staticmethod
59			def char_at(text, d):
60			if len(text) <= d+1:
61			return -1
62			return ord(text[d])

chen0040 / pyalgs