sort_analyse.py

import random
from math import log

'''
findMaxDisplace = lambda array: \
    max(
        origIndex - sortedIndex \
        for sortedIndex, (origIndex, value) in \
        enumerate(
            sorted(
                enumerate(array),
                key=lambda x: x[1],
            )
        )
    )
'''

## MDR = Maximum Displace Ratio

findSortedRatio = lambda array: \
    max(
        origIndex - sortedIndex \
        for sortedIndex, (origIndex, value) in \
        enumerate(
            sorted(
                enumerate(array),
                key=lambda x: x[1],
            )
        )
    )/float(
        (len(array) - 1) ** 1.02
    )


if __name__=='__main__':
    print '%8s  %10s'%('length', 'avgSR')
    tryTimes = 10000
    for length in xrange(100, 100000, 100):
        array = list(range(length))
        #SR = 1 - MDR
        sumSR = 0
        for _ in range(tryTimes):
            random.shuffle(array)
            sumSR += findSortedRatio(array)
        avgSR = float(sumSR) / tryTimes
        print '%8s  %10.6f'%(length, avgSR)