SortShell

class corsort.SortShell(compute_history=False, gap_sequence=None)[source]

Shellsort.

Examples

>>> shellsort = SortShell(compute_history=True)
>>> my_xs = np.array([4, 1, 7, 6, 0, 8, 2, 3, 5])
>>> shellsort(my_xs).n_comparisons_
22
>>> shellsort.history_comparisons_  
[(4, 0), (4, 5), (1, 5), (6, 2), (6, 7), (7, 3), (7, 8), (0, 8), (4, 1), (1, 6),
(6, 7), (7, 0), (0, 5), (2, 5), (0, 2), (3, 5), (3, 2), (0, 3), (8, 5), (8, 2), (8, 3), (0, 8)]
>>> shellsort.history_comparisons_values_  
[(0, 4), (0, 8), (1, 8), (2, 7), (2, 3), (3, 6), (3, 5), (4, 5), (0, 1), (1, 2),
(2, 3), (3, 4), (4, 8), (7, 8), (4, 7), (6, 8), (6, 7), (4, 6), (5, 8), (5, 7), (5, 6), (4, 5)]
>>> shellsort.history_distances_
[28, 32, 22, 20, 14, 12, 10, 8, 8, 8, 8, 8, 4, 8, 4, 6, 6, 4, 0, 0, 0, 0, 0]
>>> shellsort.sorted_list_
array([0, 1, 2, 3, 4, 5, 6, 7, 8])

>>> np.random.seed(42)
>>> shellsort = SortShell(compute_history=False)
>>> shellsort(np.random.permutation(100)).n_comparisons_
774

distance_to_sorted_array()[source]

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.