jit_sorts

corsort.jit_sorts.heapify(arr, n, i, states, scores, comparisons)

Based on a code by Mohit Kumra: https://www.geeksforgeeks.org/python-program-for-heap-sort/

corsort.jit_sorts.jit_corsort_borda(perm)

Corsort designed for low total number of comparison. Not efficient in terms of convergence trajectory.

Parameters:

perm (ndarray) – A random permutation.

Returns:

• states (list of ndarray) – List of estimates of the sorted result.

• scores (list of ndarray) – List of estimates of the importance of each item.

• comparisons (list of tuple) – List of performed comparison. Each element is a tuple (index of lower item, index of higher item).

Examples

>>> np.random.seed(42)
>>> p = np.random.permutation(10)
>>> st, sc, co = jit_corsort_borda(p)
>>> st[0]
array([8, 1, 5, 0, 7, 2, 9, 4, 3, 6])
>>> st[10]
array([0, 2, 1, 4, 5, 3, 6, 7, 8, 9])
>>> st[-1]
array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> p[:5]
array([8, 1, 5, 0, 7])
>>> sc[0][:5]
array([0, 0, 0, 0, 0])
>>> sc[10][:5]
array([ 5, -3,  0, -5,  3])
>>> sc[-1][:5]
array([ 7, -7,  1, -9,  5])
>>> len(co)
22

corsort.jit_sorts.jit_corsort_delta_max_delta(perm)

Corsort with delta core scorer, max-knowledge tie-break, and delta output scorer.

Parameters:

perm (ndarray) – A random permutation.

Returns:

• states (list of ndarray) – List of estimates of the sorted result.

• scores (list of ndarray) – List of estimates of the importance of each item.

• comparisons (list of tuple) – List of performed comparison. Each element is a tuple (index of lower item, index of higher item).

Examples

>>> np.random.seed(42)
>>> p = np.random.permutation(10)
>>> st, sc, co = jit_corsort_delta_max_delta(p)
>>> st[0]
array([8, 1, 5, 0, 7, 2, 9, 4, 3, 6])
>>> st[10]
array([0, 1, 2, 4, 3, 6, 5, 7, 8, 9])
>>> st[-1]
array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> p[:5]
array([8, 1, 5, 0, 7])
>>> sc[0][:5]
array([0, 0, 0, 0, 0])
>>> sc[10][:5]
array([ 4, -4,  2, -5,  2])
>>> sc[-1][:5]
array([ 7, -7,  1, -9,  5])
>>> len(co)
22

corsort.jit_sorts.jit_corsort_delta_max_rho(perm)

Corsort with delta core scorer, max-knowledge tie-break, and rho output scorer. Currently, the best corsort for trajectory.

Parameters:

perm (ndarray) – A random permutation.

Returns:

• states (list of ndarray) – List of estimates of the sorted result.

• scores (list of ndarray) – List of estimates of the importance of each item.

• comparisons (list of tuple) – List of performed comparison. Each element is a tuple (index of lower item, index of higher item).

Examples

>>> np.random.seed(42)
>>> p = np.random.permutation(10)
>>> st, sc, co = jit_corsort_delta_max_rho(p)
>>> st[0]
array([8, 1, 5, 0, 7, 2, 9, 4, 3, 6])
>>> st[10]
array([0, 1, 2, 4, 3, 6, 5, 7, 8, 9])
>>> st[-1]
array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> p[:5]
array([8, 1, 5, 0, 7])
>>> sc[0][:5]
array([0.5, 0.5, 0.5, 0.5, 0.5])
>>> sc[10][:5]
array([0.83333333, 0.16666667, 0.66666667, 0.14285714, 0.75      ])
>>> sc[-1][:5]
array([0.81818182, 0.18181818, 0.54545455, 0.09090909, 0.72727273])
>>> len(co)
22

corsort.jit_sorts.jit_corsort_delta_sum_delta(perm)

