Testing different algorithm for checking if a list is sorted

is_sorted.py

import itertools
import time
import random
import math
import pandas as pd


def is_sorted_permutation(perm):
    for i in range(len(perm)):
        for j in range(i, len(perm)):
            if perm[i] > perm[j]:
                return False
    return True


def brute_force_check(lst):
    permutations = list(itertools.permutations(lst))
    for perm in permutations:
        for perm2 in permutations:
            if is_sorted_permutation(perm) and is_sorted_permutation(perm2):
                return True
    return False


def optimized_check(lst):
    permutations = list(itertools.permutations(lst))
    for perm in permutations:
        if is_sorted_permutation(perm):
            return True
    return False


def built_in_sorted_check(lst):
    return lst == sorted(lst)


def factorial(n):
    return math.factorial(n)


def permutation_index(lst):
    """ Calculate the permutation index of a list """
    index = 0
    factor = 1
    for i in range(len(lst) - 1, -1, -1):
        count = 0
        for j in range(i + 1, len(lst)):
            if lst[j] < lst[i]:
                count += 1
        index += count * factor
        factor *= len(lst) - i
    return index


def is_sorted_by_permutation_index(lst):
    """ Check if list is sorted by comparing permutation index to first and last indices """
    n = len(lst)
    original_index = permutation_index(lst)
    return original_index == 0 or original_index == factorial(n) - 1


def random_shuffle_check(lst, iterations=1000):
    """ Check if a list is sorted by randomly shuffling and checking if sorted """
    for _ in range(iterations):
        shuffled_lst = lst[:]
        random.shuffle(shuffled_lst)
        if is_sorted_permutation(shuffled_lst):
            return True
    return False


# Example list
lst = [3, 1, 2]

# Timing single execution for all methods
start_time = time.time()
result_brute_force = brute_force_check(lst)
end_time = time.time()
brute_force_time = end_time - start_time

start_time = time.time()
result_optimized = optimized_check(lst)
end_time = time.time()
optimized_time = end_time - start_time

start_time = time.time()
result_sorted = built_in_sorted_check(lst)
end_time = time.time()
sorted_time = end_time - start_time

start_time = time.time()
result_permutation_index = is_sorted_by_permutation_index(lst)
end_time = time.time()
permutation_index_time = end_time - start_time

start_time = time.time()
result_random_shuffle = random_shuffle_check(lst)
end_time = time.time()
random_shuffle_time = end_time - start_time

# Running with a larger list to see execution time
large_lst = random.sample(range(100), 5)  # Smaller size due to complexity

# Timing single execution for all methods on larger list
start_time = time.time()
result_brute_force_large = brute_force_check(large_lst)
end_time = time.time()
brute_force_large_time = end_time - start_time

start_time = time.time()
result_optimized_large = optimized_check(large_lst)
end_time = time.time()
optimized_large_time = end_time - start_time

start_time = time.time()
result_sorted_large = built_in_sorted_check(large_lst)
end_time = time.time()
sorted_large_time = end_time - start_time

start_time = time.time()
result_permutation_index_large = is_sorted_by_permutation_index(large_lst)
end_time = time.time()
permutation_index_large_time = end_time - start_time

start_time = time.time()
result_random_shuffle_large = random_shuffle_check(large_lst)
end_time = time.time()
random_shuffle_large_time = end_time - start_time

# Results for single execution
single_execution_results = {
    "Method": ["Brute Force", "Optimized", "Built-in Sorted", "Permutation Index", "Random Shuffle",
               "Brute Force (Large)", "Optimized (Large)", "Built-in Sorted (Large)", "Permutation Index (Large)",
               "Random Shuffle (Large)"],
    "Time (s)": [brute_force_time, optimized_time, sorted_time, permutation_index_time, random_shuffle_time,
                 brute_force_large_time, optimized_large_time, sorted_large_time, permutation_index_large_time,
                 random_shuffle_large_time]
}

# Number of repetitions for timing
N = 1000

# Timing repeated execution for all methods on the small list
lst = [3, 1, 2]

# Brute-force check
start_time = time.time()
for _ in range(N):
    brute_force_check(lst)
end_time = time.time()
brute_force_time_repeated = end_time - start_time

# Optimized check
start_time = time.time()
for _ in range(N):
    optimized_check(lst)
end_time = time.time()
optimized_time_repeated = end_time - start_time

# Built-in sorted() check
start_time = time.time()
for _ in range(N):
    built_in_sorted_check(lst)
end_time = time.time()
sorted_time_repeated = end_time - start_time

# Permutation index check
start_time = time.time()
for _ in range(N):
    is_sorted_by_permutation_index(lst)
end_time = time.time()
permutation_index_time_repeated = end_time - start_time

# Random shuffle check
start_time = time.time()
for _ in range(N):
    random_shuffle_check(lst)
end_time = time.time()
random_shuffle_time_repeated = end_time - start_time

# Timing repeated execution for all methods on the larger list
large_lst = random.sample(range(100), 5)  # Smaller size due to complexity

# Brute-force check on larger list
start_time = time.time()
for _ in range(N):
    brute_force_check(large_lst)
end_time = time.time()
brute_force_large_time_repeated = end_time - start_time

# Optimized check on larger list
start_time = time.time()
for _ in range(N):
    optimized_check(large_lst)
end_time = time.time()
optimized_large_time_repeated = end_time - start_time

# Built-in sorted() check on larger list
start_time = time.time()
for _ in range(N):
    built_in_sorted_check(large_lst)
end_time = time.time()
sorted_large_time_repeated = end_time - start_time

# Permutation index check on larger list
start_time = time.time()
for _ in range(N):
    is_sorted_by_permutation_index(large_lst)
end_time = time.time()
permutation_index_large_time_repeated = end_time - start_time

# Random shuffle check on larger list
start_time = time.time()
for _ in range(N):
    random_shuffle_check(large_lst)
end_time = time.time()
random_shuffle_large_time_repeated = end_time - start_time

# Results for repeated execution
repeated_execution_results = {
    "Method": ["Brute Force", "Optimized", "Built-in Sorted", "Permutation Index", "Random Shuffle",
               "Brute Force (Large)", "Optimized (Large)", "Built-in Sorted (Large)", "Permutation Index (Large)",
               "Random Shuffle (Large)"],
    "Time (s)": [brute_force_time_repeated, optimized_time_repeated, sorted_time_repeated,
                 permutation_index_time_repeated, random_shuffle_time_repeated,
                 brute_force_large_time_repeated, optimized_large_time_repeated, sorted_large_time_repeated,
                 permutation_index_large_time_repeated, random_shuffle_large_time_repeated]
}

# Creating DataFrames
df_single = pd.DataFrame(single_execution_results)
df_repeated = pd.DataFrame(repeated_execution_results)

print("Single execution:\n", df_single)
print("Repeated execution:\n", df_repeated)