SortLargestInterval

class corsort.SortLargestInterval(compute_history=False)

Adaptation of quicksort where we always sort the largest remaining interval.

Examples

>>> my_sort = SortLargestInterval(compute_history=True)
>>> my_xs = np.array([4, 1, 7, 6, 0, 8, 2, 3, 5])
>>> my_sort(my_xs).n_comparisons_
16
>>> my_sort.history_comparisons_  
[(1, 0), (0, 2), (0, 3), (4, 0), (0, 5), (6, 0), (7, 0), (0, 8),
(4, 1), (1, 6), (1, 7), (3, 2), (2, 5), (8, 2), (6, 7), (8, 3)]
>>> my_sort.history_distances_
[30, 30, 30, 30, 24, 24, 16, 8, 8, 6, 6, 6, 6, 6, 2, 2, 0]
>>> my_sort.sorted_list_
array([0, 1, 2, 3, 4, 5, 6, 7, 8])

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.