I have to write a program that:
- Generates 100 random lists with lengths increasing from 10 to 10000. Each list should consist of numbers drawn from the range [0, 1) using the random() function from the random module.
- For each list, he performs an experiment consisting in sorting it using four algorithms and write down the comparison numbers. The output of the experiment should be a list [n, lpq, lph, lpi, lpb],where n is the length of the input list and lpq, lph, lpi, lpb are the number of comparisons made through QUICK-SORT, HEAP-SORT, INSERTION-SORT and BUBBLE-SORT in turn. Note: It is important that each list be sorted with four algorithms. For this purpose, it is necessarysort a copy of the list (because sorting changes the list).
- Saves the results of experiments in a file in CSV format. Each result should be written on a separate line. You should use the csv module.
I have got a code, that generates 100 lists and I have a codes for four sorting algoritms. But how to combine it into one? Under I post what I have.
import random
num_lists = 100
min_length = 10
max_length = 10000
step = 10
lists=[]
for i in range(num_lists):
length = random.randrange(min_length, max_length+1, step)
lists.append([random.random() for _ in range(length)])
for lst in lists:
print(lists)
# # QIUCK SORT
def partition(a, p, r):
x = a[r]
i = p - 1
comparisons = 0
for j in range(p, r):
comparisons += 1
if a[j] <= x:
i += 1
a[i], a[j] = a[j], a[i]
a[i + 1], a[r] = a[r], a[i + 1]
return i + 1, comparisons
def quick_sort(a, p, r):
comparisons = 0
if p < r:
q, comparisons1 = partition(a, p, r)
comparisons += comparisons1
comparisons2 = 0
comparisons2 += quick_sort(a, p, q - 1)
comparisons2 += quick_sort(a, q + 1, r)
comparisons += comparisons2
return comparisons
# # HEAP SORT
def max_heapify(a, n, i):
count = 0
l, r = 2 * i + 1, 2 * i + 2
largest = i
if l < n:
count += 1
if a[l] > a[largest]:
largest = l
if r < n:
count += 1
if a[r] > a[largest]:
largest = r
if largest != i:
a[i], a[largest] = a[largest], a[i]
count += max_heapify(a, n, largest)
return count
def build_max_heap(a):
n = len(a)
count = 0
for i in range(n // 2, -1, -1):
count += max_heapify(a, n, i)
return count
def heap_sort(a):
count = build_max_heap(a)
n = len(a)
for i in range(n - 1, 0, -1):
a[0], a[i] = a[i], a[0]
count += max_heapify(a, i, 0)
return count
# BUBBLE SORT
def bubble_sort(a):
n = len(a)
comparisons = 0
for i in range(n-1):
zamiany = False
for j in range(n-i-1):
comparisons += 1
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
zamiany = True
if not zamiany:
break
return comparisons
# INSERTION SORT
def insertion_sort(a):
comparisons = 0
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1], a[j] = a[j], a[j + 1]
j -= 1
comparisons += 1
if j >= 0:
comparisons += 1
a[j + 1] = key
return comparisons
All the codes are okey and they are working. I have a problem with combining it into one big code. And maybe you know how to write the output into CSV as in the task?
Aucun commentaire:
Enregistrer un commentaire