파이썬 자료구조 6-1장. 정렬 알고리즘 1

in Python on Data Structure

1. 정렬 알고리즘의 안정성

안정적인 정렬 알고리즘은 값이 같은 원소의 순서가 정렬한 후에도 유지되는 것을 말한다. 하지만 안정적이지 않은 알고리즘은 정렬한 후에도 원래의 순서가 유지된다는 보장을 할 수 없다.

2. 버블 정렬

오름차순으로 정렬을 가정하면 배열의 오른쪽부터 2개씩 비교하면서 제일 작은 것을 인덱스 0에 위치시키고 이후에는 다시 과정을 반복해서 인덱스 1, 인덱스 2… 로 위치를 찾아가는 정렬이다. 이러한 일련의 비교, 교환하는 과정을 패스라고 하며 모든 정렬이 끝나려면 패스를 n-1번 수행해야한다. n-1번인 이유는 n-1개의 원소의 정렬이 끝나면 마지막 원소는 이미 끝에 놓이기 때문이다.

# 오름차순
def buble_sort(a):
    n = len(a)
    k = 0 # 정렬한 원소를 넣을 인덱스, 교환 후 오른쪽 대상을 가리키는 변수, 범위를 단축시켜줌
    while k<n-1:  # 총 인덱스는 n-1이므로 인덱스 n까지 정렬이 완료되면 정렬 완료
        last = n-1 # last가 안바뀌었으면 이미 정렬이 완료된것으로 k에 그대로 들어가 종료
        for j in range(n-1,k,-1):
            if a[j]<a[j-1]:
                a[j],a[j-1] = a[j-1],a[j]
                last = j
        k = last

a = [5,4,3,2,1]
buble_sort(a)
print(a)

k는 교환 후 오른쪽 대상을 가리키는 변수로 k앞의 인덱스는 정렬되었다고 간주되어 범위를 단축시켜준다. 처음에 0을 대입하는 이유는 첫 번째 패스에서 맨 앞까지 모든 원소를 스캔하기 때문이다.
last 변수는 배열의 끝 인덱스로 초기화되고 교환이 발생하면 교환 후 오른쪽 대상을 가리킨다. 만약 for문을 돌았는데 last가 바뀌지 않으면 이미 정렬되었다고 판단되어 k에 last가 n-1인 상태로 들어가 while문이 종료된다.

3. 양방향 버블 정렬(셰이커 정렬)

a = [9,1,2,3,4,5]를 버블 정렬 프로그램으로 실행한다고 생각해보자. 9를 제외한 원소들은 정렬이 되었지만 버블 정렬에서는 가장 큰 원소인 9가 한 패스에 하나씩 뒤로 이동하기 때문에 정렬 작업을 빠르게 마칠 수 없다. 만약 9를 빠르게 맨 뒤로 이동시킨다면 작업 속도가 빨라질 것이다. 해결 방법으로는 홀수 패스에서는 가장 작은 원소를 맨 앞으로 이동시키고, 짝수 패스에서는 가장 큰 원소를 맨 뒤로 이동시켜 패스의 스캔 방향을 번갈아 바꾸는 것이다. 이렇게 버블 정렬을 개선한 알고리즘은 셰이커 정렬, 양방향 버블 정렬이라고 한다.

# 오름차순
def shaker_sort(a):
    # 범위 지정을 위한 left, right
    # 정렬완료 지점을 체크하기 위한 last
    left = 0
    last = right = len(a) -1 
    while left<right: # 제일 작은 수 왼쪽으로
        for i in range(right,left,-1):
            if a[i-1]>a[i]:
                a[i],a[i-1] = a[i-1],a[i]
                last = i
        left = last

        for i in range(left,right): # 제일 큰 수 오른쪽으로
            if a[i]>a[i+1]:
                a[i],a[i+1] = a[i+1],a[i]
                last = i
        right = last

right와 left를 last없이 바로 받으면 for문 안에 영향을 주기 때문에 반드시 last가 필요하다.

cf) 산술 연산에 사용하는 내장함수

  • abx(x) : x의 절댓값을 반환한다.
  • bool(x) : x의 논리값(True or False)를 반환
  • divmod(a,b) : a를 b로 나누었을 때의 몫과 나머지로 구성된 튜플을 반환
  • float(x) : 문자열 또는 수로 받은 x를 부동 소수점 수로 변환하여 값을 반환, x생략시 0.0반환
  • hex(x) : 정수값 x의 16진수 문자열을 반환
  • int(x,base) : x를 int형 정수로 변환한 값을 반환, base는 0~36의 범위에서 진수를 나타내야하며, 생략시 10진법
  • max(args1, ars2,…) : 인수의 최댓값을 반환
  • min(args1, ars2,…) : 인수의 최소값을 반환
  • oct(x) : 정수값 x에 해당하는 8진수 문자열을 반환
  • pow(x,y,z) : x의 y제곱인 (x**y)를 반환한다. z값을 입력하면 x의 y제곱을 z로 나누었을 때의 나머지를 반환, 같은 식인 pow(x,y)%z보다 효율적으로 계산이 가능
  • round(n, ndigits) : n의 소수부를 ndigits 자릿수가 되도록 반올림한 값을 반환, ndigits가 None이거나 생략한 경우 입력한 값에 가장 가까운 정수를 반환
  • sum(x,start) : x의 원소값을 처음부터 끝까지 순서대로 더한 총합에 start값을 더하여 반환, start기본값은 0


