1
\$\begingroup\$

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]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.