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

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()
print("Before Bubble sort ");
printList(lyst)
print(" ")
bubbleSort(lyst)
print("After Bubble sort ");
printList(lyst)
main()
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()
print("Before Insertion sort ");
printList(lyst)
print(" ")
insertionSort(lyst)
print("After Insertion sort ");
printList(lyst)
main()
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()
print("Before Selection sort ");
printList(lyst)
print(" ")
selectionSort(lyst)
print("After Selection sort ");
printList(lyst)
main()

Bubble Sort:

It scans the array and swaps the adjacent pairs if not in order, untill last element, repeats this one untill all the elements are ordered. 2 loops are considered and max we have n length lops => n2 time complexity and max swappings are also n2

Insertion Sort

Divides the array in 2 parts 1 is sorted with fisrt element and unsorted of remaining, then take 1st element of unsorted and insert in sorted, by shifting the lements right side, repeat this untill no more elements left in unsorted. 2 loops are considered and max we have n length lops => n2 time complexity and max shiftings are are also n2, since for first element 1 shifting, 2 -> 2 shiftings, 3rd 3, ==> 1+2+3,...n=>n2 shiftings

Selection sort

find smallest of all elements and swap with 1st element, next find second smallest element and swap with 2nd element, repeat this untill largest element and the elements are ordered. Outer loop runs n-1 times and inner lopp runs n times, totally n2 time complexity, and swapping are n, each time one swapping

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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