Create a function that will generate a list of random numbers. Be sure the numbe

ID: 3828772 • Letter: C

Question

Create a function that will generate a list of random numbers. Be sure the numbers are in random order. The function should accept a number that represents the size of the list and return the list. Modify the Insertion sort, Select sort and Merge sort functions to perform benchmark analysis on each of these functions. You can use some type of counting such as comparisons and /or swaps or you could use time. These files are mentioned:

Insertion sort:

def insertionSort(alist):
    for index in range(1, len(alist)):
        currentValue = alist[index]
        position = index
        while position > 0 and alist[position - 1] > currentValue:
            alist[position] = alist[position - 1]
            position -= 1
        alist[position] = currentValue

Selection sort:

def selectionSort(alist):
    for fillslot in range(len(alist) - 1, 0, -1):
        positionOfMax = 0
        for location in range(1, fillslot + 1):
            if alist[location] > alist[positionOfMax]:
                positionOfMax = location
        temp = alist[fillslot]
        alist[fillslot] = alist[positionOfMax]
        alist[positionOfMax] = temp

Merge sort:

def mergeSort(alist):
    if len(alist) > 1:
        mid = len(alist) // 2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]
        mergeSort(lefthalf)
        mergeSort(righthalf)
        i = 0
        j = 0
        k = 0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k] = lefthalf[i]
                i = i + 1
            else:
                alist[k] = righthalf[j]
                j = j + 1
            k = k + 1
        while i < len(lefthalf):
            alist[k] = lefthalf[i]
            i = i + 1
            k = k + 1
        while j < len(righthalf):
            alist[k] = righthalf[j]
            j = j + 1
            k = k + 1

Note: Run the benchmark analysis on each sorting function for list sizes of 100, 1000, and 10000. Print the size and the benchmark values (time or counts). Please use Python language

Part2: Use the binaryList. You will need to read the numbers into a list. Run a for loop 20 times searching for the 20 numbers locationed in the binaryLook.txt file. Analyze these searched using comparison.

part-3: Use the hashList.txt file (mentioned in the below). Using the hash search (mid-square method), move the numbers from the file to a hash list. Suggested size for the hash list is 1171. Once the list is created, use the hash function to search for 20 numbers founds in the hashLook.txt file. Analyze these searches using comparison. Write an essay completely explaining the two search methods.

Explanation / Answer

Hi there,

I used time to benchmark, apparently it is a really long question hence I answered the first part. Here is the code:

import time
import random
import math

def create_rand_list(size):
    """ Creates a list of 'size' random numbers. """
    MAX = 10
    return [int(math.floor((random.random()*MAX)+1)) for x in range(10)]

def insertionSort(alist):
    start = time.clock()
    for index in range(1, len(alist)):
   currentValue = alist[index]
   position = index
   while position > 0 and alist[position - 1] > currentValue:
           alist[position] = alist[position - 1]
       position -= 1
   alist[position] = currentValue
    end = time.clock()
    print "Sort: Insertion sort, Array size: " + str(len(alist)) + ", Time taken: " + str(end - start)

def selectionSort(alist):
    start = time.clock()
    for fillslot in range(len(alist) - 1, 0, -1):
        positionOfMax = 0
        for location in range(1, fillslot + 1):
            if alist[location] > alist[positionOfMax]:
                positionOfMax = location
        temp = alist[fillslot]
        alist[fillslot] = alist[positionOfMax]
        alist[positionOfMax] = temp
    end = time.clock()
    print "Sort: Selection sort, Array size: " + str(len(alist)) + ", Time taken: " + str(end - start)

def call_merge_sort(alist):
    """ Calls Merge sort. Recursive functions make it hard to benchmark,
    since the clock would be init-ed multiple times if put at the start. """
    start = time.clock()
    mergeSort(alist)
    end = time.clock()
    print "Sort: Merge sort, Array size: " + str(len(alist)) + ", Time taken: " + str(end - start)

# 100 Array size
print "** 100 Array size **"
mylist = create_rand_list(100)
insertionSort(mylist)
selectionSort(mylist)
call_merge_sort(mylist)
print "=-=-=-=-=-= "

# 1000 Array size
print "** 1000 Array size **"
mylist = create_rand_list(1000)
insertionSort(mylist)
selectionSort(mylist)
call_merge_sort(mylist)
print "=-=-=-=-=-= "

# 1000 Array size
print "** 10000 Array size **"
mylist = create_rand_list(10000)
insertionSort(mylist)
selectionSort(mylist)
call_merge_sort(mylist)
print "=-=-=-=-=-= "

The create rand list is a straight out formula

(random.random()*MAX)+1

random.random() produces a decimal number betwen 0, 1, 0 inclusive, 1 non-inclusive. We multiply it to the max number we want producing results from 0 to MAX(MAX non-inclusive). we don't want zero so we'll add 1 this steps up the list to 1 - MAX(inclusive). Sometimes results are upto MAX.1234(some floating point number greater than MAX). Floor it and we'll get the result we need. You'd like to read more on 'math.floor python' for more info. I used call merge sort it helps call merge sorted and records time for its working. If you'd like to know why go a head and put those start and end lines straight on the function 'mergeSort' and you'll know why we do this way with the merge sort or any other recursive functions. Time being shown is processor time by the way. Google it for more info.

Cheers,

Navigate

Create a function that will draw an octagonal prism as shown below. The base of

Create a function that will print a list out, given the header node. Here is the

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Create a function that will generate a list of random numbers. Be sure the numbe

Question

Explanation / Answer

Related Questions

Navigate