자료 정렬 알고리즘 - 선택, 삽입, 합병 정렬

*본문은 <컴퓨팅 사고력 향상을 위한 문제해결과 알고리즘>(성균관대학교 출판부, 2017)을 참고하여 작성하였습니다.

 

 

1. 개요

선택,삽입,버블     빠른,합병,쉘 정렬 등 존재. 앞 3개는 단순&비효율, 뒤 3개는 복잡&효율.
알고리즘 선택 기준은 1)자료의 양  2)사용 가능한 메모리 크기  3)정렬 위한 자료 이동 빈도 수
1)이 적으면 앞 3개를 주로 선택하고, 많으면 뒤 3개 선택하지만, 메모리 크기가 작으면 이들 중 메모리 적게 먹는 알고를 선택할 수밖에 없다.
효율성의 기준은 3번, 즉 이동 빈도 수고 이게 바로 빅오로 연결되는 것. 빅오를 계산하여 알고 효율성을 검토하는 것을 '시간 복잡도'라고 한다.

 

 

2. 선택 정렬(selection sort)

def selection_sort(arr):
    for i in range(len(arr)-1):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
    if min_idx != i: # 이걸 넣는 것과 안넣는 것 중 어떤게 더 좋은 알고인지 빅오 표기 공부 후 알아보기
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

 

 

 

3. 삽입 정렬(insertion sort)

이 알고리즘 볼 거 진짜 많음!!! 코드 숙달!!
- while 파트 왜 저렇게 했는지
- key값만 보관하면 되기 때문에 6번째 줄처럼 할 수 있다는 점

alist = [int(x) for x in input().split()]
for j in range(1,len(alist)):
    key = alist[j]
    i = j-1
    while i>=0 and alist[i]>key:
        alist[i+1] = alist[i]
        i -= 1
    alist[i+1] = key
print(alist)

 

 

 

4. 합병 정렬(merge sort)

병합 정렬은 분할 정복 기법(divide and conquer)과 재귀 알고리즘을 이용한 정렬 알고리즘.

말인 즉 큰 그림에서 보면 분할(split)단계와 병합(merge)단계로 나눌 수 있음

즉 주어진 배열을 원소가 하나 밖에 남지 않을 때까지(더이상 쪼갤 수 없을 떄까지) 계속 둘로 쪼갠 후

다시 크기 순으로 재배열 하면서 원래 크기의 배열로 합친다.

 

1) 반복문으로 구현한 예

def SplitArr(aList):
    returnList = [[x] for x in aList] # Divided Array
    MergeArr(returnList)
    return returnList[0]

def MergeArr(aList):
    resultArr = []
    mid_criteria = len(aList)//2
    for i in range(0,mid_criteria):
        resultArr.append(Arrange_Join(aList[2*i], aList[2*i+1]))
    if mid_criteria%2:
        resultArr.append(aList[-1])
    return resultArr

def Arrange_Join(xa, ya):
    i,j = 0,0
    x,y = xa[i],ya[i]
    returnArr = []
    while i<len(xa) and j<len(ya):
        if x>y:
            returnArr.append(y)
            j += 1
        else:
            returnArr.append(x)
            i += 1
    returnArr.append(xa[i:]) #i,j가 본래 배열 크기 넘어간 인덱스 가질 떄 에러 안나나...?
    returnArr.append(ya[j:]) #i,j가 본래 배열 크기 넘어간 인덱스 가질 떄 에러 안나나...?
    return returnArr



aList = [int(x) for x in input().split()]
SplitArr(aList)

2) 재귀 함수로 구현한 예