chapter 6-1 & 2 정렬 알고리즘, 버블 정렬

정렬 (sorting)

key를 항목값의 대소관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업

 

오름차순 정렬 : 값이 작은 데이터를 앞에 늘어놓는 것

내림차순 정렬 : 값이 큰 데이터를 앞에 늘어 놓는 것

 

안정적인 알고리즘 : 값이 같은 원소의 순서가 정렬한 후에도 유지되는 것

안정적이지 않은 알고리즘 : 정렬한 후에도 원래의 순서가 유지된다.

 

내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘

외부 정렬 : 정렬할 데이터가 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘

 

버블 정렬 = 단순 교환 알고리즘

이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘 

패스 : 일련의 비교 교환하는 과정

원소 수가 n인 배열에서 n - 1 번 비교,교환을 사용하면 가장 작은 원소 1이 맨 앞으로 이동

패스를 한 번 수행할 때마다 정렬할 대상은 1개씩 줄어든다. 패스를 k 번 수행하면 맨 앞부터 k 개 원소가 정렬된다.

모든 정렬이 끝나려면 패스를 n-1번 수행해야 한다.

버블 정렬은 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]  # 위치 바꾸기7
 
 
if __name__ == '__main__':
    print('버블 정렬을 수행합니다.')
    num = int(input('원소 수를 입력하세요.: '))
    x = [None] * num   # 원소 수가 num인 배열을 생성
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))
 
    bubble_sort(x)   # 배열 x를 버블 정렬
 
 
    print('오름차순으로 정렬했습니다.')
    for i in range(num):
        print(f'x[{i}] = {x[i]}')
 

위의 첫번째 방법은 앞 뒤 원소를 한번 씩 비교하며 위치를 바꾼다. 하지만  두 원소를 비교하기 전에 이미 정렬을 마친 상태라면, 즉 맨 마지막 원소까지 비교하지 않아도 이미 정렬이 완료된 경우, 굳이 비교횟수를 증가시키지 않고 패스가 원소 교환을 하지 않도록 하는 방법이다.패스에서 교환 횟수를 가리키는 변수 exchange를 만들어주고교환 횟수가 0일 때 break문을 통해 빠져나오도록 하여 비교횟수를 줄일 수 있다. 코드는 다음과 같다.

# 버블 정렬 알고리즘 구현하기(알고리즘의 개선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

# 버블 정렬 알고리즘 구현하기
from typing import MutableSequence
 
 
def bubble_sort(a:MutableSequence) -> None:
    """버블 정렬(스캔 범위를 제한)"""
    n = len(a)
    k = 0
    while k <n-1:
        last = n -1
        for j in range(n-1,k,-1):
            if a[j-1] > a[j]:
                a[j - 1] ,a[j] = a[j], a[j - 1]
                last = j
 
        k = last

셰이커 정렬 = 양방향 정렬

버블 정렬을 개선한 알고리즘이다.

# 셰이커 정렬 알고리즘 구현하기
 
from typing import MutableSequence
 
def shaker_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+1], a[j]
                last =  j
        right = last
 

while문 안에 for 문이 2개 들어있는 구조이다. 첫번째 for문은 맨 뒤에서 맨 앞으로 스캔한다.

여기서 left는 맨 앞 원소이다. 두번째 for문은 맨 앞에서 맨 뒤로 스캔한다. 여기서 right는 맨 뒤 원소이다.