정렬(Sorting) - 1

정렬 알고리즘

정렬(sorting) : 문자 그대로, 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업
정렬 알고리즘의 핵심은 교환, 선택, 삽입!

정렬 알고리즘의 안정성

안정 정렬 - 값이 같은 원소의 순서가 정렬한 후에도 유지
불안정 정렬 - 정렬한 후에도 원래의 순서가 유지된다는 보장 X

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

내부정렬에 대해서만 다룰 예정이며,

다음의 표의 정렬 방법들의 구현과 특징을 살펴보자..!

Burble Sort

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

• 원소 수가 n인 배열에서 n-1번 비교, 교환을 하면 가장 큰 원소인 7이 맨 뒤로 이동하며 이러한 일련의 비교, 교환 과정을 패스라고 함
• 모든 정렬이 끝나려면 n-1번의 패스가 필요하며, 수행하는 패스 횟수는 n-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]
    #___________________________________________
    # 패스
    # 배열의 맨 앞에서부터 순차적으로, 탐색하며 i번째 원소를 n-1개 원소~ i+1번째 원소까지 스캔하며, 더 작은경우 둘을 swap

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]}')

버블 정렬 알고리즘 개선

def bubble_sort1(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
            
            
            
def bubble_sort2(a: MutableSequence) -> None:
    """버블 정렬(스캔 범위를 제한)"""
    # 각각의 패스에서 비교,교환을 하다가 특정한 원소 이후에 교환을 하지 않는다면, 그 원소 앞에 위치한 원소는 이미 정렬이 완료된 것으로 간주
    # last 변수에 한번의 패스에서 가장 마지막으로 교환이 발생한 인덱스를 저장하여, 그 다음 패스의 스캔 범위를 제한
    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

Selection Sort

가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘

• 1) 아직 정렬되지 않은 부분에서 값이 가장 작은 원소 a[min]을 선택
• 2) a[min]과 아직 정렬되지 않은 부분의 맨앞에 있는 우너소와 교환

def selection_sort(a: MutableSequence) -> None:
    """단순 선택 정렬"""
    n = len(a)
    for i in range(n - 1):
        min = i  # 정렬 할 부분에서 가장 작은 원소의 인덱스
        for j in range(i + 1, n):
            if a[j] < a[min]:
                min = j
        a[i], a[min] = a[min], a[i]  # 정렬 할 부분에서 맨 앞의 원소와 가장 작은 원소를 교환 

선택정렬을 불안정 정렬

Insertion Sort

주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘
단순 선택 정렬과 비슷해 보이지만 값이 가장 작은 원소를 선택하지 않는다는 점에서 차이를 보임

def insertion_sort(a: MutableSequence) -> None:
    """단순 삽입 정렬"""
    n = len(a)
    for i in range(1, n):
        j = i
        tmp = a[i]
        while j > 0 and a[j - 1] > tmp:
            a[j] = a[j - 1]
            j -= 1
        a[j] = tmp
"""
j -> i번째 원소(해당 인덱스에서 적절한 위치에 삽입되어야 하는 원소)
tmp -> 현재까지 정렬된 부분의 값들을 스캔해 내려가면서 조건을 만족하는 경우 해당 인덱스에 값을 대입

종료조건1 : 정렬된 배열의 왼쪽 끝에 도달한 경우
종료조건2 : tmp보다 작거나 키값이 같은 원소 a[j-1]을 발견한 경우
중 하나를 만족할때까지 반복

->드모르간 법칙 적용
계속조건1 : j가 0보다 큰 경우
계속조건2 : a[j-1]의 값이 tmp보다 큰 경우

"""

• 장점 : 이미 정렬을 마쳤거나 정렬이 거의 끝나가는 상태에서는 속도가 아주 빠름
• 단점 : 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아짐

이진 삽입정렬

