Sorting_Network/sorting_network_complexity.py at master · AlessandroConti11/Sorting_Network · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
import matplotlib.pyplot as plt
import numpy as np
import csv

def ls3_sort(n):
    return 9 * n - 9

def mergesort_4way(n):
    return 7 * n - 6

def rotatesort(n):
    return 10 * n + 5 * np.sqrt(n) + 11

def schnorr_shamir(n):
    return 3 * n + 22 * n**(3/4) - 18

def shearsort(n):
    return n * np.log2(n) + 3 * n - 2

# Range of n
n_values = np.arange(1, 211, 1)

# Calculating values and converting to integers
ls3_vals = ls3_sort(n_values).astype(int)
merge4_vals = mergesort_4way(n_values).astype(int)
rotate_vals = np.round(rotatesort(n_values)).astype(int)
schnorr_vals = np.round(schnorr_shamir(n_values)).astype(int)
shearsort_vals = np.round(shearsort(n_values)).astype(int)


vertical_line = []
for i in range(len(n_values)):
    if shearsort_vals[i] > rotate_vals[i]:
        vertical_line.append(n_values[i])
        print(f"shearsort - rotatesort {n_values[i]} - {shearsort_vals[i]}, {rotate_vals[i]}")
        break
for i in range(len(n_values)):
    if shearsort_vals[i] > ls3_vals[i]:
        vertical_line.append(n_values[i])
        print(f"shearsort - ls3 {n_values[i]} - {shearsort_vals[i]}, {ls3_vals[i]}")
        break
for i in range(len(n_values)):
    if shearsort_vals[i] > merge4_vals[i]:
        vertical_line.append(n_values[i])
        print(f"shearsort - 4way-mergesort {n_values[i]} - {shearsort_vals[i]}, {merge4_vals[i]}")
        break
for i in range(len(n_values)):
    if shearsort_vals[i] > schnorr_vals[i]:
        vertical_line.append(n_values[i])
        print(f"shearsort - 3n {n_values[i]} - {shearsort_vals[i]}, {schnorr_vals[i]}")
        break
for i in range(len(n_values)):
    if merge4_vals[i] > schnorr_vals[i]:
        vertical_line.append(n_values[i])
        print(f"4way-mergesort - 3n {n_values[i]} - {merge4_vals[i]}, {schnorr_vals[i]}")
        break

# Plot
plt.figure(figsize=(12, 6))
plt.plot(n_values, ls3_vals, label="LS3-Sort", linestyle='-', color='red')
plt.plot(n_values, merge4_vals, label="4-Way Mergesort", linestyle='-', color='green')
plt.plot(n_values, rotate_vals, label="Rotatesort", linestyle='-', color='blue')
plt.plot(n_values, schnorr_vals, label="3n-Sort (Schnorr-Shamir)", linestyle='-', color='magenta')
plt.plot(n_values, shearsort_vals, label="Shearsort", linestyle='-', color='cyan')

for x in vertical_line:
    plt.axvline(x=x, color='gray', linestyle='--')

plt.title("Sorting Network Complexity")
plt.xlabel("n")
plt.ylabel("Complexity")
plt.legend()
plt.grid(True)
plt.tight_layout()
plt.margins(x=0.01)
plt.margins(y=0.01)
plt.show()


with open("sorting_algorithms_data.csv", "w", newline='') as csvfile:
    writer = csv.writer(csvfile)
    writer.writerow(["x", "y_ls3", "y_merge4", "y_rotate", "y_schnorr", "y_shear"])
    for i in range(len(n_values)):
        writer.writerow([
            n_values[i],
            ls3_vals[i],
            merge4_vals[i],
            rotate_vals[i],
            schnorr_vals[i],
            shearsort_vals[i]
        ])
with open("vertical_line.csv", "w", newline='') as csvfile:
    writer = csv.writer(csvfile)
    writer.writerow(["x", "y0", "y1"])
    for x in vertical_line:
        writer.writerow([x, 0, 2300])