samedi 22 avril 2023

Counting elements and saving to CSV file

I have to write a program that:

  1. 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.
  2. 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).
  3. 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