4. 단순 선택 정렬

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

  1. 아직 정렬하지 않은 부분에서 가장 작은 원소 a[min]을 선택한다.
  2. a[min]과 아직 정렬하지 않은 부분에서 맨 앞에 있는 원소를 교환한다.

이 알고리즘은 서로 이웃하지 않는 떨어져 있는 원소를 교환하므로 안정적이지 않다. 같은 원소의 순서가 이전과 바뀔 수 있다는 뜻이다.

def selection_sort(a):
    n = len(a)
    for i in range (n-1) : # n-1번하면 마지막은 자동으로 정렬
        min = i
        for j in range(i+1,n):
            if a[min]>a[j]:
                min=j
        a[min],a[i]=a[i],a[min]


5. 단순 삽입 정렬

단순 삽입 정렬은 주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘이다. 단순 선택 정렬과 비슷해 보이지만 값이 가장 작은 원소를 선택하지 않는다는 점이 다르다. 두 번째 원소부터 주목하여 그 앞의 원소들과 비교해서 자리를 찾고 다음에는 세 번째 원소를 주목하여 그 앞의 원소들과 비교해서 자리를 찾아간다.
종료 조건

  • 정렬된 배열의 왼쪽 끝에 도달한 경우
  • tmp보다 작거나 키값이 같은 원소 a[j-1]을 발견한 경우

계속 조건

  • j가 0보다 큰 경우
  • a[j-1]의 값이 tmp보다 큰 경우
def insertion_sort(a):
    n = len(a)
    for i in range(1,n): # 더 앞쪽의 알맞은 위치로 삽입해야하므로 앞에 비교대상으로 인덱스0
        tmp = a[i]
        j=i-1
        while j>=0 and tmp<a[j]:
            a[j+1] = a[j]
            j-=1
        a[j+1] = tmp        

a = [1,8,2,3,5,7,9,6,45,5,4]
insertion_sort(a)
print(a)

이 알고리즘은 서로 떨어져 있는 원소를 교환하지 않으므로 안정적이다.

6. 이진 삽입 정렬

단순 삽입 정렬은 배열 원소 수가 많아지면 원소 삽입에 필요한 비교, 교환 비용이 커진다. 그러나 이진 검색법을 사용하여 삽입 정렬을 하면 이미 정렬을 마친 배열을 제외하고 원소를 삽입해야 할 위치를 검사하므로 비용을 줄일 수 있다.

def binary_insertion_sort(a):
    n = len(a)
    for i in range(1,n):
        first = 0
        last = i-1        
        key = a[i]
        while True:
            mid = (first+last)//2
            if key>a[mid]:
               first = mid+1
            elif key<a[mid]:
                last = mid-1
            else : ## key 찾음
                break
            if first>last: ## 역전시 탈출
                break
        point = last+1 if first>last else mid +1
        # last +1 인 이유
        # 1. 마지막 한개 남은 상태에서 key가 더 커서 first가 mid+1이 된다면
        # 이미 한개의 오른쪽은 key보다 다 큰 상태이므로 last+1이 대입될 자리
        # 2. 마지막 한개 남은 상태에서 key가 작아서 last가 mid-1아 된다면 
        # 이미 한개의 왼쪽은 key보다 다 작은상태이므로 last+1이 대입될 자리 

        for j in range(i,point,-1):
            a[j]=a[j-1]
        a[point] = key

a = [1,8,2,3,5,7,9,6,45,5,4]
binary_insertion_sort(a)
print(a)


7. 단순 정렬 알고리즘의 시간 복잡도

단순 정렬(버블, 선택, 삽입) 알고리즘의 시간 복잡도는 모두 O(n^2)으로 효율이 좋지 않다.

8. bisect 모듈의 insort 함수

단순 삽입 정렬 알고리즘은 파이썬 표준 라이브러리에서 bisect 모듈의 insort() 함수로 제공한다. 이미 정렬이 끝난 배열의 상태를 유지하면서 원소를 삽입한다. 이를 이용하면 이진 삽입 정렬을 간결하게 구현할 수 있다.

# 사용법
bisect.insort(a,x,lo,hi)
a는 들어올 때 정렬 상태를 그대로 유지하면서 a[lo~hi]사이에 x를 삽입한다. 
만약 같은 원소가 여러 개 있으면 가장 오른쪽에 삽입

# 이진 삽입 정렬
from bisect import insort

def binary_insertion_sort(a):
    for i in range(1,len(a)):
        insort(a,a.pop(i),0,i)
        #pop으로 꺼내서 비교하고 삽입하고 반복

pop은 리스트의 i 인덱스에 있는 요소를 지우고 반환(이후는 알아서 앞으로 당겨짐)


© 2021. By Backtony