BaieSort

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

Merge sort, Baie version (BFS + dedicated scorer).

Examples

>>> baie_sort = SortBaie(compute_history=True)
>>> my_xs = np.array([4, 1, 7, 6, 0, 8, 2, 3, 5])
>>> baie_sort(my_xs).n_comparisons_
19
>>> baie_sort.history_comparisons_  
[(7, 8), (1, 0), (3, 2), (4, 5), (6, 7), (1, 3), (4, 6), (0, 3), (6, 5),
(7, 5), (8, 5), (4, 1), (1, 6), (6, 0), (7, 0), (0, 8), (8, 3), (3, 5), (2, 5)]
>>> baie_sort.history_distances_
[30, 28, 28, 22, 16, 16, 14, 14, 10, 8, 8, 4, 4, 4, 4, 2, 2, 2, 0, 0]
>>> baie_sort.sorted_list_
array([0, 1, 2, 3, 4, 5, 6, 7, 8])

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.

corsort.sort_baiesort.aux_split(lot)[source]

Compute the next layer of a tree merge.

Parameters:: lot (list of tuple) – A layer of a tree merge.
Returns:: The next layer of a tree merge.
Return type:: list of tuple

corsort.sort_baiesort.split(n)[source]

Parameters:: n (int) – Size of the list to sort.
Returns:: The merges to perform by increasing layer. Each merge is a tuple (s, m, e), meaning that the left part of the merge are indices s:m and the right part of the merge are indices m:e. The first element of the list has always one unique element, the final merge (root of the merge tree). The last element of the list indicates the lowest merges (2-merges at the bottom of the tree).
Return type:: list of list of tuple

Examples

With 2 elements, you just merge them.

>>> split(2)
[[(0, 1, 2)]]

With 10 elements, it gets a bit more complicated.

>>> split(10)
[[(0, 5, 10)], [(0, 2, 5), (5, 7, 10)], [(0, 1, 2), (2, 3, 5), (5, 6, 7), (7, 8, 10)], [(3, 4, 5), (8, 9, 10)]]

Interpretation:

In the end (layer 0), you will merge sorted elements of indices 0 to 4 with sorted elements of indices 5 to 9;
Layer 1: merge [0, 1] with [2, 3, 4], merge [5, 6] with [7, 8, 9];
Layer 2: [0] and [1], [2] and [3, 4], [5] and [6], [7] and [8, 9];
Layer 3: [3] and [4], [8] and [9].