Last active
January 26, 2019 14:25
-
-
Save neila/b8405fc9d6fc3258820675f204752f13 to your computer and use it in GitHub Desktop.
CS110 2.1 Preclass Code
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# First subarray is arr[l..m] | |
# Second subarray is arr[m+1..r] | |
def merge(arr, l, middle, r): | |
leftlength = middle - l + 1 | |
rightlength = r - middle | |
# create temporary arrays | |
left = [] | |
right = [] | |
# Copy data to temp subarrays L[] and R[] | |
for i in range(leftlength): | |
left.append(arr[l + i]) | |
for j in range(rightlength): | |
right.append(arr[middle + 1 + j]) | |
i = 0 # Initial index of left subarray | |
j = 0 # Initial index of right subarray | |
k = l # Initial index of main array | |
# Merge the subarrays into arr[l..r] | |
while i < leftlength and j < rightlength : | |
if left[i] <= right[j] : | |
arr[k] = left[i] | |
i += 1 | |
else: | |
arr[k] = right[j] | |
j += 1 | |
k += 1 | |
# Copy the rest of left array if it remains | |
while i < leftlength: | |
arr[k] = left[i] | |
i += 1 | |
k += 1 | |
#Copy the rest of the right array if it remains | |
while j < rightlength: | |
arr[k] = right[j] | |
j += 1 | |
k += 1 | |
# l is for left index and r is right index of the subject array to be sorted | |
def mergeSort(arr,l,r): | |
if l < r: #need this if statement because it allows to stop when array length is 1 | |
middle = (l+r)//2 | |
mergeSort(arr, l, middle) | |
mergeSort(arr, middle+1, r) | |
merge(arr, l, middle, r) | |
#TEST | |
import random | |
arr = [int(100*random.random()) for i in range(100)] | |
n = len(arr) | |
print ("Generated: ", arr) | |
mergeSort(arr,0,n-1) | |
print ("\nSorted: ", arr) | |
#I could not figure out how to keep count of the steps in merge sort; each time a function calls itself, | |
#it resets the count. But without setting an initial value in the function, it can't add the counts. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment