SortFordJohnson

class corsort.SortFordJohnson(compute_history=False)[source]

Ford-Johnson sorting algorithm.

Examples

>>> fj_sort = SortFordJohnson(compute_history=False)
>>> perm = np.array([14, 2, 0, 10, 13, 5, 18, 19, 7, 12, 6, 15, 16, 1, 3, 4, 8, 17, 11, 9])
>>> fj_sort(perm).n_comparisons_
60
>>> fj_sort.perm_  
array([14,  2,  0, 10, 13,  5, 18, 19,  7, 12,  6, 15, 16,  1,  3,  4,  8,  17, 11,  9])
>>> fj_sort.sorted_list_  
array([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19])

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.