Corsort with delta core scorer, sum-knowledge tie-break, and delta output scorer.

Parameters:

perm (ndarray) – A random permutation.

Returns:

• states (list of ndarray) – List of estimates of the sorted result.

• scores (list of ndarray) – List of estimates of the importance of each item.

• comparisons (list of tuple) – List of performed comparison. Each element is a tuple (index of lower item, index of higher item).

Examples

>>> np.random.seed(42)
>>> p = np.random.permutation(10)
>>> st, sc, co = jit_corsort_delta_sum_delta(p)
>>> st[0]
array([8, 1, 5, 0, 7, 2, 9, 4, 3, 6])
>>> st[10]
array([0, 1, 2, 4, 3, 6, 5, 7, 8, 9])
>>> st[-1]
array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> p[:5]
array([8, 1, 5, 0, 7])
>>> sc[0][:5]
array([0, 0, 0, 0, 0])
>>> sc[10][:5]
array([ 4, -4,  2, -5,  2])
>>> sc[-1][:5]
array([ 7, -7,  1, -9,  5])
>>> len(co)
21

corsort.jit_sorts.jit_corsort_delta_sum_rho(perm)

Corsort with delta core scorer, sum-knowledge tie-break, and rho output scorer.

Parameters:

perm (ndarray) – A random permutation.

Returns:

• states (list of ndarray) – List of estimates of the sorted result.

• scores (list of ndarray) – List of estimates of the importance of each item.

• comparisons (list of tuple) – List of performed comparison. Each element is a tuple (index of lower item, index of higher item).

Examples

>>> np.random.seed(42)
>>> p = np.random.permutation(10)
>>> st, sc, co = jit_corsort_delta_sum_rho(p)
>>> st[0]
array([8, 1, 5, 0, 7, 2, 9, 4, 3, 6])
>>> st[10]
array([0, 1, 2, 4, 3, 6, 5, 7, 8, 9])
>>> st[-1]
array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> p[:5]
array([8, 1, 5, 0, 7])
>>> sc[0][:5]
array([0.5, 0.5, 0.5, 0.5, 0.5])
>>> sc[10][:5]
array([0.83333333, 0.16666667, 0.66666667, 0.14285714, 0.75      ])
>>> sc[-1][:5]
array([0.81818182, 0.18181818, 0.54545455, 0.09090909, 0.72727273])
>>> len(co)
21

corsort.jit_sorts.jit_corsort_rho_max_delta(perm)

Corsort with rho core scorer, max-knowledge tie-break, and delta output scorer.

Parameters:

perm (ndarray) – A random permutation.

Returns:

• states (list of ndarray) – List of estimates of the sorted result.

• scores (list of ndarray) – List of estimates of the importance of each item.

• comparisons (list of tuple) – List of performed comparison. Each element is a tuple (index of lower item, index of higher item).

Examples

>>> np.random.seed(42)
>>> p = np.random.permutation(10)
>>> st, sc, co = jit_corsort_rho_max_delta(p)
>>> st[0]
array([8, 1, 5, 0, 7, 2, 9, 4, 3, 6])
>>> st[10]
array([0, 1, 2, 4, 3, 6, 5, 7, 8, 9])
>>> st[-1]
array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> p[:5]
array([8, 1, 5, 0, 7])
>>> sc[0][:5]
array([0, 0, 0, 0, 0])
>>> sc[10][:5]
array([ 4, -4,  2, -5,  2])
>>> sc[-1][:5]
array([ 7, -7,  1, -9,  5])
>>> len(co)
23

corsort.jit_sorts.jit_corsort_rho_max_rho(perm)

Corsort with rho core scorer, max-knowledge tie-break, and rho output scorer.

Parameters:

perm (ndarray) – A random permutation.

Returns:

• states (list of ndarray) – List of estimates of the sorted result.

• scores (list of ndarray) – List of estimates of the importance of each item.

