Ttykuu

I'm new to python, and I wrote the following code. Please review, critique and enhance.

This project compares quicksort, mergesort and bubblesort

1. write/test the partition routine for quicksort. (20 points) The rest of the code is given.




2. write/test the merging part of the mergesort. (20 points) The rest of the code is given.




3. write/test bubblesort. (10 points) No code is given.




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.

#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]