7
\$\begingroup\$

To further generalize the algorithm (past the doc string): Given a list E(1) E(3) E(2) E(4) _ E(0) _ where E(N + 1) is ahead of E(N) when sorted and _ represents a "static element" (that is, an element whose index and value will remain unchanged despite the sorting), the list returned should be E(0) E(1) E(2) E(3) _ E(4) _.

In the following code, non-static elements would be the elements affected by the sorting, while a static element would be unaffected (i.e, an _).

def static_sort(old_list: list, static_index_list: list) -> list:
    """
    Returns a list whose non-static elements (defined to be the ones whose
    indexes are not specified in the static_index_list) are sorted in ascending order.
    The static elements (with indexes specified in the static_index_list) remain unchanged
    in both numeric value and index in the original list.

    static_sort([1, 9, 3, 5], [0, 2]) -> [1, 5, 3, 9]
    static_sort([0, 8, 2, 6], [2]) -> [0, 6, 2, 8]

    :param static_index_list: A list of indexes whose associated elements in
    old_list should be exclusive of the sorting in the rest of the list.
    :param old_list: The unsorted list, to-be sorted using the comparator and
    static_index_list.
    """

    sorted_list = []
    non_sort_subjects = list(map(lambda static_index: old_list[static_index], static_index_list))

    def sort_subject_filter(element):
        return element not in non_sort_subjects

    sort_subjects = sorted(list(filter(sort_subject_filter, old_list)))

    whole_index = sort_subject_index = 0
    while whole_index < len(old_list):
        if whole_index in static_index_list:
            sorted_list.append(non_sort_subjects[whole_index - sort_subject_index])
        else:
            sorted_list.append(sort_subjects[sort_subject_index])
            sort_subject_index += 1
        whole_index += 1

    return sorted_list

Reviews on the algorithm itself in addition to formatting/code style are appreciated.

\$\endgroup\$
4
\$\begingroup\$

There are a few things you don't say that might be important. First, is it a requirement that the inputs be lists? Or coincidence? Must the return value be the same list, or must it be a different list? Is the function permitted or expected to modify the input list? Is it prohibited from doing so?

I'd suggest you reset your expected inputs to be Iterables, rather than lists. It's more general.

Similarly, let's assume that your function behaves much like sorted and returns a totally different list, without modifying either of the inputs.

You spend some time and effort to filter the non-sorted values away from the sorted values. You don't specify how large you expect either of the two inputs to be, but if they are very large this might be inefficient. I suggest you create a sort key that is a tuple, and use that to sort the non-sorted values to one end of the result:

if not static_index_list:
    return sorted(old_list)

ignored = set(static_index_list)
subjects = sorted(range(len(old_list)), key=lambda i: (i in ignored, old_list[i]))

Python sorts False before True, so the ignored values will be the topmost N values. Cut them off:

subjects = subjects[0:-len(static_index_list)]

Now you have tuples where you can ignore the [0] element, and the [1] element is the index value. You can either make a pass to replace the indexes with values, and then merge the static and dynamic lists, or you could do it all in one pass. I suspect that the sizes of the inputs will determine which is the right solution: for very large inputs, especially with smallish static_index_lists, using bulk operators (array slices) is worth getting right - that is, figuring out how to do result.append(sorted_subject[start+offset:end+offset]). On the other hand, for short lists, the single while loop that merges like you have now may be faster, or at least fast enough.

\$\endgroup\$
5
\$\begingroup\$

Limitations

The implementation will not work well for certain inputs with duplicate values. The spec doesn't say that there won't be duplicate values, so you should not assume that.

This limitation can be fixed by excluding items to sort by index instead of value.

Performance

element not in non_sort_subjects and whole_index in static_index_list will be linear searches, since non_sort_subjects and static_index_list are lists. A simple improvement would be to search in sets.

\$\endgroup\$
2
\$\begingroup\$

Instead of creating a new list to merge the two subresults, you could insert back the static elements into the sorted list. If the number of static elements is low, this could be faster than all those append:

def static_sort (elements, static_indexes):
    static_indexes = set (static_indexes)
    result = sorted (e for i, e in enumerate(elements) if i not in static_indexes)

    for index in sorted(static_indexes):
        result.insert(index, elements[index])
    return result

As an alternative to your implementation, you could take whole slices of the sorted elements at once rather than single elements:

def static_sort (elements, static_indexes):
    static_indexes = set (static_indexes)
    sorted_elements = sorted (e for i, e in enumerate(elements) if i not in static_indexes)

    result = []
    old_index = 0
    for i, index in enumerate(sorted(static_indexes)):
        static_element = elements[index]
        index -= i  # compensate for filtered elements
        result.extend(sorted_elements[old_indeed:index])
        result.append(static_element)
        old_index = index

    result.extend(sorted_elements[old_index:])
    return result
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.