+ 1

# Sorting Algorithm

Sorting Algorithm w/ multiple lists Suppose I am given a sorting algorithm which I cannot modify. This algorithm accepts an input list and outputs a sorted list. Now, I have multiple lists of integers to be sorted separately. How can I pre-process the given lists and post-process the sorted data using the given algorithm only once? Note: it must be at most linear time for the processing.

4 Answers

+ 1

If you use Python sorting, it's super simple. If you have another function provided, it would be simple to convert this to use that other algorythm. But it's confusing because you said you can only sort once and then said you need three different sorts. So I'm not sure if this does what you want or not.
list1 = [5,3,4,1,2]
list2 = [9,5,1,6,8,7]
list3 = list1 + list2
list1.sort()
list2.sort()
list3.sort()
print(list1)
print(list2)
print(list3)
What's not clear is how to make it more linear because you need to sort several lists. If this is your school homework, your teacher probably provided more instruction than that.

+ 1

Jerry Hobby Thank you. I’ve 2 or multiple separate lists but can only use the sorting algorithm, which I have no control over, ONLY ONCE.

+ 1

@coip I have created a program for you that does what you described. You should be able to adapt it to your needs or at least get ideas from it. It takes multiple lists as input, sorts them in one sort operation, and outputs all the sorted data. It accomplishes this by combining the lists together, with an index, then extracting the sorted data back to the original arrays, but sorted.
https://code.sololearn.com/cA20A12a24a2

0

i solved the problem by using disjoint union set ✔️