def binary_insertion_sort(a: MutableSequence) -> None:
    """이진 삽입 정렬"""
    n = len(a)
    for i in range(1, n):
        key = a[i]
        pl = 0      # 검색 범위의 맨 앞 원소 인덱스
        pr = i - 1  # 검색 범위의 맨 끝 원소 인덱스

        while True:
            pc = (pl + pr) // 2  # 검색 범위의 중앙 원소 인덱스
            if a[pc] == key:     # 검색 성공
                break
            elif a[pc] < key:
                pl = pc + 1
            else:
                pr = pc - 1
            if pl > pr:
                break
    
        pd = pc + 1 if pl <= pr else pr + 1  # 삽입할 위치의 인덱스

        for j in range(i, pd, -1):
            a[j] = a[j - 1]
        a[pd] = key
        
        
def binary_insertion_sort2(a: MutableSequence) -> None:
    """이진 삽입 정렬(bisect.insort을 사용)"""
    for i in range(1, len(a)):
        bisect.insort(a, a.pop(i), 0, i)

Shell Sort

단순 삽입 정렬의 장점은 살리고 단점은 보완하여 더 빠르게 정렬하는 알고리즘

정렬할 배열의 원소를 그룹으로 나눠 각 그룹별로 정렬을 수행
-> 그 후 정렬된 그룹을 합치는 작업을 반복하여 원소의 이동 횟수를 줄임

# 단순 삽입정렬에 비해 비교 횟수는 늘어나지만 전체적으로 원소의 이동 횟수가 줄어드는 장점
def shell_sort(a: MutableSequence) -> None:
    """셸 정렬"""
    n = len(a)
    h = n // 2
    while h > 0:
        for i in range(h, n):
            j = i - h
            tmp = a[i]
            while j >= 0 and a[j] > tmp:
                a[j + h] = a[j]
                j -= h
                #주목하는 원소와 비교하는 원소가 서로 이웃하지 않고 h개 만큼 떨어져 있음
            a[j + h] = tmp
        h //= 2

셸 정렬의 시간복잡도 O(n^1.25)
불안정정렬

Quick Sort

가장 빠른 정렬 알고리즘

• 피벗(pivot)
  : 비교를 수행해야하는 배열 내에서 두 그룹으로 나누는 중심축
  각 그룸에서 피벗을 선택하여 누니기를 반복하며 모든 그룹이 1명씩 남으면 정렬 완료
  

피벗을 기준으로 피벗 이하인 원소를 왼쪽, 피벗 이상인 원소를 오른쪽으로 이동시키기 위해
왼쪽 커서와 오른쪽 커서를 각각 끝에서부터 이동시키며 피벗 이상인 값이 왼쪽에서, 피벗 이하인 값이 오른쪽에서 탐색되면 그 둘의 값을 교환 -> 왼쪽, 오른쪽 커서가 교차될 때까지

pl, pr이 교차되면 배열을 두 그룹으로 나눌수 있음

   
# 배열을 두 그룹으로 나누기

