PYTHON EXPERT ONLY......
Jim_Ak
assignment.zipAssignment/compare_mergeSorted.py
######################################### # Programmer: Mr. G # Date: 07.03.2015 # File Name: compare_mergeSorted.py # Description: Several example implementations of functions that # merge two sorted lists into a single one. ######################################### def mergeSorted1(sortedA, sortedB): merged = [] while len(sortedA)>0 and len(sortedB)>0: if sortedA[0] <= sortedB[0]: merged.append(sortedA.pop(0)) else: merged.append(sortedB.pop(0)) return merged + sortedA + sortedB def mergeSorted2(sortedA, sortedB): merged = [] i = 0 j = 0 while True: if i == len(sortedA): return merged + sortedB[j:] if j == len(sortedB): return merged + sortedA[i:] if sortedA[i] <= sortedB[j]: merged.append(sortedA[i]) i = i + 1 else: merged.append(sortedB[j]) j = j + 1 def mergeSorted3(sortedA, sortedB): merged = [] i = 0 j = 0 while i < len(sortedA) and j < len(sortedB): if sortedA[i] <= sortedB[j]: merged.append(sortedA[i]) i = i + 1 else: merged.append(sortedB[j]) j = j + 1 return merged + sortedA[i:] + sortedB[j:] def mergeSorted4(sortedA, sortedB): merged = [] i = 0 j = 0 while i < len(sortedA) and j < len(sortedB): if sortedA[i] <= sortedB[j]: merged.append(sortedA[i]) i = i + 1 else: merged.append(sortedB[j]) j = j + 1 merged.extend(sortedA[i:]) merged.extend(sortedB[j:]) return merged def mergeSorted5(sortedA, sortedB): merged = [] i = 0 j = 0 lenA = len(sortedA) lenB = len(sortedB) while i < lenA and j < lenB: if sortedA[i] <= sortedB[j]: merged.append(sortedA[i]) i = i + 1 else: merged.append(sortedB[j]) j = j + 1 merged.extend(sortedA[i:]) merged.extend(sortedB[j:]) return merged #---------------------------------------- import time import heapq size = 100000 for sortedA in [range(0,size,2), [size/2], [size-1]]: for sortedB in [range(0,size,2), [size/2], [size-1]]: print "" lst1 = sortedA[:] lst2 = sortedB[:] t_start = time.time() lst = mergeSorted1(lst1, lst2) t_finish = time.time() execution_time = (t_finish - t_start) * 1000.0 print 'MergeSorted1 in',execution_time,'miliseconds.' lst1 = sortedA[:] lst2 = sortedB[:] t_start = time.time() lst = mergeSorted2(lst1, lst2) t_finish = time.time() execution_time = (t_finish - t_start) * 1000.0 print 'MergeSorted2 in',execution_time,'miliseconds.' lst1 = sortedA[:] lst2 = sortedB[:] t_start = time.time() lst = mergeSorted3(lst1, lst2) t_finish = time.time() execution_time = (t_finish - t_start) * 1000.0 print 'MergeSorted3 in',execution_time,'miliseconds.' lst1 = sortedA[:] lst2 = sortedB[:] t_start = time.time() lst = mergeSorted4(lst1, lst2) t_finish = time.time() execution_time = (t_finish - t_start) * 1000.0 print 'MergeSorted4 in',execution_time,'miliseconds.' lst1 = sortedA[:] lst2 = sortedB[:] t_start = time.time() lst = mergeSorted5(lst1, lst2) t_finish = time.time() execution_time = (t_finish - t_start) * 1000.0 print 'MergeSorted5 in',execution_time,'miliseconds.' lst1 = sortedA[:] lst2 = sortedB[:] t_start = time.time() lst = heapq.merge(lst1, lst2) t_finish = time.time() execution_time = (t_finish - t_start) * 1000.0 print 'Merged by heapq.merge in',execution_time,'miliseconds.' print "\n\nComment out the execution of MergeSorted1, increase the size to 1 million, and try again." print "\nRead about Heapq queue algorithm: https://docs.python.org/2/library/heapq.html"
Assignment/Sorting Algorithms.docx
Advanced Sorting Algorithms
1. Mergesort
Pseudo code:
· If the list has less than two elements (base case)
· return the list
· otherwise:
· calculate the middle index
· recursively sort the sub list from the
beginning to the middle index
· recursively sort the sub list from the
middle index to the end
· merge the two sorted sub lists
and return the result
Note: When merging the two sorted lists the result should be a sorted list.
Explore the compare_mergeSorted.py file to understand how this helper function should work.
See animation here: http://en.wikipedia.org/wiki/Merge_sort
2. Quick Sort
Pseudo code:
· If the list has less than two elements (base case)
· return the list
· otherwise:
· arbitrarily pick a pivot element
(usually the first element)
· compare the pivot to all items in the list
and create three sub lists:
· items smaller than the pivot
· items greater than the pivot
· items equal to the pivot
· recursively sort the first two sub lists
· concatenate the three sorted sub lists
and return the result
Note: The list for items equal to the pivot is needed in case there are duplicates. Since all items in this list are of the same value, there is no need to sort it.
See animation here: http://en.wikipedia.org/wiki/Quicksort
Advanced Sorting Algorithms - Tips
1. Break the tasks to smaller ones and solve the smaller tasks independently.
The pseudo code for the mergesort suggests a new task - merge two SORTED lists.
Solve this task as a separate function.
2. Creating copies of lists increases memory usage.
3. The time needed to remove an item from a list is about the same as the time needed to insert an item at the same location. Removing items at the end is fast, removing items at the beginning is slow.
4. Popping specific elements from a list could be a time consuming operation. If other than the last element is popped, the list must be rearranged in the memory.
5. The time needed to insert an item depends on how many items that are to the right of the inserted item. Inserting items at the end is fast, but inserting items at the beginning can be relatively slow, if the list is large.
6. The time needed to append an item to a list is constant.
7. The list method extend() performs better than appending items one by one.
8. Remember to use slices from beginning to a certain index lst[:index] and from a certain index to the end: lst[index:].