• comparisons (list of tuple) – List of performed comparison. Each element is a tuple (index of lower item, index of higher item).

Examples

>>> np.random.seed(42)
>>> p = np.random.permutation(10)
>>> st, sc, co = jit_corsort_rho_max_rho(p)
>>> st[0]
array([8, 1, 5, 0, 7, 2, 9, 4, 3, 6])
>>> st[10]
array([0, 1, 2, 4, 3, 6, 5, 7, 8, 9])
>>> st[-1]
array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> p[:5]
array([8, 1, 5, 0, 7])
>>> sc[0][:5]
array([0.5, 0.5, 0.5, 0.5, 0.5])
>>> sc[10][:5]
array([0.83333333, 0.16666667, 0.66666667, 0.14285714, 0.75      ])
>>> sc[-1][:5]
array([0.81818182, 0.18181818, 0.54545455, 0.09090909, 0.72727273])
>>> len(co)
23

corsort.jit_sorts.jit_corsort_rho_sum_delta(perm)

Corsort with rho core scorer, sum-knowledge tie-break, and delta output scorer.

Parameters:

perm (ndarray) – A random permutation.

Returns:

• states (list of ndarray) – List of estimates of the sorted result.

• scores (list of ndarray) – List of estimates of the importance of each item.

• comparisons (list of tuple) – List of performed comparison. Each element is a tuple (index of lower item, index of higher item).

Examples

>>> np.random.seed(42)
>>> p = np.random.permutation(10)
>>> st, sc, co = jit_corsort_rho_sum_delta(p)
>>> st[0]
array([8, 1, 5, 0, 7, 2, 9, 4, 3, 6])
>>> st[10]
array([0, 1, 2, 4, 3, 6, 5, 7, 8, 9])
>>> st[-1]
array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> p[:5]
array([8, 1, 5, 0, 7])
>>> sc[0][:5]
array([0, 0, 0, 0, 0])
>>> sc[10][:5]
array([ 4, -4,  2, -5,  2])
>>> sc[-1][:5]
array([ 7, -7,  1, -9,  5])
>>> len(co)
21

corsort.jit_sorts.jit_corsort_rho_sum_rho(perm)

Corsort with rho core scorer, sum-knowledge tie-break, and rho output scorer.

Parameters:

perm (ndarray) – A random permutation.

Returns:

• states (list of ndarray) – List of estimates of the sorted result.

• scores (list of ndarray) – List of estimates of the importance of each item.

• comparisons (list of tuple) – List of performed comparison. Each element is a tuple (index of lower item, index of higher item).

Examples

>>> np.random.seed(42)
>>> p = np.random.permutation(10)
>>> st, sc, co = jit_corsort_rho_sum_rho(p)
>>> st[0]
array([8, 1, 5, 0, 7, 2, 9, 4, 3, 6])
>>> st[10]
array([0, 1, 2, 4, 3, 6, 5, 7, 8, 9])
>>> st[-1]
array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> p[:5]
array([8, 1, 5, 0, 7])
>>> sc[0][:5]
array([0.5, 0.5, 0.5, 0.5, 0.5])
>>> sc[10][:5]
array([0.83333333, 0.16666667, 0.66666667, 0.14285714, 0.75      ])
>>> sc[-1][:5]
array([0.81818182, 0.18181818, 0.54545455, 0.09090909, 0.72727273])
>>> len(co)
21

corsort.jit_sorts.jit_heapsort(arr)

Heap sort.

:param arr:class:~numpy.ndarray: A random permutation.

Returns:

• states (list of ndarray) – List of estimates of the sorted result.

• scores (list of ndarray) – List of estimates of the importance of each item.

• comparisons (list of tuple) – List of performed comparison. Each element is a tuple (index of lower item, index of higher item).

Examples

>>> np.random.seed(42)
>>> p = np.random.permutation(10)
>>> st, sc, co = jit_heapsort(p)