After courageously overcoming my own human error. I got the merge sort algorithm to work correctly. It took an unordered array/list of numbers and returned a new array that contained those same numbers but sorted in ascending order. I am super happy I was able to make some progress with this. Step by step I’ll get some more reps in and grow stronger MUHAHAHAHAHA
TLDR;
Okay, so here are the highlights of what I did:
- Data structures -> Continued going through another freeCodeCamp YouTube video covering data structures and algorithms for beginners. I finally understand how the Merge Sort algorithm works. It took some time to write out the code and run it. Once I got through my own human error, I was able to understand how it goes.
Merge Sort Code
def merge_sort(list):
"""
Sorts a list in ascending order
Returns a new sorted list
Divide: Find the midpoint of the list and divide into two sublists
Conquer: Recursively sort the sublists created in previous step
Combine: Merge the sorted sublists created in previous step
"""
if len(list) <= 1:
return list
left_half, right_half = split(list)
left = merge_sort(left_half)
right = merge_sort(right_half)
return merge(left, right)
def split(list):
"""
Divide the unsorted list at midpoint into sublists
Returns two sublists - left and right
"""
mid = len(list)//2
left = list[:mid]
right = list[mid:]
return left, right
def merge(left, right):
"""
Merges two lists (arrays), sorting them in the process
Returns a new merged list
"""
print("left list: ", left)
print("right list: ", right)
l = []
i = 0
j = 0
while i < len(left) and j < len(right):
print(f"Comparing {left[i]} and {right[j]}")
if left[i] < right[j]:
l.append(left[i])
i += 1
else:
l.append(right[j])
j += 1
print(l)
while i < len(left):
print(f"Adding {left[i]} from left list")
l.append(left[i])
i += 1
while j < len(right):
print(f"Adding {right[j]} from right list")
l.append(right[j])
j += 1
print(l)
print("----------")
return l
alist = [10, 4, 5, 2, 6, 7, 9, 8, 0, 3, 1]
sorted_list = merge_sort(alist)
print("------------------------------")
print(alist)
print(sorted_list)
Merge Sort Code Output
left list: [10]
right list: [4]
Comparing 10 and 4
[4]
Adding 10 from left list
[4, 10]
----------
left list: [2]
right list: [6]
Comparing 2 and 6
[2]
Adding 6 from right list
[2, 6]
----------
left list: [5]
right list: [2, 6]
Comparing 5 and 2
Comparing 5 and 6
[2, 5]
Adding 6 from right list
[2, 5, 6]
----------
left list: [4, 10]
right list: [2, 5, 6]
Comparing 4 and 2
Comparing 4 and 5
Comparing 10 and 5
Comparing 10 and 6
[2, 4, 5, 6]
Adding 10 from left list
[2, 4, 5, 6, 10]
----------
left list: [9]
right list: [8]
Comparing 9 and 8
[8]
Adding 9 from left list
[8, 9]
----------
left list: [7]
right list: [8, 9]
Comparing 7 and 8
[7]
Adding 8 from right list
Adding 9 from right list
[7, 8, 9]
----------
left list: [3]
right list: [1]
Comparing 3 and 1
[1]
Adding 3 from left list
[1, 3]
----------
left list: [0]
right list: [1, 3]
Comparing 0 and 1
[0]
Adding 1 from right list
Adding 3 from right list
[0, 1, 3]
----------
left list: [7, 8, 9]
right list: [0, 1, 3]
Comparing 7 and 0
Comparing 7 and 1
Comparing 7 and 3
[0, 1, 3]
Adding 7 from left list
Adding 8 from left list
Adding 9 from left list
[0, 1, 3, 7, 8, 9]
----------
left list: [2, 4, 5, 6, 10]
right list: [0, 1, 3, 7, 8, 9]
Comparing 2 and 0
Comparing 2 and 1
Comparing 2 and 3
Comparing 4 and 3
Comparing 4 and 7
Comparing 5 and 7
Comparing 6 and 7
Comparing 10 and 7
Comparing 10 and 8
Comparing 10 and 9
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Adding 10 from left list
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
----------
------------------------------
[10, 4, 5, 2, 6, 7, 9, 8, 0, 3, 1]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Goal For Round 7 of the #100DaysofCode Challenge
This is my seventh round of the “#100daysofcode” challenge. I will be continuing my work from round five and round six into round seven. I am currently working through the book “Cracking the Coding Interview” by Gayle Laakmann McDowell. My goal is to become more familiar with algorithms and data structures. This goal was derived from my goal to better understand operating systems and key programs that I use in the terminal regularly e.g. Git. This goal was in turn derived from my desire to better understand the fundamental tools used for coding outside of popular GUIs. This in turn was derived from my desire to be a better back-end developer.
I have no idea if my path is correct but I am walking down this road anyways. Worst case scenario I learn a whole bunch of stuff that will help me out on my own personal projects.