data-structures-algorithms-python/5.py at master · RohanSaxena2020/data-structures-algorithms-python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
# ### Merge Sort Exercise

# Modify [merge_sort function](https://github.com/codebasics/data-structures-algorithms-python/blob/master/algorithms/5_MergeSort/merge_sort_final.py) such that it can sort following list of athletes as per the time taken by them in the marathon,
# ```
# elements = [
#         { 'name': 'vedanth',   'age': 17, 'time_hours': 1},
#         { 'name': 'rajab', 'age': 12,  'time_hours': 3},
#         { 'name': 'vignesh',  'age': 21,  'time_hours': 2.5},
#         { 'name': 'chinmay',  'age': 24,  'time_hours': 1.5},
#     ]
# ```
# merge_sort function should take key from an athlete's marathon log and sort the list as per that key. For example,
# ```
# merge_sort(elements, key='time_hours', descending=True)
# ```
# This will sort elements by time_hours and your sorted list will look like,
# ```
# elements = [
#         {'name': 'rajab', 'age': 12, 'time_hours': 3},
#         {'name': 'vignesh', 'age': 21, 'time_hours': 2.5},
#         {'name': 'chinmay', 'age': 24, 'time_hours': 1.5},
#         {'name': 'vedanth', 'age': 17, 'time_hours': 1},
#     ]
# ```
# But if you call it like this,
# ```
# merge_sort(elements, key='name')
# ```
# output will be,
# ```
# elements = [
#         { 'name': 'chinmay',   'age': 24, 'time_hours': 1.5},
#         { 'name': 'rajab', 'age': 12,  'time_hours': 3},
#         { 'name': 'vedanth',  'age': 17,  'time_hours': 1},
#         { 'name': 'vignesh',  'age': 21,  'time_hours': 2.5},
#     ]
# ```

# [Solution](https://github.com/codebasics/data-structures-algorithms-python/blob/master/algorithms/5_MergeSort/merge_sort_exercise_solution.py)

# def merge_sort(arr):
#     if len(arr) <= 1:
#         return

#     mid = len(arr)//2

#     left = arr[:mid]
#     right = arr[mid:]

#     merge_sort(left)
#     merge_sort(right)

#     merge_two_sorted_lists(left, right, arr)

# def merge_two_sorted_lists(a,b,arr):
#     len_a = len(a)
#     len_b = len(b)

#     i = j = k = 0

#     while i < len_a and j < len_b:
#         if a[i] <= b[j]:
#             arr[k] = a[i]
#             i+=1
#         else:
#             arr[k] = b[j]
#             j+=1
#         k+=1

#     while i < len_a:
#         arr[k] = a[i]
#         i+=1
#         k+=1

#     while j < len_b:
#         arr[k] = b[j]
#         j+=1
#         k+=1

# def merge_two_sorted_by_key(a,b,arr,key):
#     len_a = len(a)
#     len_b = len(b)

#     i = j = k = 0

#     while i < len_a and j < len_b:
#         if a[i][key] <= b[j][key]:
#             arr[k] = a[i]
#             i+=1
#         else:
#             arr[k] = b[j]
#             j+=1
#         k+=1

#     while i < len_a:
#         arr[k] = a[i]
#         i+=1
#         k+=1

#     while j < len_b:
#         arr[k] = b[j]
#         j+=1
#         k+=1

def merge_sort_by_key(arr, key,descending=False):
    if len(arr) <= 1:
        return arr

    mid = len(arr)//2

    left = arr[:mid]
    right = arr[mid:]

    left = merge_sort_by_key(left,key,descending)
    right = merge_sort_by_key(right,key,descending)

    return merge_two_sorted_lists_by_key(left, right,key,descending)

def merge_two_sorted_lists_by_key(a,b,key,descending):
    sorted_list = []

    len_a = len(a)
    len_b = len(b)

    i = j = 0

    while i < len_a and j < len_b:
        if descending:
            condition = a[i][key] > b[j][key]  # Note the change here for descending
        else:
            condition = a[i][key] <= b[j][key]

        if condition:
            sorted_list.append(a[i])
            i += 1
        else:
            sorted_list.append(b[j])
            j += 1

    while i < len_a:
        sorted_list.append(a[i])
        i+=1

    while j < len_b:
        sorted_list.append(b[j])
        j+=1

    return sorted_list


elements = [
    { 'name': 'vedanth',   'age': 17, 'time_hours': 1},
    { 'name': 'rajab', 'age': 12,  'time_hours': 3},
    { 'name': 'vignesh',  'age': 21,  'time_hours': 2.5},
    { 'name': 'chinmay',  'age': 24,  'time_hours': 1.5},
   ]

print(merge_sort_by_key(elements,key="age",descending=False))