[5.20] 06-2 버블 정렬

버블 정렬 bubble sort = 단순 교환 정렬 - 이웃한 두 원소의 대소관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘

버블 정렬 알아보기

pass - 비교/교환하는 과정 1세트

버블 정렬 프로그램

from typing import MutableSequence

def bubble_sort(a:MutableSequence) -> None:
    n = len(a)
    for i in range(n-1):
        for j in range(n-1, i, -1):
            if a[j-1] > a[j]:
                a[j-1], a[j] = a[j], a[j-1]

if __name__ == '__main__':
    print('버블 정렬을 수행합니다.')
    num = int(input('원소 수를 입력하세요'))
    x = [None] * num

    for i in range(num):
        x[i] = int(input(f'{i}번째 원소를 입력하세요 : '))

    bubble_sort(x)

    for i in range(num):
        print(f'x[{i}]는 {x[i]}입니다')

교환 과정 출력

from typing import MutableSequence

def bubble_sort(a:MutableSequence) -> None:
    n = len(a)
    count = 0
    chan = 0
    for i in range(n-1):
        print(f'패스 {i+1}')
        for j in range(n-1, i, -1):
            for m in range(0, n-1):
                print(f'{a[m]:2}' + ('  ' if m!= j-1 else
                                     '  ' if a[j-1] > a[j] else ' -'),
                                     end = '')
            print(f'{a[n-1]:2}')
            count += 1
            if a[j-1] > a[j]:
                chan += 1
                a[j-1], a[j] = a[j], a[j-1]
        for m in range(0, n-1):
            print(f'{a[m]:2}', end = '')
        print(f'{a[n-1]:2}')
    print(f'비교를 {count}번 했습니다.')
    print(f'교환을 {chan}번 했습니다.')
    
if __name__ == '__main__':
    print('버블 정렬을 수행합니다.')
    num = int(input('원소 수를 입력하세요'))
    x = [None] * num

    for i in range(num):
        x[i] = int(input(f'{i}번째 원소를 입력하세요 : '))

    bubble_sort(x)

    for i in range(num):
        print(f'x[{i}]는 {x[i]}입니다')

알고리즘의 개선 1

from typing import MutableSequence

def bubble_sort(a:MutableSequence) -> None:
    n = len(a)
    for i in range(n-1):
        exchng = 0
        for j in range(n-1, i, -1):
            if a[j-1] > a[j]:
                a[j-1], a[j] = a[j], a[j-1]
                exchng += 1
            if exchng == 0:
                break

if __name__ == '__main__':
    print('버블 정렬을 수행합니다.')
    num = int(input('원소 수를 입력하세요'))
    x = [None] * num

    for i in range(num):
        x[i] = int(input(f'{i}번째 원소를 입력하세요 : '))

    bubble_sort(x)

    for i in range(num):
        print(f'x[{i}]는 {x[i]}입니다')

알고리즘의 개선 2

from typing import MutableSequence

def bubble_sort(a:MutableSequence) -> None:
    n = len(a)
    for i in range(n-1):
        exchng = 0
        for j in range(n-1, i, -1):
            if a[j-1] > a[j]:
                a[j-1], a[j] = a[j], a[j-1]
                exchng += 1
            if exchng == 0:
                break

if __name__ == '__main__':
    print('버블 정렬을 수행합니다.')
    num = int(input('원소 수를 입력하세요'))
    x = [None] * num

    for i in range(num):
        x[i] = int(input(f'{i}번째 원소를 입력하세요 : '))

    bubble_sort(x)

    for i in range(num):
        print(f'x[{i}]는 {x[i]}입니다')

셰이커 정렬 알고리즘

from typing import MutableSequence

def bubble_sort(a:MutableSequence) -> None:
    left = 0
    right = len(a) -1
    last = right
    while left < right:
        for j in range(right, left, -1):
            if a[j-1] > a[j]:
                a[j-1], a[j] = a[j], a[j-1]
                last = j
        left = last

        for j in range(left, right):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j], a[j-1]
                last = j
            right = last
            
if __name__ == '__main__':
    print('버블 정렬을 수행합니다.')
    num = int(input('원소 수를 입력하세요'))
    x = [None] * num

    for i in range(num):
        x[i] = int(input(f'{i}번째 원소를 입력하세요 : '))

    bubble_sort(x)

    for i in range(num):
        print(f'x[{i}]는 {x[i]}입니다')