SortQuick

class corsort.SortQuick(compute_history=False)

Quicksort.

Examples

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

>>> np.random.seed(42)
>>> quicksort = SortQuick(compute_history=False)
>>> quicksort(np.random.permutation(100)).n_comparisons_
662

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.