Sorting関連

bubble_sort.py

# Bubble Sort - "Bubbling" the largest element to the right!
# (pseudo-code)
# list = [...]
# for each i from 1 to len(list)
#     compare two adjacent elements
#     if the first element is greater than the second element
#         swap two elements

# Time Complexity
# O(n^2) algorithm


def bubble_sort_original(alist):

    round = 0
    steps = 0

    for n in range(len(alist)):
        round += 1

        print("======================")
        print("[Round] ", round)

        for i in range(len(alist) - 1):

            steps += 1

            if alist[i] > alist[i + 1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i]
            print("-------------------------")
            print("steps:", steps, "|", alist)



def bubble_sort_improved_1(alist):
    round = 0
    steps = 0

    for n in range(len(alist)):
        round += 1

        print("======================")
        print("[Round] ", round)

        for i in range(len(alist) - 1 -n):

            steps += 1

            if alist[i] > alist[i + 1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i]
            print("-------------------------")
            print("steps:", steps, "|", alist)


def bubble_sort_improved_2(alist):

    round = 0
    steps = 0


    for scan in range(len(alist)):
        round += 1
        swaps = 0

        print("======================")
        print("[Round] ", round)

        for i in range(len(alist) - 1 - scan):
            steps += 1
            if alist[i] > alist[i + 1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i]
                swaps += 1

            print("-------------------------")
            print("steps:", steps, "|", alist)

        if swaps == 0: # not swapped
            return


while True:

    alist = [5, 1, 3, 2, 4]

    print("1. bubble_sort_original\n2. bubble_sort_improved_1\n3. bubble_sort_improved_2")
    select = int(input("Which sort do you use? "))

    if select == 1:
        bubble_sort_original(alist)
    elif select == 2:
        bubble_sort_improved_1(alist)
    elif select == 3:
        bubble_sort_improved_2(alist)
    elif select == 0:
        break

section_search.py

# Selection Sort
# (pseudo-code)
# for each scan from 0 to len(alist)
#     find the min element (linear search)
#     swap the min element with alist[scan]

# Time Complexity
# O(n^2) algorithm


def section_search(alist):

    index_min = 0
    steps = 0
    rounds = 0

    for current in range(len(alist)):

        rounds += 1

        print("======================")
        print("[Round] ", rounds)

        n_min = alist[current]

        # scan to find minimum value
        for i in range(current, len(alist)):

            steps += 1

            n_min = min(n_min, alist[i])
            index_min = alist.index(n_min)

        # swap at the end of scan
        alist[current], alist[index_min] = alist[index_min], alist[current]
        print("steps:", steps, "|", alist)


def section_search_improved(alist):

    index_min = 0
    steps = 0
    swaps = 0
    rounds = 0

    for current in range(len(alist)-1): # improve point 1
        rounds += 1

        print("======================")
        print("[Round] ", rounds)

        n_min = alist[current]

        # scan to find minimum value
        for i in range(current+1, len(alist)): # improve point 2
            steps += 1
            n_min = min(n_min, alist[i])
            index_min = alist.index(n_min)

        # swap at the end of scan
        if not index_min == current: # improve point 3
            alist[current], alist[index_min] = alist[index_min], alist[current]
            swaps += 1
        print("steps:", steps, "swaps:", swaps, "|", alist)


while True:

    alist = [5, 1, 3, 2, 4]

    print("1. section_search\n2. section_search_improved\n0. exit")
    select = int(input("Which sort do you use? "))

    if select == 1:
        section_search(alist)
    elif select == 2:
        section_search_improved(alist)
    elif select == 0:
        break