I have to design an algorithm to sort a list of orders by selection time (t selection, finding the good in the warehouse and bringing it to the surface) plus shipping time (t shipping, constant). The customer orders can be retrieved (in the same order as placed) from a server database
The program takes as input a data-set of orders where the id, t selection, and t shipping are of type unsigned int, n is the number of orders and a space character.
id1, t selection1, t shipping1; ...; idn, t selectionn, t shippingn \n
The expected output is a space-separated list of the ids, sorted by t selection + t shipping and terminated by a new line \n.
Input: 1, 500, 100; 2, 700, 100; 3, 100, 100\n
Output: 3 1 2\n
I have made this work with mergesort, however, my teacher also wants the ids to be sorted. for example, if there are 2 orders with the same sum of selection + shipping time, the smallest id should come first. see example
80001, 1000, 10; 70001, 1000, 100
my program still outputs the 80001 first, but 70001 should come first. I have provided my code below. Anyone that can help?
#!/usr/bin/env python3
import sys
class Order:
def __init__(self, id: int, selection_time: int, shipping_time: int):
self.id: int = id
self.selection_time: int = selection_time
self.shipping_time: int = shipping_time
def merge(lit):
def combi(order_):
return order_.selection_time + order_.shipping_time
if len(lit) > 1:
mid = len(lit) // 2
left = lit[:mid]
right = lit[mid:]
merge(left)
merge(right)
i = j = k = 0
while i < len(left) and j < len(right):
if combi(left[i]) < combi(right[j]):
lit[k] = left[i]
i += 1
else:
lit[k] = right[j]
j += 1
k += 1
for _i in range(i, len(left)):
lit[k] = left[_i]
k += 1
for _j in range(j, len(right)):
lit[k] = right[_j]
k += 1
return lit
if __name__ == '__main__':
'''
Retrieves and splits the input
'''
data = input()
data = data.split('; ')
order_list = []
for d in data:
id, selection_t, shipping_t = d.split(', ', 2)
order: Order = Order(int(id), int(selection_t), int(shipping_t))
order_list.append(order)
merge(order_list)
for order in order_list:
sys.stdout.write(str(order.id))
sys.stdout.write(" ")