Starting from:
$22.99
Lab07: Mergesort Comparison
Lab07: Mergesort Comparison
1. Introduction In this exercise, we will complete two Python functions in order to implement the mergesort sorting algorithm. In the second half of the assignment, you will also compare the time this algorithm takes to run with the time taken by other algorithms. 2. Objectives The purpose of this assignment is to help you: • Practice mergesort. • See the efficiencies of various sorting algorithms in practice. Note: Before you start, if you are not familiar with mergesort, bubble sort, selection sort, or insertion sort, you are recommended to review your lecture notes and the additional materials from Dr. Sheehy on common sorting algorithms and divide-and-conquer sorting algorithms.
3. Background 3.1. Mergesort Mergesort is a classic sorting algorithm which takes a divide-and-conquer approach. It is implemented recursively, where the function takes a list as input, divides the list into two halves, then calls itself recursively for the two halves. Once the smaller portions of the list cannot be divided any further, the algorithm builds the list back up again, in sorted form, by combining the sorted pieces. So, given a list of length n, the asymptotic running time of mergesort is O(nlogn).
Wikipedia has an excellent gif that shows mergesort in action on a list of size 8.
4. Assignment In this assignment, you will need to complete the mergesort(L) function as well as its merge(A, B, L) helper function, where L is the current list to be sorted and A and B are two smaller sublists.
4.1. mergesort(L) First, we will implement the base case. In this case, if the size of the list is one or empty, this list is already sorted and we can return.
2
To divide, we simply want to create two new lists, A and B. A will contain the first half of the elements in L, and B will contain the second half of L.
To conquer, or solve the original problem using much smaller sub-problems, we recursively call mergesort() twice with the new lists A and B as the inputs. Once we have done this, we will now call the merge() function in order to combine the two lists A and B.
Note that the final line of the function, provided for you, contains three variables: cost_A, cost_B, and cost_m. The purpose of these variables is to determine the actual time, or cost, that the mergesort algorithm takes. cost_A and cost_B are the result of recursively calling mergesort(A) and mergesort(B), respectively, while cost_m is the result of calling the merge() function (discussed in the following section).
4.2. merge(A, B, L) Now, we will move to the merge(A, B, L) function. This is a helper function for the main mergesort() function, and this is where the actual merging of two lists will be done. We want to iterate over the two lists A and B, each time comparing two elements, one from each list. The third parameter, L, is the new, combined list that we are about to build up.
We will need two index variables for each of the lists A and B, say i and j. With each comparison, we will add the smaller element to L in order to end up with a list that is ultimately sorted from smallest to largest. If the elements are equal, it does not matter in which order they are added to the list. If you reach the end of one list but there are still remaining elements in the other list, simply add all remaining elements into L. Note that the input lists A and B are already sorted. The merge() function merely combines two sorted sub-lists.
A 2 3 5 B 1 4 5 index 0 1 2
For example, let’s look at the sample lists in the table above. We will begin by comparing A[0] and B[0]. 1 < 2, and so we have L = [1]. We will now compare A[0] and B[1]. 2 < 4, and so we will add 4 to the list to get L = [1, 2]. Next, we compare A[1] and B[1]; 3 < 4, and so we have L = [1, 2, 3]. We continue this same process to ultimately result in L = [1, 2, 3, 4, 5, 5]. We return the length of L, which in this case would be 6.
3
4.3 Comparison of Sorting Algorithms Notice that implementations of bubble sort, selection sort, and insertion sort are also provided. The details of these sorting algorithms will not be described in great detail in this document, but please review your notes from class and this link from Dr. Sheehy’s notes, which describes the implementations of these three functions.
Below these three additional sorting algorithms, you will see the run() function. This function uses Python’s time module to calculate the precise time that each algorithm takes.
Once you have implemented the mergesort functions correctly, running the program should look something like this:
These numbers will all vary each time you run the program. Note that run() contains a line ‘print(fun)’, where fun is the function name itself. This causes lines such as <function selectionsort at 0x105599d90 to be printed. Here, the 0x105599d90 is the memory address of the function. Memory storage is beyond the scope of this course, but it’s useful to begin to recognize what memory addresses look like.
4
If you watch the program run, you will see that mergesort runs quite quickly, and that the three O(n2) algorithms—bubble sort, selection sort, and insertion sort—are the ones that take significantly longer.
1. Introduction In this exercise, we will complete two Python functions in order to implement the mergesort sorting algorithm. In the second half of the assignment, you will also compare the time this algorithm takes to run with the time taken by other algorithms. 2. Objectives The purpose of this assignment is to help you: • Practice mergesort. • See the efficiencies of various sorting algorithms in practice. Note: Before you start, if you are not familiar with mergesort, bubble sort, selection sort, or insertion sort, you are recommended to review your lecture notes and the additional materials from Dr. Sheehy on common sorting algorithms and divide-and-conquer sorting algorithms.
3. Background 3.1. Mergesort Mergesort is a classic sorting algorithm which takes a divide-and-conquer approach. It is implemented recursively, where the function takes a list as input, divides the list into two halves, then calls itself recursively for the two halves. Once the smaller portions of the list cannot be divided any further, the algorithm builds the list back up again, in sorted form, by combining the sorted pieces. So, given a list of length n, the asymptotic running time of mergesort is O(nlogn).
Wikipedia has an excellent gif that shows mergesort in action on a list of size 8.
4. Assignment In this assignment, you will need to complete the mergesort(L) function as well as its merge(A, B, L) helper function, where L is the current list to be sorted and A and B are two smaller sublists.
4.1. mergesort(L) First, we will implement the base case. In this case, if the size of the list is one or empty, this list is already sorted and we can return.
2
To divide, we simply want to create two new lists, A and B. A will contain the first half of the elements in L, and B will contain the second half of L.
To conquer, or solve the original problem using much smaller sub-problems, we recursively call mergesort() twice with the new lists A and B as the inputs. Once we have done this, we will now call the merge() function in order to combine the two lists A and B.
Note that the final line of the function, provided for you, contains three variables: cost_A, cost_B, and cost_m. The purpose of these variables is to determine the actual time, or cost, that the mergesort algorithm takes. cost_A and cost_B are the result of recursively calling mergesort(A) and mergesort(B), respectively, while cost_m is the result of calling the merge() function (discussed in the following section).
4.2. merge(A, B, L) Now, we will move to the merge(A, B, L) function. This is a helper function for the main mergesort() function, and this is where the actual merging of two lists will be done. We want to iterate over the two lists A and B, each time comparing two elements, one from each list. The third parameter, L, is the new, combined list that we are about to build up.
We will need two index variables for each of the lists A and B, say i and j. With each comparison, we will add the smaller element to L in order to end up with a list that is ultimately sorted from smallest to largest. If the elements are equal, it does not matter in which order they are added to the list. If you reach the end of one list but there are still remaining elements in the other list, simply add all remaining elements into L. Note that the input lists A and B are already sorted. The merge() function merely combines two sorted sub-lists.
A 2 3 5 B 1 4 5 index 0 1 2
For example, let’s look at the sample lists in the table above. We will begin by comparing A[0] and B[0]. 1 < 2, and so we have L = [1]. We will now compare A[0] and B[1]. 2 < 4, and so we will add 4 to the list to get L = [1, 2]. Next, we compare A[1] and B[1]; 3 < 4, and so we have L = [1, 2, 3]. We continue this same process to ultimately result in L = [1, 2, 3, 4, 5, 5]. We return the length of L, which in this case would be 6.
3
4.3 Comparison of Sorting Algorithms Notice that implementations of bubble sort, selection sort, and insertion sort are also provided. The details of these sorting algorithms will not be described in great detail in this document, but please review your notes from class and this link from Dr. Sheehy’s notes, which describes the implementations of these three functions.
Below these three additional sorting algorithms, you will see the run() function. This function uses Python’s time module to calculate the precise time that each algorithm takes.
Once you have implemented the mergesort functions correctly, running the program should look something like this:
These numbers will all vary each time you run the program. Note that run() contains a line ‘print(fun)’, where fun is the function name itself. This causes lines such as <function selectionsort at 0x105599d90 to be printed. Here, the 0x105599d90 is the memory address of the function. Memory storage is beyond the scope of this course, but it’s useful to begin to recognize what memory addresses look like.
4
If you watch the program run, you will see that mergesort runs quite quickly, and that the three O(n2) algorithms—bubble sort, selection sort, and insertion sort—are the ones that take significantly longer.
1 file (159.1KB)