def partition(a: MutableSequence) -> None:
    """배열을 분할하여 출력"""
    n = len(a)
    pl = 0         # 왼쪽 커서
    pr = n - 1     # 오른쪽 커서
    x = a[n // 2]  # 피벗(가운데 원소)
	# 배열 a를 피벗 x로 나누는 코드
    while pl <= pr:
        while a[pl] < x: pl += 1
        while a[pr] > x: pr -= 1
        if pl <= pr:
            a[pl], a[pr] = a[pr], a[pl]
            pl += 1
            pr -= 1

다음의 코드에선 중앙의 원소를 피벗으로 선택했지만, 어떤 피벗을 선택하느냐에 따라 정렬의 성능에 영향을 미친다.

두 배열을 그룹으로 나누는 것을 재귀적으로 반복하면 퀵정렬 알고리즘(분할 정복)

원소수가 1개인 그룹은 더이상 나눌 필요가 없으므로 원소수가 2개 이상은 그룹만 다음과 같이 반복해서 나눔

• pr이 a[0]보다 오른쪽에 위치하면 left<pr 왼쪽 그룹을 나눔
• pl이 a[-1]보다 왼쪽에 위치하면 pl<right 오른쪽 그룹을 나눔

def qsort(a: MutableSequence, left: int, right: int) -> None:
    """a[left] ~ a[right]를 퀵 정렬"""
    pl = left                   # 왼쪽 커서
    pr = right                  # 오른쪽 커서
    x = a[(left + right) // 2]  # 피벗(가운데 요소)

    while pl <= pr:    # 실습 6-10과 같은 while 문
        while a[pl] < x: pl += 1
        while a[pr] > x: pr -= 1
        if pl <= pr:
            a[pl], a[pr] = a[pr], a[pl]
            pl += 1
            pr -= 1
	#분할 정복
    if left < pr: qsort(a, left, pr)
    if pl < right: qsort(a, pl, right)

def quick_sort(a: MutableSequence) -> None:
    """퀵 정렬"""
    qsort(a, 0, len(a) - 1)

퀵 정렬의 비재귀적 구현

def qsort(a: MutableSequence, left: int, right: int) -> None:
    """a[left] ~ a [right]를 퀵 정렬(비재귀 버전)"""
    range = Stack(right - left + 1)  # 스택 생성

    range.push((left, right))

    while not range.is_empty():
        pl, pr = left, right = range.pop()  # 왼쪽, 오른쪽 커서를 꺼냄
        x = a[(left + right) // 2]          # 피벗(중앙 요소)

        while pl <= pr:
            while a[pl] < x: pl += 1
            while a[pr] > x: pr -= 1
            if pl <= pr:                        # 실습 6-10, 실습 6-11과 같음
                a[pl], a[pr] = a[pr], a[pl]
                pl += 1
                pr -= 1

        if left < pr: range.push((left, pr))    # 왼쪽 그룹의 커서를 저장
        if pl < right: range.push((pl, right))  # 오른쪽 그룹의 커서를 저장

def quick_sort(a: MutableSequence) -> None:
    """퀵 정렬"""
    qsort(a, 0, len(a) - 1)

-> 원소수가 적은 그룹의 나누기를 먼저하면 스택에 도잇에 쌓이는 데이터의 개수가 적어짐

피벗 선택하기

피벗의 선택 방법이 퀵 정렬의 실행 효율에 큰 영향을 미침

idea
1) 나누어야 할 배열의 원소 수가 3 이상이면 배열에서 임의의 원소 3개를 꺼내 중앙값인 원소를 피벗으로 선택
2) 나누어야할 배열의 맨 앞 원소, 가운데 원소, 맨 끝 원소를 정렬한 뒤 가운데 원소와 맨 끝에서 두번째 원소를 교환함
-> 맨 끝에서 두번째 원소값 a[right-1]이 피벗, 나눌 대상은 a[left+1] ~ a[right-2]
-> 나누는 그룹을 어느 한 쪽으로 치우치는 것을 피하면서 스캔할 원소도 3개 줄일 수 있음

def sort3(a: MutableSequence, idx1: int, idx2: int, idx3: int):
    """a[idx1], a[idx2], a[idx3]을 오름차순으로 정렬하고 가운데 값의 인덱스를 반환"""
    if a[idx2] < a[idx1]: a[idx2], a[idx1] = a[idx1], a[idx2]
    if a[idx3] < a[idx2]: a[idx3], a[idx2] = a[idx2], a[idx3]
    if a[idx2] < a[idx1]: a[idx2], a[idx1] = a[idx1], a[idx2]
    return idx2


def qsort(a: MutableSequence, left: int, right: int) -> None:
    """a[left] ~ a[right]를 퀵 정렬"""
    if right - left < 9:            # 원소 수가 9개 미만이면 단순 삽입 정렬을 호출
        insertion_sort(a, left, right)
    else:                           # 원소 수가 9개 이상이면 퀵 정렬을 수행
        pl = left                   # 왼쪽 커서
        pr = right                  # 오른쪽 커서
        m = sort3(a, pl, (pl + pr) // 2, pr)
        x = a[m]

        a[m], a[pr - 1] = a[pr - 1], a[m]
        pl += 1
        pr -= 2
        while pl <= pr:
            while a[pl] < x: pl += 1
            while a[pr] > x: pr -= 1
            if pl <= pr:
                a[pl], a[pr] = a[pr], a[pl]
                pl += 1
                pr -= 1

        if left < pr: qsort(a, left, pr)
        if pl < right: qsort(a, pl, right)

def quick_sort(a: MutableSequence) -> None:
    """퀵 정렬"""
    qsort(a, 0, len(a) - 1)