CorsortDelegate

class corsort.CorsortDelegate(sort, compute_history=False, record_leq=False, final_scorer=<function scorer_delta>)

Corsort that delegates the choice of pairwise comparisons to another sorting algorithm.

Parameters:

sort (Sort) – A sorting algorithm.

Examples

>>> corsort = CorsortDelegate(SortQuick(), compute_history=True)
>>> corsort(np.array(['e', 'b', 'a', 'c', 'd'])).n_comparisons_
8
>>> corsort.history_comparisons_
[(1, 0), (2, 0), (3, 0), (4, 0), (2, 1), (1, 3), (1, 4), (3, 4)]
>>> corsort.history_distances_
[8, 2, 2, 2, 2, 4, 2, 0, 0]
>>> corsort.__name__
'corsort_delegate_quicksort'

apply_i_lt_j(i, j)

Assuming perm[i] < perm[j], update the poset accordingly.

Parameters:

• i (int) – Index of the small item.

• j (int) – Index of the big item.

Examples

>>> corsort = Corsort()
>>> corsort.n_ = 4

Assume that we know perm[0] < perm[1], and perm[2] < perm[3]:

>>> corsort.leq_ = np.array([
...     [ 1,  1,  0,  0],
...     [-1,  1,  0,  0],
...     [ 0,  0,  1,  1],
...     [ 0,  0, -1,  1],
... ])

Assume we learn that perm[1] < perm[2]:

>>> corsort.apply_i_lt_j(1, 2)
>>> corsort.leq_
array([[ 1,  1,  1,  1],
       [-1,  1,  1,  1],
       [-1, -1,  1,  1],
       [-1, -1, -1,  1]])

Now we know the full order by transitivity.

compare_and_update_poset(i, j)

Perform a comparison between perm[i] and perm[j], and update the poset accordingly.

Parameters:

• i (int) – First index.

• j (int) – Second index.

distance_to_sorted_array()

Distance to sorted array.

Returns:

Distance between the current estimation and the sorted array.

Return type:

int

property history_comparisons_values_

History of the pairwise comparisons, in terms of compared values. Tuple (x, y) means that items of values x and y were compared, and that x < y.

Type:

list of tuple

next_compare()

Iterator of pairwise comparisons to make.

Returns:

An iterator of pairwise comparisons to make.

Return type:

iterable

test_i_lt_j(i, j)

Test whether perm[i] < perm[j].

Parameters:

• i (int) – First index.

• j (int) – Second index.

Returns:

True if item of index i is lower than item of index j.

Return type:

bool

Notes

The history of distance is computed just before the comparison. Hence it should be computed a last time at the end of the algorithm.

update_position_estimates()

Update position estimate of each item.

Examples

>>> corsort = Corsort(final_scorer=scorer_delta)
>>> corsort.n_ = 4
>>> corsort.leq_ = np.array([
...     [ 1,  1,  1,  1],
...     [-1,  1, -1, -1],
...     [-1,  1,  1,  0],
...     [-1,  1,  0,  1],
... ])
>>> corsort.update_position_estimates()
>>> corsort.position_estimates_
array([-3,  3,  0,  0])