Блог

Главная - Вопросы по программированию - Какой алгоритм сортировки был бы назван?

Какой алгоритм сортировки был бы назван?

#python #sorting

Вопрос:

Меня попросили реализовать алгоритм быстрой сортировки, однако я, возможно, не смог этого сделать и реализовал что-то другое (которое все еще сортирует). Однако, ища его имя, я не смог найти его настоящее имя.

Сложность, по-видимому, O(n*ln(n)) равна O(n), если список уже отсортирован, и O(n*n) в худшем случае.

Вот код :

 def sort(L):
    S = [L[0]]
    for i in range(1,len(L)):
        addEnd = True
        for j in range(len(S)):
            if L[i] < S[j]:
                addEnd = False
                S.insert(j, L[i])
                break
        if addEnd:
            S.insert(len(S), L[i])
    return S

Спасибо, что помогли мне !

Комментарии:

1. Это похоже на что-то вроде вставки. кстати, пузырьковая сортировка-это O(n) если список отсортирован.

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

3. Я не знаю, откуда у тебя O(n log n). Это O(n) в лучшем случае, когда входной список отсортирован.

4. О, вы правы, я имел в виду другую версию, которая была O(n*ln(n)), и код был очень похож, я исправлю это. Спасибо.

Ответ №1:

Ваша функция завершается ошибкой, если длина входных данных пуста. Но кроме этого (исправление которого тривиально), быстрая проверка гипотезы не смогла найти контрпримера.

Это тип вставки «не на месте «.

Список из одного элемента уже отсортирован, поэтому вашим начальным результатом является первый элемент входных данных.
затем вы выполняете итерацию по каждому оставшемуся элементу входных данных, ищете его позицию в всегда отсортированном результате и вставляете его туда.

Метки: