Блог

Я пытаюсь реализовать функцию таким образом, чтобы она выполняла в основном то же самое, sorted(lst) что и без использования sorted(lst) или var = lst.copy() , но я просто не могу понять, как это работает таким образом и точно так, как написано в псевдокоде.

Может кто-нибудь мне помочь?

Моя оценка:

Ниже приведен псевдокод алгоритма сортировки:

1. Начиная с начала списка, сравните каждый элемент со следующим соседом.
2. Если элемент больше, чем его следующий сосед, измените их местами.
3. Пройдите по списку до конца.
4. Если на шаге 2 были какие-либо путаницы, перейдите к шагу 1

мой код прямо сейчас:

 def my_sort(lst):
    lst_sorted = []
    lst2 = lst.copy()
    compare = True
    while compare:
        compare = False
        num = lst2[0]
        if num not in lst_sorted:
            try:
                for x in lst2:
                    if x < num:
                        x, num = num, x
                        lst_sorted.append(num)
                    elif num < x:
                        compare = True
        else:
            compare = True
    return lst_sorted
 

тестовый код, который дал мне мой профессор:

 def test_my_sort():
    lst_test = random.choices(range(-99, 100), k=6)
    lst_copy = lst_test.copy()
    lst_output = my_sort(lst_test)

    assert lst_copy == lst_test, "Error: my_sort (lst) changes the contents of list lst"
    assert lst_output == sorted(lst_test), 
        f"Error: my_sort ({lst_test}) returns {lst_output} instead of {sorted (lst_test)}"

if __name__ == '__main__':
    try:
        test_my_sort()
        print("Your my_sort () function works fine!")
 

Простое решение

Следуя вашему намерению использовать флаг compare и точные правила оценки, вот пошаговое объяснение :

 def my_sort(lst):
    # We copy the list so that the changes are not made in the original variable.
    # We will modify lst2 from now.
    lst2 = lst.copy()
    compare = True
    while compare is True:
        # compare will remain False as long as there is no swapping
        compare=False
        # We walk the list index by index, excepted the last one
        # so we don't get an index error from the last "index 1"
        for i in range(len(lst2)-1):
            # If the first is greater than the second...
            if lst2[i]>lst2[i 1]:
                # We swap
                bump = lst2[i]
                lst2[i]=lst2[i 1]
                lst2[i 1]= bump
                # and set compare to True to ask for another iteration of the while loop
                compare=True
    return lst2
 

Другой способ замены в Python

Вы можете поменять местами в одной строке:

 for i in range(len(lst2)-1):
    if lst2[i]>lst2[i 1]:
       lst2[i], lst2[i 1] = lst2[i 1], lst2[i]
       compare=True
 

Оптимизация пузырьковой сортировки

Вызывается этот алгоритм сортировки Bubble Sort .

Существует оптимизация, основанная на наблюдении, что наибольшее значение всегда переносится в конечный слот за одну итерацию. Поэтому в худшем случае вы можете избежать (n-1)**2 индексации, останавливая один индекс раньше на каждой итерации.

Вот адаптированная реализация:

 def optimized_sort(lst):
    lst2 = lst.copy()
    compare = True
    #Creating a variable to store the iteration count
    n = 0
    while compare is True :
        compare=False
        # This time, we walk from index 0 to the last index minus the iteration count
        for i in range(len(lst2) - 1 - n):
            if lst2[i]>lst2[i 1]:
                lst2[i],lst2[i 1] = lst2[i 1], lst2[i]
                compare=True
        # We increment the iteration count
        n  = 1
    return lst2
 

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

Конечно, этот алгоритм остается малопроизводительным и в основном используется в образовательных целях.

Я только изучаю python, но это работает для меня:

 def my_sort(lst):
    randHolder = []
    for ele in range(len(lst)):
        mini = min(lst)
        giveIndex = lst.index(mini)
        popped = lst.pop(giveIndex)
        randHolder.append(popped)
    lst = randHolder
    return lst