kclee6880
BAN USERThe idea is similar to merge sort, which is to merge the 2 sorted arrays into one big array. The first subarray is all the elements merged thus far. The second subarray is the 2 2-tuples obtained by the 3-tuple. It will always be a subarray of two elements.
The sorting algorithm would first construct a temp array that holds the two halves. It will then compare the first element of the two halves and picks the smaller of the two halves into the first position of the resulting sorted array. It then advances the pointer of the half A from which the first element is drawn and compares the next element of A with the first element of the other half. It continues this until the pointer passes the length of either two halves. The remaining elements in the first half will then be placed at the end one after another. Since they are already sorted, they need not be sorted.
Following is the code:
def sort_three_tuples(three_tuples):
first_three_tuple = three_tuples[0]
# put the first 2 tuples from first_three_tuples into the result array
# first
result = [(first_three_tuple[0], first_three_tuple[1]), (first_three_tuple[0], first_three_tuple[2])]
del three_tuples[0]
for three_tuple in three_tuples:
first_tuple = (three_tuple[0], three_tuple[1])
second_tuple = (three_tuple[0], three_tuple[2])
# left will iterate up to, not including, middle
middle = len(result)
left = 0
# right will iterate from middle
right = middle
# + 2 because there is always two tuples added to the existing sorted
# tuples
tot = middle + 2
# store result temporarily in temp first
temp = result + [first_tuple, second_tuple]
# this makes sure result has the same size as temp
result = temp
cur = 0
# now compare the first half with the second half
while left < middle and right < tot:
if temp[left][1] > temp[right][1]:
#print cur, right
result[cur] = temp[right]
cur = cur + 1
right = right + 1
else:
result[cur] = temp[left]
cur = cur + 1
left = left + 1
# remaining will keep track of how many of remaining elements in the
# left half that need to be copied into the result array
# if remaining = 0, there is nothing to copy and we are done sorting
remaining = middle - left
for i in xrange(0, remaining):
result[cur] = temp[left]
cur = cur + 1
left = left + 1
return result
print sort_three_tuples([('a', 1, 5), ('b', 2, 4), ('c', 7, 8)])
Assuming there are N 3-tuples. First time, it will take O(4) because we will have to move at most 4 elements (2 elements from the right and 2 from the left). Second, it will take at most 6 elements (2 elements from the right and 4 from the left). Third, it will take at most 8 elements (2 elements from the right and 6 from the left). The pattern is 2 + 4 + 6 + 8 + N*2 = 2(1+2+3+…(N-1)+N) = O(N^2).
- kclee6880 October 13, 2014
Doesn't work for
- kclee6880 October 13, 2014{{
print sortTuples([('a', 2, 8), ('b', 1, 7)])
}}