자료구조와 함께 배우는 알고리즘 입문 [파이썬] - 6장. 정렬 알고리즘

youngtae·2023년 3월 25일
버블 정렬알고리즘정렬퀵 정렬파이썬힙 정렬
0

알고리즘 이론 - 파이썬

목록 보기
6/9
post-thumbnail

6-1. 버블 정렬(단순 교환 정렬)

  • 이웃한 두 원소의 대소관계를 비교하여 필요에 따라 교환 반복하는 알고리즘
  • 원소가 n개인 배열에서 n-1번 비교하면 가장 작은 원소가 맨 앞으로 감 = 1pass
  • pass 한번 할때마다 대상은 1개씩 줄어듦
  • pass n-1번 수행하면 모두 정렬

def bubble_sort(arr):  # 버블정렬
	n = len(arr)
	for i in range(n-1):
		count = 0  # 교환횟수
    for j in range(n - 1, i, -1):
		    if arr[j-1] > arr[j +]:
	        arr[j-1], arr[j] = arr[j], arr[j-1]
					count += 1
		if count == 0:  # 교환횟수 0이면 모두 정렬이므로 종
				break

# 마지막으로 교환한 위치 저장하여 앞의 원소 정렬 상태면 횟수 줄이는 경우
	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
  • 원소 비교 횟수 : n-1 + n-2 + n-2 + … + 1 = n(n-1)/2,
    평균 : n(n-1)/4, O(n2)O(n^2)
  • 어떤 패스의 원소 교환 횟수가 0이면 모든 원소가 정렬을 완료한 경우이다
    그 이후의 패스는 불필요하므로 중단
  • 셰이커 정렬(양방향 버블정렬)

    • 홀수번째는 가장 작은 원소 맨 앞으로, 짝수번째는 가장 큰 원소 맨 뒤로 이동

      #셰이커 정렬
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

6-2. 단순 선택 정렬

  • 가장 작은 원소부터 선택하여 알맞은 위치로 옮기는 작업
    1. 아직 정렬하지 않은 부분에서 값이 가장 작은 원소 a[min] 선택
    2. a[min]과 아직 정렬하지 않은 부분에서 맨 앞에 있는 원소 교환
    • 정렬 범위 한칸씩 줄어듦, n-1번 반복하면 전체 정렬 완료
# 단순 선택 정렬
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]  # 정렬 할 부분에서 맨 앞의 원소와 가장 작은 원소를 교환
  • 원소 비교 횟수는 (n2−n)/2(n^2 - n) / 2, O(n2)O(n^2)
  • 서로 이웃하지 않은 원소 교환하므로 안정적이지 않음, 중복값도 교환 해버림

6-3. 단순 삽입 정렬

  • 주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬
  • 두번째 원소부터 주목
  • 가장 작은 원소 선택하지 않는다는 점에서 단순 선택 정렬과 다름
  • 아직 정렬되지 않은 부분의 맨 앞 원소를 정렬된 부분의 알맞은 위치에 삽입, n-1

#단순 삽입 정렬
for i in range(1, len(a)):
    j = i
		tem = a[i]

    while j > 0 and a[j - 1] > tmp:  # 원소가 앞의 수보다 작으면
        a[j] = a[j-1]  # 앞의 수가 한칸 씩 뒤로 이동
        j -= 1  # 왼쪽 끝에 도착하면 종료
		a[j] = tmp  # 원소는 알맞은 자리로 이동
  • 배열 왼쪽 끝에 도달하거나, tmp보다 작거나 같은 원소 발견하면 종료
  • 비교횟수, 교환횟수 n2/2n^2 /2 , O(n2)O(n^2)
  • bisect 모듈 insort() 함수로 가능
  • 이진 삽입 정렬
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

# bisent 모듈 사용
from typing import MutableSequence
import bisect

def binary_insertion_sort(a, x, lo, hi):  # 정렬 유지하면서 a[lo]~a[hi] 사이에 x 삽
    """이진 삽입 정렬(bisect.insort을 사용)"""
    for i in range(1, len(a)):
        bisect.insort(a, a.pop(i), 0, i)

6-4. 셸 정렬

  • 단순 삽입 정렬의 장점 살리고 단점 보완
  • 정렬할 배열의 원소를 그룹으로 나눠 각 그룹별로 정렬 수행 후 그룹을 합치는 작업 반복
  • 시간 복잡도 O(n1.25)O(n^1.25), 빠르지만 떨어져있는 원소 교환하므로 안정적이지 않다

def shell_sort(arr):
    N = len(arr)
    h = N // 2
    while h > 0:
        for i in range(h, N):  # h칸 떨어진 범위
            temp = arr[i]
            j = i - h
            while j >= 0 and arr[j] > temp:  # 뒤의 숫자가 크면
                arr[j + h] = arr[j]  # 두 칸 위치 바꾸기, 간격 유지하며 반복
                j -= h
            arr[j + h] = temp
        h //= 2
 # h값은 서로 배수 되지 않는게 좋음
    print(arr)

