## Friday, May 22, 2015

### A G-sort of 20 items and example code

Supposing we have a list of 20 items to be sorted, here I'll just use the numbers 0-19:
[13, 8, 10, 18, 0, 4, 2, 11, 12, 14, 7, 19, 1, 3, 17, 6, 15, 5, 9, 16]
Consider a number M for each pairwise comparison that is the distance between the numbers swapped if a swap should be made, that is that the rightmost number is smaller, for that pair or 0 otherwise.

Now I thought, what swap could be made on 10000 such random lists like the above so that the sum of the M's for that swap is the greatest over all the lists... perhaps unsurprisingly this ended up being:
[0, 19], indicating that the first and the last items of the the list should be compared and swapped to maximize the sum of the M's over all the lists, in the example above 13 would be compared to 16 and no swap would be made because 13 is already smaller than 16, but in many lists a swap would be made....

So if we have our 10000 random lists and we've already swapped [0,19], we find what should be the next swap to make the greatest sum of M's over all the lists, and iterate like that until all the lists are completely sorted, I ended up with:
[[0, 19], [1, 18], [2, 17], [3, 16], [4, 15], [5, 19], [0, 14], [1, 13], [6, 18], [7, 17], [2, 12], [5, 14], [0, 11], [8, 19], [9, 16], [1, 9], [3, 13], [6, 15], [0, 10], [10, 18], [4, 10], [5, 11], [11, 17], [8, 14], [2, 8], [12, 19], [7, 12], [0, 7], [10, 16], [3, 11], [8, 13], [13, 18], [1, 7], [9, 15], [15, 19], [3, 9], [6, 11], [11, 15], [5, 10], [2, 6], [1, 5], [14, 18], [4, 8], [0, 4], [10, 14], [6, 10], [16, 19], [12, 16], [8, 12], [14, 17], [7, 13], [3, 7], [9, 14], [5, 9], [0, 2], [2, 5], [10, 13], [7, 10], [1, 4], [13, 15], [5, 8], [12, 14], [6, 9], [9, 12], [4, 6], [8, 11], [15, 18], [17, 19], [15, 17], [6, 8], [11, 13], [3, 5], [7, 9], [10, 12], [9, 11], [16, 18], [0, 3], [14, 16], [5, 7], [2, 4], [1, 3], [13, 14], [14, 15], [12, 13], [8, 10], [3, 4], [11, 12], [18, 19], [5, 6], [4, 5], [7, 8], [6, 7], [16, 17], [15, 16], [8, 9], [10, 11], [1, 2], [2, 3], [0, 1], [17, 18], [9, 10], [13, 14], [12, 13], [5, 6], [14, 15], [7, 8], [11, 12], [3, 4], [13, 14], [1, 2], [6, 7], [8, 9], [12, 13], [10, 11], [14, 15], [9, 10]]
After these 116 compares and swaps all 10000 lists were in order. As you can see it's hard to discern a pattern after the first few swaps other than generally the items swapped get closer together, the code below is general enough that it can be used for more than 10000 lists or more or less than 20 items...

**Python Source Code**

import random
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 bestswap(s, trials, listlength, sortd):
pair = [0,0]
best = 0
allsorted = True
for n in range(0, trials):
r = copy(s[n])
if s[n] != sortd:
allsorted = False
if allsorted == True:
return [-1,-1]
for i in range(0, listlength-1):
for j in range(i+1, listlength):
total = 0

for n in range(0, trials):
t = copy(s[n])
if compare(t, i, j):
total += j-i
if total > best:
best = total
pair = [i,j]
return pair
def main():
s = []
trials = 10000
listlength = 20
sortd = []
for j in range(0, listlength):
sortd.append(j)

for j in range(0, trials):
l = []
for i in range(0, listlength):
l.append(i)
random.shuffle(l)
s.append(l)
bestpair = [0,listlength-1]
i = 0
al = []
while(bestpair != [-1,-1]):
i+=1
al.append(bestpair)
for j in range(0, trials):
swap(s[j], bestpair[0], bestpair[1])
bestpair = bestswap(s, trials, listlength, sortd)
print(bestpair)

print(i)
print(al)

main()
** Update**
I let the program go over 100,000 trials and it found these 120 swaps to work over that entire assortment of lists, it took a couple of hours for the python code to run it could be much faster in other languages. So for 10,000 it took 116 swaps, for 100,000 it took 120, I figure it must not be that many more swaps for all possible lists...

[[0, 19], [1, 18], [2, 17], [3, 16], [4, 15], [5, 19], [0, 14], [1, 13], [6, 18], [2, 12], [7, 17], [5, 14], [8, 19], [0, 11], [9, 16], [1, 9], [3, 10], [10, 18], [6, 13], [4, 12], [12, 19], [8, 15], [0, 8], [5, 11], [11, 17], [7, 14], [2, 8], [1, 7], [0, 6], [6, 12], [8, 13], [13, 19], [4, 9], [9, 14], [14, 18], [3, 11], [0, 4], [10, 15], [5, 10], [12, 16], [7, 12], [1, 5], [15, 19], [3, 8], [13, 17], [2, 6], [6, 11], [10, 13], [11, 15], [4, 7], [7, 10], [8, 12], [6, 9], [16, 18], [13, 16], [0, 3], [2, 4], [3, 6], [9, 11], [11, 14], [5, 8], [17, 19], [15, 17], [12, 15], [11, 13], [8, 11], [3, 5], [5, 7], [7, 9], [1, 3], [10, 12], [12, 14], [14, 16], [8, 10], [4, 6], [6, 8], [0, 2], [18, 19], [4, 5], [6, 7], [13, 15], [16, 17], [17, 18], [15, 16], [8, 9], [3, 4], [2, 3], [5, 6], [1, 2], [0, 1], [11, 12], [9, 11], [10, 11], [12, 13], [9, 10], [14, 15], [13, 14], [7, 8], [16, 17], [11, 12], [15, 16], [3, 4], [4, 5], [2, 3], [6, 7], [8, 9], [1, 2], [16, 17], [12, 13], [5, 6], [14, 15], [10, 11], [9, 10], [7, 8], [6, 7], [13, 14], [8, 9], [10, 11], [11, 12], [5, 6]]

**UPDATE**
A professor of computer science John Owens pointed out that there are different measures of sortedness that I will try to find some improvements, and also that these are covered under the name "sorting networks" in Donald Knuth's Art of Programming books, including how to tell whether one is optimal or not, so I'll be reading that and adding more to this idea later...