Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- I'm new to python, I wrote the following code. Please review,
- critique and enhance.
- Thanks for your help.
- #This project compares quicksort, mergesort and bubblesort
- 1) write/test the partition routine for quicksort. (20 points) The # # rest of the code is given.
- #1) write/test the partition routine for quicksort.
- def qS(items):
- quickSortHelper(items,0,len(items)-1)
- def quickSortHelper(items,first,last):
- if first<last:
- splitpoint = partition(items,first,last)
- quickSortHelper(items,first,splitpoint-1)
- quickSortHelper(items,splitpoint+1,last)
- def partition(items,first,last):
- pivotvalue = items[first]
- leftside = first+1
- rightside = last
- done = False
- while not done:
- while leftside <= rightside and items[leftside] <= pivotvalue:
- leftside = leftside + 1
- while items[rightside] >= pivotvalue and rightside >= leftside:
- rightside = rightside -1
- if rightside < leftside:
- done = True
- else:
- temp = items[leftside]
- items[leftside] = items[rightside]
- items[rightside] = temp
- temp = items[first]
- items[first] = items[rightside]
- items[rightside] = temp
- return rightside
- # 2) write/test the merging part of the mergesort.
- def mS(items):
- #print("Splitting ",items)
- if len(items)>1:
- mid = len(items)//2
- lefthalf = items[:mid]
- righthalf = items[mid:]
- mS(lefthalf)
- mS(righthalf)
- i=0
- j=0
- k=0
- while i < len(lefthalf) and j < len(righthalf):
- if lefthalf[i] < righthalf[j]:
- items[k]=lefthalf[i]
- i=i+1
- else:
- items[k]=righthalf[j]
- j=j+1
- k=k+1
- while i < len(lefthalf):
- items[k]=lefthalf[i]
- i=i+1
- k=k+1
- while j < len(righthalf):
- items[k]=righthalf[j]
- j=j+1
- k=k+1
- # 3) write/test bubblesort. (10 points) No code is given.
- def bS(items):
- exchanges = True
- passnum = len(items)-1
- while passnum > 0 and exchanges:
- exchanges = False
- for i in range(passnum):
- if items[i]>items[i+1]:
- exchanges = True
- temp = items[i]
- items[i] = items[i+1]
- items[i+1] = temp
- passnum = passnum-1
- # 4) compare the sorts using lists of 10 and 50 items (in-order, reverse #order
- # and random (hard coded). Be sure
- # to print out the initial and sorted arrays so I can see that #your module
- # sorted properly. (10 points)
- def mergeSort(L, ascending = True):
- result = []
- if len(L) == 1:
- return L
- mid = len(L) // 2
- firsthalf = mergeSort(L[:mid])
- secondhalf = mergeSort(L[mid:])
- x, y = 0, 0
- while x < len(firsthalf) and y < len(secondhalf):
- if firsthalf[x] > secondhalf[y]: # < for descending
- result.append(secondhalf[y])
- y = y + 1
- else:
- result.append(firsthalf[x])
- x = x + 1
- result = result + firsthalf[x:]
- result = result + secondhalf[y:]
- if ascending == True :
- return result
- else:
- result.reverse()
- return result
- def _quickSort(list):
- if len(list) <= 1:
- return list
- smaller, equal, larger = [], [], []
- pivot = random.choice(list)
- for x in list:
- if x < pivot: smaller.append(x)
- elif x == pivot: equal.append(x)
- else: larger.append(x)
- return _quickSort(smaller) + equal + _quickSort(larger)
- def quickSort(list, ascending=True):
- if ascending:
- return _quickSort(list)
- else:
- return _quickSort(list)[::-1]
- def BubbleSortAsc(list):
- swapped = True
- sortedvalue=0
- while swapped:
- swapped = False
- sortedvalue+=1
- for i in range(0,len(list)-sortedvalue):
- if list[i]>list[i+1]:
- list[i], list[i+1], swapped = list[i+1], list[i], True
- def BubbleSortDsc(list):
- swapped = True
- sortedvalue=0
- while swapped:
- swapped = False
- sortedvalue+=1
- for i in range (0,len(list)-sortedvalue):
- if list[i]<list[i+1]:
- list[i], list[i+1], swapped = list[i+1], list[i], True
- list=[3,2,4,1,5,9,7,6]
- # 6) write/test a variation on quicksort (vqS) that makes the following
- # improvements:
- # chooses pivot by taking a small sample size (3 items) and using
- # median for pivot. (10 points)
- def quicksort(array, l=0, r=-1):
- if r == -1:
- r = len(array)
- # base case
- if r-l <= 1:
- return
- # pick the median of 3 possible pivots
- mid = int((l+r)*0.5)
- pivot = 0
- #pivots = [ l, mid, r-1]
- if array[l] > array[mid]:
- if array[r-1]> array[l]:
- pivot = l
- elif array[mid] > array[r-1]:
- pivot = mid
- else:
- if array[r-1] > array[mid]:
- pivot = mid
- else:
- pivot = r-1
- i = l+1
- array[l], array[pivot] = array[pivot], array[l]
- for j in range(l+1,r):
- if array[j] < array[l]:
- array[i], array[j] = array[j], array[i]
- i = i+1
- array[l], array[i-1] = array[i-1], array[l]
- quicksort(array, l, i-1)
- quicksort(array, i, r)
- return array
- ls =[random.randrange(50) for _ in range(10)]
- #7) write/test a variation on mergesort (vmS) that makes the following
- # improvement:
- # Use insertion sort for small arrays (10 items or less).
- RUN = 10
- def insertionSort(arr, left, right):
- for i in range(left + 1, right+1):
- temp = arr[i]
- j = i - 1
- while arr[j] > temp and j >= left:
- arr[j+1] = arr[j]
- j -= 1
- arr[j+1] = temp
- def hybridSort(arr, n):
- # Sort individual subarrays of size RUN
- for i in range(0, n, RUN):
- insertionSort(arr, i, min((i+31), (n-1)))
- # start merging from size RUN (or 10). It will merge
- size = RUN
- while size < n:
- for left in range(0, n, 2*size):
- mid = left + size - 1
- right = min((left + 2*size - 1), (n-1))
- merge(arr, left, mid, right)
- size = 2*size
- # utility function to print the Array
- def printArray(arr, n):
- for i in range(0, n):
- print(arr[i], end = " ")
- print()
- # Driver program to test above function
- if __name__ == "__main__":
- arr = [5, 21, 7, 23, 19,25,2]
- n = len(arr)
- items = [55,27,90,18,78,30,44,56,21,67]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement