Using python. Create a function that will generate a list of random numbers. Be

Question

Using python.

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 bubble sort, selection sort and insertion 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 located in the I:koppoutboxCS 222 02Final Project folder.

Run the benchmark analysis on each sorting function for list sizes of 1000, 10000, and 100000. Print the size and the benchmark values (time or counts).

Write an essay discussing your results. Be sure complete in your explanation. In your conclusion, determine which, if any, of the sorting techniques are better.

implement both comparison and time analysis. Include both in your essay

Here is the BubbleSort:

import random

def bubbleSort(aList):
for passnum in range(len(aList) - 1, 0, -1):
for i in range(passnum):
if aList[i] > aList[i + 1]:
temp = aList[i]
aList[i] = aList[i + 1]
aList[i + 1] = temp

def createList():
lyst = []
temp = []
while len(lyst) < 1000:
num = random.randint(1, 10000)
if num not in lyst:
lyst.append(num)
return lyst

def printList(lyst):
count = 0
for num in lyst:
print("%6d" % num, end="")
count += 1
if count == 15:
count = 0
print()
  
def main():
lyst = createList()
printList(lyst)
print(" ")
bubbleSort(lyst)
printList(lyst)

main()

and Here is the InsertionSort:

import random

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 = position - 1
aList[position] = currentValue

def createList():
lyst = []
temp = []
while len(lyst) < 1000:
num = random.randint(1, 10000)
if num not in lyst:
lyst.append(num)
return lyst

def printList(lyst):
count = 0
for num in lyst:
print("%6d" % num, end="")
count += 1
if count == 15:
count = 0
print()
  
def main():
lyst = createList()
printList(lyst)
print(" ")
insertionSort(lyst)
printList(lyst)

main()

and here is the SelectionSort:

import random

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

def createList():
lyst = []
temp = []
while len(lyst) < 1000:
num = random.randint(1, 10000)
if num not in lyst:
lyst.append(num)
return lyst

def printList(lyst):
count = 0
for num in lyst:
print("%6d" % num, end="")
count += 1
if count == 15:
count = 0
print()
  
def main():
lyst = createList()
printList(lyst)
print(" ")
selectionSort(lyst)
printList(lyst)

main()

Explanation / Answer

// ============== Bubble Sort ======================

import random

def bubbleSort(aList):
for passnum in range(len(aList) - 1, 0, -1):
for i in range(passnum):
if aList[i] > aList[i + 1]:
temp = aList[i]
aList[i] = aList[i + 1]
aList[i + 1] = temp

def createList():
lyst = []
temp = []
while len(lyst) < 1000:
num = random.randint(1, 10000)
if num not in lyst:
lyst.append(num)
return lyst

def printList(lyst):
count = 0
for num in lyst:
print("%6d" % num, end="")
count += 1
if count == 15:
count = 0
print()
  
def main():
lyst = createList()
printList(lyst)
print(" ")
bubbleSort(lyst)
printList(lyst)

main()

// =========== insertion Sort ================

import random

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 = position - 1
aList[position] = currentValue

def createList():
lyst = []
temp = []
while len(lyst) < 1000:
num = random.randint(1, 10000)
if num not in lyst:
lyst.append(num)
return lyst

def printList(lyst):
count = 0
for num in lyst:
print("%6d" % num, end="")
count += 1
if count == 15:
count = 0
print()
  
def main():
lyst = createList()
printList(lyst)
print(" ")
insertionSort(lyst)
printList(lyst)

main()

//======== SelectionSort =============

import random

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

def createList():
lyst = []
temp = []
while len(lyst) < 1000:
num = random.randint(1, 10000)
if num not in lyst:
lyst.append(num)
return lyst

def printList(lyst):
count = 0
for num in lyst:
print("%6d" % num, end="")
count += 1
if count == 15:
count = 0
print()
  
def main():
lyst = createList()
printList(lyst)
print(" ")
selectionSort(lyst)
printList(lyst)

main()

//===========

Best case time complexity :
    Bubble sort: O(n)
   selection sort: O(n2)
Average case time complexity :
    Bubble sort: O(n2)
   Selection sort: O(n2)
Selection Sort faster than bubble Sort    Because :

Average number of comparisons :
Bubble sort: 1/2(N^2NlnN(+ln21)N)+O(N)
Insertion sort: 1/4(N^2N)+NHN
Selection sort: (N+1)HN2N

1.Bubble sort requires K x n comparisons , where k is max distance between an initial and final position.
2. selection sort requires (n-1)x(n-2)/2 comparisons.
3. Bubble sort taking more swap times, but selection sort avoid .
4. Insertion sort does see good amount of use in production running in O(n^2).

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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