Question

Looking for python code. Perform a series of benchmarking tests on merge-sort and quick-sort to determine which one is faster. Your tests should include sequences that are “random” as well as “almost” sorted

Answer 1

Quick Sort:-

def quickSort(alist):

   quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):

   if first<last:

       splitpoint = partition(alist,first,last)

       quickSortHelper(alist,first,splitpoint-1)

       quickSortHelper(alist,splitpoint+1,last)

def partition(alist,first,last):

   pivotvalue = alist[first]

   leftmark = first+1

   rightmark = last

   done = False

   while not done:

       while leftmark <= rightmark and alist[leftmark] <= pivotvalue:

           leftmark = leftmark + 1

       while alist[rightmark] >= pivotvalue and rightmark >= leftmark:

           rightmark = rightmark -1

       if rightmark < leftmark:

           done = True

       else:

           temp = alist[leftmark]

           alist[leftmark] = alist[rightmark]

           alist[rightmark] = temp

   temp = alist[first]

   alist[first] = alist[rightmark]

   alist[rightmark] = temp

   return rightmark

Merge Sort:-

def merge(arr, l, m, r):

    n1 = m - l + 1

    n2 = r- m

  

    # create temp arrays

    L = [0] * (n1)

    R = [0] * (n2)

  

    # Copy data to temp arrays L[] and R[]

    for i in range(0 , n1):

        L[i] = arr[l + i]

  

    for j in range(0 , n2):

        R[j] = arr[m + 1 + j]

  

    # Merge the temp arrays back into arr[l..r]

    i = 0     # Initial index of first subarray

    j = 0     # Initial index of second subarray

    k = l     # Initial index of merged subarray

  

    while i < n1 and j < n2 :

        if L[i] <= R[j]:

            arr[k] = L[i]

            i += 1

        else:

            arr[k] = R[j]

            j += 1

        k += 1

    # Copy the remaining elements of L[], if there

    # are any

    while i < n1:

        arr[k] = L[i]

        i += 1

        k += 1

  

    # Copy the remaining elements of R[], if there

    # are any

    while j < n2:

        arr[k] = R[j]

        j += 1

        k += 1

# l is for left index and r is right index of the

# sub-array of arr to be sorted

def mergeSort(arr,l,r):

    if l < r:

        # Same as (l+r)//2, but avoids overflow for

        # large l and h

        m = (l+(r-1))//2

        # Sort first and second halves

        mergeSort(arr, l, m)

        mergeSort(arr, m+1, r)

        merge(arr, l, m, r)

# Driver code to test above

arr = [12, 11, 13, 5, 6, 7]

n = len(arr)

print ("Given array is")

for i in range(n):

    print ("%d" %arr[i]),

mergeSort(arr,0,n-1)

print ("\n\nSorted array is")

for i in range(n):

    print ("%d" %arr[i]),