Skip to content

Instantly share code, notes, and snippets.

Last active Oct 3, 2022
What would you like to do?
average number of queries to sort
import numpy as np
import random
class Oracle():
def __init__(self, n, replace = True):
self.n = n
self.count = 0
self.replace = replace
self.returned = []
def query(self):
# draw random pair of distinct elements
while True:
i, j = random.sample(range(self.n), 2)
ordered = (i, j) if i < j else (j, i)
if self.replace or ordered not in self.returned:
if not self.replace:
self.count += 1
return ordered
def test(n, replace = True):
oracle = Oracle(n, replace)
smaller = np.eye(n)
while True:
i, j = oracle.query()
smaller[i, j] = 1
# transitive closure
for k in range(n):
for i in range(n):
for j in range(n):
if smaller[i, k] and smaller[k, j]:
smaller[i, j] = 1
if np.all(smaller + smaller.T > 0):
return oracle.count
if __name__ == "__main__":
for i in range(2, 20):
tests = np.array([test(i) for _ in range(10000)])
print('w/ replace', i, tests.mean(), tests.std() / np.sqrt(len(tests)))
for i in range(2, 20):
tests = np.array([test(i, replace=False) for _ in range(10000)])
print('wo replace', i, tests.mean(), tests.std() / np.sqrt(len(tests)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment