It's known that the optimal sorting network for 16 entries as described here:
http://en.wikipedia.org/wiki/Sorting_network
will be between 53 and 60 compares long, the approach I describe here could only find a sorting network of 121 compares which I would call somewhat suboptimal, it would only require twice as many physical components to implement in hardware, but my code can find it quickly. It only takes a couple of minutes (in single-threaded Python) to find the 121 network for 16 entries which came out to:
[(0, 15), (1, 15), (0, 14), (2, 15), (1, 14), (0, 13), (3, 15), (2, 14), (1, 13), (0, 12), (4, 15), (3, 14), (2, 13), (1, 12), (0, 11), (5, 15), (4, 14), (3, 13), (2, 12), (1, 11), (0, 10), (6, 15), (5, 14), (4, 13), (3, 12), (2, 11), (1, 10), (0, 9), (7, 15), (6, 14), (5, 13), (4, 12), (3, 11), (2, 10), (1, 9), (0, 8), (8, 15), (7, 14), (6, 13), (5, 12), (4, 11), (3, 10), (2, 9), (1, 8), (0, 7), (9, 15), (8, 14), (7, 13), (6, 12), (5, 11), (4, 10), (3, 9), (2, 8), (1, 7), (0, 6), (10, 15), (9, 14), (8, 13), (7, 12), (6, 11), (5, 10), (4, 9), (3, 8), (2, 7), (1, 6), (0, 5), (11, 15), (10, 14), (9, 13), (8, 12), (7, 11), (6, 10), (5, 9), (4, 8), (3, 7), (2, 6), (1, 5), (0, 4), (12, 15), (11, 14), (10, 13), (9, 12), (8, 11), (7, 10), (6, 9), (5, 8), (4, 7), (3, 6), (2, 5), (1, 4), (0, 3), (13, 15), (12, 14), (11, 13), (10, 12), (9, 11), (8, 10), (7, 9), (6, 8), (5, 7), (4, 6), (3, 5), (2, 4), (1, 3), (0, 2), (14, 15), (13, 14), (12, 13), (11, 12), (10, 11), (9, 10), (8, 9), (7, 8), (6, 7), (5, 6), (4, 5), (3, 4), (2, 3), (1, 2), (0, 1)]
My approach was to compile a list of lists of every combination of 0's and 1's up to length 16, and find the longest swap necessary over all the lists, then iterate by making that swap over all the lists and then finding the next longest swap necessary, etc until all the lists are sorted. It's known by the Zero-One theorem that a network that sorts all of these lists will also sort any list of arbitrary elements...
** Notes**
If you shuffle the list of lists, it finds a different sorting network, but I haven't run it shuffled and found one better than 121, but these different 121 sorting networks might be good starting candidates for a genetic approach... Also thanks to John Owens who knew that my rough idea had to do with sorting networks and pointed me to some good references to continue...
**Source Code**
def copy(l):
l2 = []
for i in l:
l2.append(i)
return l2
def compare(t, i, j):
if t[i] > t[j]:
return True
return False
def swap(t, i, j):
if t[i] > t[j]:
temp = t[j]
t[j] = t[i]
t[i] = temp
return True
return False
def addelement(s, a, weight, listlength):
if len(a) < listlength:
a1 = copy(a)
a1.append(0)
addelement(s, a1,weight+1, listlength)
a2 = copy(a)
a2.append(1)
addelement(s, a2,weight, listlength)
else:
s.append([a, sorted(a)])
def bestswap(s, listlength):
pair = [0, listlength-1]
bestr = 0
bestl = listlength
best = 0
allsorted = True
for n in range(0, len(s)):
if s[n][0] != s[n][1]:
allsorted = False
if allsorted == True:
return [-1,-1]
for n in range(0, len(s)):
for l in range(0, listlength-best):
if s[n][0][l] == 1:
for r in range(listlength-1, l, -1):
if s[n][0][r] == 0:
if r - l > best:
best = r-l
bestl = l
bestr = r
return bestl, bestr
def main():
listlength = 16
s = []
a = []
addelement(s, a,0, listlength)
print(len(s))
pair = [0,0]
i = 0
pairs = []
while(pair != [-1,-1]):
pair = bestswap(s, listlength)
print(pair)
pairs.append(pair)
if pair != [-1,-1]:
for j in range(0, len(s)):
swap(s[j][0], pair[0], pair[1])
i+=1
print(i)
print(pairs)
main()
No comments:
Post a Comment