정렬(Sort)

in Blog / 알고리즘 on 크래프톤 정글

알고리즘을 배우며, 여러가지 정렬 방법들을 배웠고 그 정렬들의 특징을 아래 나열하였다. 정렬 방법에서도 효율적인 또는 비효율적인 정렬 방법이 존재하는데, 그거는 다음 블로그 포스팅의 복잡도에서 다루겠다

버블 정렬(Bubble sort) : 액체 속의 공기 방울이 가벼워서 올라와 버블이 생기는 모습에 의해 붙인 이름

이웃한 원소의 대소 관계를 비교 후 교환하는것(패스라고 지칭)을 반복

정렬 같은 경우 원소 수가 n일때, n-1번 만큼 패스(버블 정렬 1회)를 진행한다. 총 패스 횟수는 n(n-1)/2이다. 정렬을 진행할 때마다 정렬할 원소들은 1개씩 줄어든다.

225 ~235 페이지 볼것

단순 선택 정렬(Straight selection sort)

가장 작은 원소부터 선택해 앞에서부터 차례로 옮김

정렬 같은 경우 위 과정을 n-1번 반복하면 전체 정렬이 완료된다. 문제는 안정적이지 않다는 것이다. 여기서 안정적이지 않다는 것은 같은 원소의 순서가 바뀔 수 있다는 이야기이다.

단순 삽입 정렬(Straight insertion sort)

말로 하기가 쉽지 않은데, 첫번째의 원소 뒤부터 시작을 해서 앞에 있는 값들 보다 크거나 작을때 앞쪽으로 삽입을 한다. 삽입시 첫번째부터 시작해서 크거나 작은것을 비교해서 알맞은 공간에 삽입된다. 이 작업은 n-1번 반복하면 정렬이 완료된다.

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

242 ~ 243페이지 skip한 부분 있음

이진 삽입 정렬(Binary insertion sort)

단순 삽입 정렬의 원소 수가 많아졌을때의 단점(비교 교환 비용의 증가됨)을 해결하고자 나온 정렬 방법이다.

244 ~ 246 페이지 skip한 부분 있음

셸 정렬(Shell sort)

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

이동 방법을 줄이기 위해서 처음부터 n칸 떨어지는 것과 정렬. 그러면 정렬이 끝나진 않았지만, 거의 마친 상태에 가까워짐.

이후 에는 n/2 칸 떨어지는 것과 정렬. 이렇게 반복하면서 n값이 줄어들 텐데, n=1이 되면 단순 삽입 정렬이 수행된다.

궁금한건 n이 홀수일때는? 상관없다 없다 치면 된다.

252 ~ 254 페이지 skip한 부분 있음

퀵 정렬(Quick sort)

효율적임. 아직 다 보진 않음

병합 정렬(Merge sort)

병합할떄 첫번쨰꺼끼리 비교하면서 작은거 또는 큰거를 배열에 순차적으로 저장 나머지가 있다면, 나머지 저장

from typing import MutableSequence

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                    # 작업용 배열을 소멸

if __name__ == '__main__':
    print('병합 정렬을 수행합니다')
    num = int(input('원소 수를 입력하세요.: '))
    x = [None] * num    # 원소 수가 num인 배열을 생성

    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))

    merge_sort(x)       # 배열 x를 병합 정렬

    print('오름차순으로 정렬했습니다.')
    for i in range(num):
        print(f'x[{i}] = {x[i]}')

힙 정렬(Heap sort) - 불안정 정렬

먼저 힙과 완전 이진 트리라는 것을 알려줘야 하는데, 먼저 완전 이진 트리(Complete Binary Tree)는 루트(root) 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리(tree)를 의미하고 힙이란,’부모의 값이 자식의 값보다 항상 크다’거나 ‘부모의 값이 자식의 값보다 항상 작다’ 같은 두 값의 대소 관계를 가진 완전 이진 트리를 힙이라고 한다.

작동 순서는 크게 아래처럼 진행되면서 반복된다. 힙에서 최댓값인 루트를 꺼냄 ->루트 이외의 부분을 힙으로 만듬

힙 정렬(Heap sort) 함수

예제 : 힙 정렬과 heapify를 import해와서 사용하는법, 파이썬의 경우 기본 설정이 오름차순이다

import sys
import heapq
input = sys.stdin.readline

def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result

n=int(input())
arr = []

for i in range(n):
    arr.append(int(input()))

res = heapsort(arr)

for i in range(n):
    print(res[i])

마지막 : FixedStack 같은 경우 아래 예시처럼 최대 64개까지를 저장하는 Queue을 만들고 싶다면, 아래처럼 명령어를 사용하면 된다

from fixed_queue import FixedQueue

q = FixedQueue(64)

완전 이진 트리

파이썬 코드 이해 아직 덜됨.

도수 정렬 알아볼것

이렇게 큐의 함수들을 알아보았다. 함수가 어떻게 구성되어 있는지 알아야 추후 사용할때 효율적으로 사용할 수 있을것이다.

© 2022 JeongHwan Yun.