Метод анализа алгоритма сортировки

Question

У меня есть 4 алгоритма сортировки (линейная, частотная, двоичная и хеш-таблица) для сортировки списков слов.

Мне нужно проанализировать количество сравнений, которые каждый делает, учитывая список n слов и сравнить их друг с другом. Для этого я буду сравнивать сравнения, выполняемые каждым алгоритмом, в списках разного размера.

Мой подход заключается в моделировании слов с целыми числами (что должно сократить время сравнения и упростить создание диапазона для моей функции тестирования). В настоящее время я предполагаю, что средний лексикон текста составляет 300 слов. из которых 20% повторяются с разумной частотой, 30% менее распространены, а остальные 50% являются редко встречающимися.

Этот подход справедливый и логичный? Т.е.: будет ли это (разумно) точно представлять типичный список слов, скопированных из блока типичного текста.

код, я использую для имитации списка слов из текста следующим образом:

from random import randint, shuffle 

def get_list(size): 
    '''return list of psuedo random integers 
     in a list of length size, to represent 
     a typical block of text''' 

    my_list = [] 

    #percent of words that are typically most common, common, rare 
    most_common = 20 
    common = 30 
    rare = 50 
    vocab = 300 

    for word in range(0, int(size * (most_common/100))): 
     my_list.append(randint(0, 5)) 
    for word in range(0, int(size * (common/100))): 
     my_list.append(randint(0, 20)) 
    for word in range(0, int(size * (rare/100))): 
     my_list.append(randint(0, vocab)) 

    shuffle(my_list) 
    return my_list 

Благодаря

Answer 1

С общим числом 300, вы не в состоянии видеть существенную разницу в представление. Я считаю, что вы, вероятно, должны увеличить свой номер ввода для слов более 5000.

Как правило, для сортировки слов вы можете использовать HashTable, поскольку он более эффективен и может сэкономить место.

вы также можете искать структуру данных «пытается», если у вас есть предикативный текст.