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. You should expect between 100-10K elements.
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 am trying to do it with merge sort, however my program returns
1 2 3/n instead of 3 1 2/n
I have provided my code below, could anyone help me out?
#!/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(left, right):
if not len(left) or not len(right):
return left or right
result = []
i, j = 0, 0
while len(result) < len(left) + len(right):
if left[i].shipping_time + left[i].selection_time < right[j].shipping_time + right[j].selection_time:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
if i == len(left) or j == len(right):
result.extend(left[i:] or right[j:])
break
return result
def sort(list):
if len(list) < 2:
return list
middle = int(len(list) / 2)
left = sort(list[:middle])
right = sort(list[middle:])
return merge(left, right)
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)
sort(order_list)
for order in order_list:
sys.stdout.write(str(order.id))
sys.stdout.write(" ")
The simplest (and probably least efficient) sorting algorithm is the Bubble sort. But the question says nothing about performance so it can be simplified like this:
class Order:
def __init__(self, ident, selection_time, shipping_time):
self._ident = ident
self._selection_time = selection_time
self._shipping_time = shipping_time
@property
def selection_time(self):
return self._selection_time
@property
def shipping_time(self):
return self._shipping_time
@property
def ident(self):
return self._ident
def merge(lst):
def comboval(order):
return order.selection_time + order.shipping_time
if len(lst) > 1:
mid = len(lst) // 2
left = lst[:mid]
right = lst[mid:]
merge(left)
merge(right)
i = j = k = 0
while i < len(left) and j < len(right):
if comboval(left[i]) < comboval(right[j]):
lst[k] = left[i]
i += 1
else:
lst[k] = right[j]
j += 1
k += 1
for _i in range(i, len(left)):
lst[k] = left[_i]
k += 1
for _j in range(j, len(right)):
lst[k] = right[_j]
k += 1
return lst
inval = '1, 500, 100; 2, 700, 100; 3, 100, 100'
orderlist = []
for order in inval.split(';'):
orderlist.append(Order(*map(int, order.split(','))))
print(*[order.ident for order in merge(orderlist)])
Output:
3 1 2
Note:
This is an in-place sort