Wednesday, June 3, 2015

Prime sort

My idea was considering you have a list L of N items, and a list of primes P1...Q including 1, listed in reverse order like so:

Here Q is 89...
[89,83, 79, 73, 71, 67, 63, 61, 59, 53, 47, 43, 41, 37, 31, 29,23,19, 17,13, 11, 7, 5, 3, 2, 1]

My algorithm first compares every number up to N-P1 in L at position i to the number at position i+P1 , so in the example above it would compare the first item in the list at i=0 to the 89th, the i=1 number to 90, up to N-89 and N.

This is then done for every P on the list, and I found that with Q = 89 this could sort all of the random lists I tried of 1000 items,

Q varies somehow with N, I found that

N        Q
32       13
100     23
1000   89

It seems to me that the relationship might be that the number of primes in the list P should be around the square root of N...

The single threaded source code listed below is very simple, but it's actually possible to make a concurrent version where the prime P(j) loop starts as soon as the i counter for the P(j-1) loop is P(j-1)+1 through the list... So potentially many "waves" of comparisons could be going through the list simultaneously...

**For tournaments**

I think it might be good for a tournament at some game, but one where the total number of matches played for a person is minimized over the need to play concurrent matches, and where the most important thing is to make as many good matches as possible. Because each round everyone has a chance to climb up the ladder as far as they can go, and the people they're playing would generally be getting closer and closer to the same skill level as the rounds progressed making for better and better matches, Some concurrency is possible as the jth round of matches can start as soon as the prior round's i counter is P(j-1) up the list, and so on until many rounds are travelling like waves through the list... Mathematically there is the potential for someone to work their way up the ladder 1 step at a time from the bottom to the top, but statistically that's improbable as they wouldn't be that far down the ladder by the last round if they were good enough to win so many consecutive matches against increasingly tough opponents. The nature of this algorithm is that losing wouldn't punish anyone too much; they could still end up winning the whole tournament overall no matter where they are in the randomized list in the final round though it's easier to climb early on...And losing later and later on matters less and less to the person's final ranking... Adding a couple rounds over what's strictly necessary for the ideal case of numbers accentuates the fairness of the final ranking...
Source Code:
import random
def swap(l, i, ip):
    if l[i] > l[ip]:
        temp = l[ip]
        l[ip] = l[i]
        l[i] = temp        
def main():
    l = []
    for i in range(0, 1000):
    p = [89,83, 79, 73, 71, 67, 63, 61, 59, 53, 47, 43, 41, 37, 31, 29,23,19, 17,13, 11, 7, 5, 3, 2, 1]
    for prime in p:
        for i in range(0, 1000-prime):
            swap(l, i, i+prime)

No comments:

Post a Comment