SortBinaryInsertion

class corsort.SortBinaryInsertion(compute_history=False)

Binary insertion sort.

Examples

>>> binary_insertion_sort = SortBinaryInsertion(compute_history=True)
>>> my_xs = np.array([4, 1, 7, 6, 0, 8, 2, 3, 5])
>>> binary_insertion_sort(my_xs).n_comparisons_
19
>>> binary_insertion_sort.history_comparisons_  
[(1, 0), (1, 2), (0, 2), (0, 3), (3, 2), (4, 0), (4, 1), (0, 5), (3, 5), (2, 5),
(6, 0), (4, 6), (1, 6), (7, 0), (1, 7), (6, 7), (7, 8), (8, 3), (0, 8)]
>>> binary_insertion_sort.history_comparisons_values_  
[(1, 4), (1, 7), (4, 7), (4, 6), (6, 7), (0, 4), (0, 1), (4, 8), (6, 8), (7, 8),
(2, 4), (0, 2), (1, 2), (3, 4), (1, 3), (2, 3), (3, 5), (5, 6), (4, 5)]
>>> binary_insertion_sort.history_distances_
[30, 30, 30, 30, 30, 30, 30, 22, 22, 22, 22, 22, 22, 14, 14, 14, 6, 6, 6, 0]
>>> binary_insertion_sort.sorted_list_
array([0, 1, 2, 3, 4, 5, 6, 7, 8])

>>> np.random.seed(42)
>>> binary_insertion_sort = SortBinaryInsertion(compute_history=False)
>>> binary_insertion_sort(np.random.permutation(100)).n_comparisons_
537

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

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.