6-5. 퀵 정렬

  • 일반적으로 사용되는 아주 빠른 정렬 알고리즘, O(nlogn)O(n logn)
  • 원소가 적은 경우 그다지 빠른 알고리즘이 아님
  • 피벗 = 그룹 나누는 기준(중심축)
    • 나눠진 그룹에서 다시 피벗 기준으로 나누기 반복
    • 피벗에 따라 성능에 영향 미침
    • 가운데값, 중앙값으로 선택하는 것이 이상적

배열 두 그룹으로 나누기

  1. 양쪽 끝에서 하나씩 탐색
  2. 왼쪽: 피벗 이상인 원소 찾을때까지 스캔
    오른쪽: 피벗 이하인 원소 찾을때까지 스캔
  3. 두개 교환하고 다시 반복
  4. 탐색 위치 교차하면 종료
  5. 가운데 그룹은 피벗과 일치
  6. 탐색위치 겹칠때도 교환 - 안하면 교환 할때마다 같은 위치인지 체크해야함
# 배열 그룹 나누기
n = len(a)
    pl = 0         # 왼쪽 커서
    pr = n - 1     # 오른쪽 커서
    x = a[n // 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
  • 퀵 정렬은 위의 그룹 나누기를 재귀 호출로 그룹마다 반복
    # 퀵 정렬
def qsort(a: MutableSequence, left: int, right: int) -> None:
    """a[left] ~ a[right]를 퀵 정렬, 인자 3"""
    pl = left                   # 왼쪽 커서
    pr = right                  # 오른쪽 커서
    x = a[(left + right) // 2]  # 피벗(가운데 요소)

    while pl <= pr:    # 그룹 나누기와 같은 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:
    """퀵 정렬, 인자 1개, 처음, 끝 범위 고정"""
    qsort(a, 0, len(a) - 1)

6-6. 병합 정렬

  • 정렬 마친 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘
  • 정렬 마친 배열의 병합
    • 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업 반복
    • 각 배열에서 주목하는 원소의 값 비교, 작은 쪽 원소 꺼내 새로운 배열에 저장
       def merge_sorted_list(a: Sequence, b: Sequence, c: MutableSequence) -> None:
     """정렬을 마친 배열 a와 b를 병합하여 c에 저장"""
     pa, pb, pc = 0, 0, 0                 # 각 배열의 커서
     na, nb, nc = len(a), len(b), len(c)  # 각 배열의 원소수 
 
     while pa < na and pb < nb:  # pa와 pb를 비교하여 작은 값을 pc에 저장
         if a[pa] <= b[pb]:
             c[pc] = a[pa]
             pa += 1
         else:
             c[pc] = b[pb]
             pb += 1
         pc += 1
 
     while pa < na:              # a에 남은 원소를 복사
         c[pc] = a[pa]
         pa += 1
         pc += 1
 
     while pb < nb:              # b에 남은 원소를 복사
         c[pc] = b[pb]
         pb += 1
         pc += 1
    • 정렬 마친 두 배열 병합
      • heapq모듈 merge()함수 사용
  • 배열을 앞, 뒤로 나눈 후 앞부분 정렬, 뒷부분 정렬
  • 배열 병합 O(n), 병합 정렬 단계 log n → 전체 시간 복잡도 O(nlogn)O(n logn)
    def merge_sort(a: MutableSequence) -> None:
    """병합 정렬"""

    def _merge_sort(a: MutableSequence, left: int, right: int) -> None:
        """a[left] ~ a[right]를 재귀적으로 병합 정렬"""
        if left < right:
            center = (left + right) // 2

            _merge_sort(a, left, center)            # 배열 앞부분을 병합 정렬
            _merge_sort(a, center + 1, right)       # 배열 뒷부분을 병합 정렬

            p = j = 0
            i = k = left

            while i <= center:  # 배열 앞부분을 작업 배열에 복사
                 buff[p] = a[i]
                 p += 1
                 i += 1

            while i <= right and j < p:  # 배열 뒷부분과 작업배열 병합
                 if buff[j] <= a[i]:
                     a[k] = buff[j]
                     j += 1
                 else:
                     a[k] = a[i]
                     i += 1
                 k += 1

            while j < p:  # 나머지 원소 복사
                a[k] = buff[j]
                k += 1
                j += 1

    n = len(a)
    buff = [None] * n           # 작업용 배열을 생성
    _merge_sort(a, 0, n - 1)    # 배열 전체를 병합 정렬
    del buff                    # 작업용 배열을 소멸

6-7. 힙 정렬

  • 힙heap
    • ‘부모의 값이 자식의 값보다 항상 크다 or 작’는 조건 만족하는 완전 이진 트리
      • 형제끼리는 대소관계 적용 x, 부분 순서 트리 라고도 한다.
  • 힙 정렬: ‘힙에서 최댓값은 루트에 위치한다’는 특성 이용하여 정렬하는 알고리즘 O(nlogn)O(n log n)
  • 루트부터 배열에 추가
  • 한단계 아래에서 왼쪽원소 → 오른쪽 원소 순으로 추가
    • 원소 a[i]에서 다음의 관계 성립
      • 부모: a[ (i-1) // 2]
      • 왼쪽자식: a[ i * 2 + 1 ]
      • 오른쪽자식: a[ i * 2 + 2 ]
  • 루트 삭제한 힙 재구성
    • 루트 꺼내면 남은 원소들로 힙 재구성
    • 마지막 원소를 루트로 이동
    • 큰 값을 가진 자식과 교환, 반복 해서 내려감
    • 자식의 값이 작거나 리프( 자식이 없는 노드)에 도달하면 종료
  • 정렬되지 않은 서브트리를 힙으로 만들기
    • 가장 아랫부분의 작은 서브트리부터 상향식(bottom-up)으로 힙 재구성 진행
  • 힙 정렬 알고리즘
    1. 루트에 위치한 값 a[0] 꺼내 배열 맨 끝원소 a[-1] 와 교환
    2. 남은 원소들로 힙 재구성
    3. 루트 a[0] 꺼내 정렬되지 않은 부분 맨 끝 원소와 교환
    4. 반복

def heap_sort(a: MutableSequence) -> None:
    """힙 정렬"""

    def down_heap(a: MutableSequence, left: int, right: int) -> None:
        """a[left] ~ a[right]를 힙으로 만들기, 루트 제외 힙 상태"""
        temp = a[left]      # 루트

        parent = left
        while parent < (right + 1) // 2:
            cl = parent * 2 + 1     # 왼쪽 자식
            cr = cl + 1             # 오른쪽 자식
            child = cr if cr <= right and a[cr] > a[cl] else cl  # 큰 값을 선택합니다.
            if temp >= a[child]:  # 자식이 크면 교체 아니면 패스
                break
            a[parent] = a[child]
            parent = child
        a[parent] = temp

    n = len(a)

    for i in range((n - 1) // 2, -1, -1):   # a[i] ~ a[n-1]을 힙으로 만들기
        down_heap(a, i, n - 1)

    for i in range(n - 1, 0, -1):
        a[0], a[i] = a[i], a[0]     # 최댓값인 a[0]과 마지막 원소 a[i]를 교환
        down_heap(a, 0, i - 1)      # a[0] ~ a[i-1]을 힙으로 만들기
  • heapq 모듈 사용한 힙 정렬
import heapq
#from typing import MutableSequence

def heap_sort(a: MutableSequence) -> None:
    """힙 정렬(heapq.push와 heapq.pop를 사용)"""

    heap = []
    for i in a:
        heapq.heappush(heap, i)
    for i in range(len(a)):
        a[i] = heapq.heappop(heap)

6-8. 도수 정렬 = 카운팅 정렬

  • 원소의 대소 관계를 판단하지 않고 빠르게 정렬하는 알고리즘, 분포수 세기 정렬
  • 데이터의 최솟값 최댓값을 알고 있는 경우에만 적용 가능
    1. 모든 원소값 0인 배열 만들고,
    2. 맨 앞부터 스캔하며 해당 값의 인덱스에 +1하여 도수분포표 작성
    3. 누적 도수 분포표로 변경
  • data 리스트의 원소를 cnt리스트에서 그 원소의 인덱스에 해당하는 숫자로 찾아가서
    1 감소시키고 새로운 리스트에서 그 숫자의 인덱스에 원소 추가

카운팅 정렬

  • 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇개씩 있는지 세는 작업을 하여, 선형시간에 정렬하는 효율적인 알고리즘, O(n+k)
  • cnt = [0] * n 횟수 저장할 리스트
  • cnt[num] += 1 해당 숫자의 인덱스에 1 추가
  • 횟수를 앞에서부터 누적해서 리스트 다시 생성
  • data 리스트의 원소를 cnt리스트에서 그 원소의 인덱스에 해당하는 숫자로 찾아가서
    1 감소시키고 새로운 리스트에서 그 숫자의 인덱스에 원소 추가
def Counting_Sort(A, B, K)
# A[] = 입력 배열
# B[] = 정렬된 배열
# C[] = 카운트 배열
		C = [0] * (k+1)

		for i in range(0, len(A)):
				C[A[i]] += 1  # C에서 A의 원소에 해당하는 인덱스에 1 추가
		for i in range(1, len(C)):
				C[i] += C[i-1]  # 카운트 누적해서 C를 재생성
		for i in range(len(B)-1, -1, -1) :
				C[A[i]] -= 1  # A의 원소에 해당하는 인덱스에 찾아가서 1 감소시키고
				B[C[A[i]]] = A[i]  # B에서 감소시킨 수에 해당하는 인덱스에 원소 추가

정렬 알고리즘 비교

profile
youngtae
나의 개발기록
이전 포스트

자료구조와 함께 배우는 알고리즘 입문 [파이썬] - 5장. 재귀 알고리즘

다음 포스트

자료구조와 함께 배우는 알고리즘 입문 [파이썬] - 7장. 문자열 검색

0개의 댓글